תכנות מתקדם ב-Java/מבני נתונים מתקדמים: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
Johnny Zoo (שיחה | תרומות) |
Johnny Zoo (שיחה | תרומות) אין תקציר עריכה |
||
שורה 78:
===עצים בינאריים===
[[תמונה:Binary tree.svg|left|thumb|250px|עץ בינארי לא סדור]]
ראינו כבר מבנה בשם רשימה מקושרת - שרשרת של חוליות, כאשר כל חוליה מחוברת רק לחוליה הבאה אחריה. [[w:he:עץ בינארי|עץ בינארי]] מזכיר בצורתו רשימה כזו, רק שכאן - כל חוליה עשויה להחזיק חיבור אחד, שני חיבורים, או - אף חיבור. חיבורים אלו מכונים "'''צאצאים'''". מעתה, נכנה את החוליות "'''קדקודים'''", ואת החוליה הראשונה -
נעיר כי עצים אינם בהכרח בינאריים, אינם בהכרח סדורים, ואינם בהכרח ממומשים במבנה המזכיר רשימה מקושרת. אנו נתמקד כאן רק ב[[w:he:עץ חיפוש#עץ בינארי|עץ חיפוש בינארי]], מכיוון שהבנה שלו תעניק בסיס להבנה של מבנים מסובכים יותר המבוססים עליו (בדרך כלל, עם שינויים כאלה ואחרים).
====עץ חיפוש בינארי פשוט====
=====בניית העץ והכנסת איברים=====
העץ הבינארי הפשוט ביותר נבנה בצורה הבאה:
* האיבר הראשון שנכניס לעץ יהפוך להיות השורש.
* הכנסת האיברים הבאים תעשה לפי הכלל הבא:
** ננוע במסלול על העץ. בכל פעם שנפגוש קדקוד, נשווה אותו לאיבר החדש שלנו. אם הקדקוד אליו הגענו קטן מהאיבר החדש - נפנה ימינה. אם הוא גדול מהאיבר החדש - נפנה שמאלה.
** אם הגענו לקצה המסלול, כלומר - פנינו לאחד הכיוונים והגענו לקדקוד ריק, או שהקדקוד אליו הגענו שווה בדיוק לאיבר שרצינו להכניס - נמקם שם את האיבר החדש.
* הערה: המובן של "גדול מ-/קטן מ-" תלוי באופן בו הגדרנו אותו - לעיתים קרובות האיברים שהעץ יכיל לא יהיו בעלי סדר מובהק כלשהו. כמו כן, מימושים שונים מתירים, בניגוד לנאמר כאן, קיום שני איברים זהים בעץ - בבואכם לממש או להשתמש בעץ מוכן, זכרו תמיד לבדוק את העניין הזה.
=====חיפוש בעץ=====
חיפוש בעץ מסתמך על האופן בו הכנסנו איברים לעץ: אנו יכולים תמיד לדעת כי לכל קדקוד, הצאצא השמאלי שלו קטן ממנו, והימני - גדול ממנו. לכן, כאשר אנו מחפשים איבר, נטייל על העץ במסלול דומה: נתחיל משורש העץ. אם האיבר שאנו מחפשים קטן ממנו - נפנה שמאלה, ובמקרה ההפוך - ימינה. נמשיך כאן את המסלול עד שנגיע לאיבר שחיפשנו, או שנגיע למסקנה כי האיבר המבוקש לא נמצא בעץ.
=====מחיקת איבר=====
מחיקה של איבר מהעץ מסובכת קמעה. בשלב הראשון, צריך למצוא את האיבר בעץ. לאחר מכן, יש כמה מצבים אליהם אפשר להגיע:
* המצב הנוח ביותר הוא כאשר הקדקוד אותו נרצה למחוק הוא נטול צאצאים. במצב כזה, כל שנשאר לעשות זה לסלק את הקדקוד מהעץ (בדומה למחיקת חוליה מרשימה מקושרת, מספיק למחוק את החיבור אל אותו קדקוד).
* מצב בעייתי יותר הוא כאשר לאותו קדקוד יש צאצא אחד. במקרה זה, אפשר לפתור את הבעייה בעזרת החלפת האיבר שרצינו למחוק עם הצאצא שלו (חשבו: מדוע העץ נשאר מסודר?).
* המצב המסובך ביותר הוא כאשר לקדקוד אותו רצינו למחוק יש שני צאצאים. מבנה העץ הבינארי מבטיח לנו שהאיבר הבא בעץ, מבחינת הסדר שקבענו, הוא הצאצא השמאלי ביותר של הצאצא הימני של אותו איבר (כי הצאצא הימני וכל הצאצאים שלו גדולים מהאיבר שלנו, וידוע גם כי הצאצא השמאלי ביותר הוא גם הקטן ביותר). נחפש את אותו איבר, נחליף את ערכו של האיבר שרצינו למחוק בערכו של איבר זה, ואז נמחק אותו. באופן דומה, ניתן להשתמש גם באיבר הקודם בעץ (שהוא הצאצא הימני ביותר של הצאצא השמאלי).
===טבלת גיבוב===
| |||