שאלת מבחן במבני נתונים ומבוא לאלגוריתמים - האוניברסיטה הפתוחה 2022 - עצי חיפוש

נכון או לא נכון (הסבירו בקצרה): העוקב של צומת בעל שני ילדים בעץ ערכי מיקום הוא עלה.

רמז: העוקב (successor) הוא האיבר הקטן ביותר בתת-העץ הימני. האם הוא חייב להיות עלה, או שמא יכול להיות לו בן?

פתרון: **לא נכון.** העוקב של צומת בעל שני ילדים הוא האיבר המינימלי בתת-העץ הימני שלו, שמתקבל ע"י ירידה שמאלה עד הסוף בתת-העץ הימני. צומת זה הוא בהכרח **ללא בן שמאלי**, אך ייתכן שיש לו **בן ימני**. לכן הוא לא בהכרח עלה. **דוגמה:** ``` 5 / \ 3 8 / \ 6 9 \ 7 ``` העוקב של 5 הוא 6, שאינו עלה (יש לו בן ימני 7).