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

נניח שבונים עץ חיפוש בינרי על-ידי כך שמכניסים לעץ, בזה אחר זה, ערכים השונים זה מזה. הוכחתם שמספר הצמתים הנבדקים בחיפוש גדול ב-1 ממספר הצמתים שנבדקו בהכנסה. האם תשובתכם תשתנה, אם לפני החיפוש בוצעה מחיקה של אחד הצמתים בעץ? פרטו.

רמז: חשבו מה קורה למבנה העץ כשמוחקים צומת – האם המסלול לצומת המבוקש עשוי להשתנות?

פתרון: **כן, התשובה עשויה להשתנות.** מחיקה של צומת מעץ BST עשויה לשנות את מבנה העץ, ובכך לשנות את המסלול מהשורש לצומת מסוים. **דוגמה:** נבנה עץ עם ההכנסות: 5, 3, 7, 6. העץ: ``` 5 / \ 3 7 / 6 ``` כשהוכנס 6: נבדקו 5 → 7 → ואז 6 הוכנס כבן שמאלי של 7. סה"כ 2 צמתים נבדקו בהכנסה. בחיפוש רגיל אחרי 6: 5 → 7 → 6, סה"כ 3 = 2 + 1. ✓ כעת נמחק את 7 (באמצעות ה-successor שלו, שהוא... אין לו בן ימני, אז 7 מוחלף ב-6): ``` 5 / \ 3 6 ``` עכשיו חיפוש אחרי 6: 5 → 6, סה"כ 2 צמתים. זה כבר לא 2 + 1 = 3, אלא 2 בלבד. **מסקנה:** לאחר מחיקה, הטענה אינה בהכרח נכונה. המסלול עשוי להתקצר (או להתארך, במקרים אחרים).