שאלת מבחן במבני נתונים - אוניברסיטת בר-אילן 2013 - עצי B

נתון B-tree מדרגה 5 (זאת אומרת, מספר בניו של כל קודקוד בין 3 ל-5) שבציור. ברצוננו לבטל את הערך 40. א. צייר/י את העץ אחרי ביצוע הביטול. ב. איך תשובתך הייתה משתנה (אם בכלל) אם דרגת ה-B-tree הייתה 4?

רמז: חשב/י את מספר המפתחות המינימלי הנדרש בצומת עבור כל אחת מהדרגות (4 ו-5). לאחר מחיקת המפתח, בדוק/בדקי האם נוצר מצב של חסר (underflow), וטפל/י בו בהתאם.

פתרון: מאחר שלא סופק ציור של העץ, נניח את ה-B-tree הבא מדרגה 5, אשר מקיים את כל תכונות העץ. השורש מכיל את המפתחות `[30, 60]`. לילדיו שלושה צמתים (עלים): `[10, 20]`, `[40, 50]`, ו-`[70, 80, 90]`. ב-**B-tree** מ**דרגה** $m=5$, מספר המפתחות המינימלי בכל צומת (שאינו השורש) הוא $\lceil m/2 \rceil - 1 = \lceil 5/2 \rceil - 1 = 3 - 1 = 2$. **א. מחיקת הערך 40 מהעץ מדרגה 5:** 1. **חיפוש ומחיקה:** אנו מאתרים את המפתח 40 בצומת העלה `[40, 50]` ומוחקים אותו. הצומת נותר עם מפתח בודד: `[50]`. 2. **זיהוי חסר (underflow):** בצומת נותר מפתח אחד, בעוד שהמינימום הנדרש הוא 2. לכן, הצומת נמצא במצב של **חסר**. 3. **תיקון החסר:** עלינו לתקן את מצב החסר. אנו בוחנים את האחים המידיים של הצומת. האח השמאלי `[10, 20]` מכיל 2 מפתחות (המספר המינימלי) ולכן אינו יכול לתרום מפתח. האח הימני `[70, 80, 90]` מכיל 3 מפתחות, יותר מהמינימום, ולכן ניתן לבצע ממנו "השאלה" באמצעות פעולת **סיבוב (rotation)**. 4. **ביצוע הסיבוב:** א. המפתח המפריד באב (`[30, 60]`) בין הצומת בחסר לבין אחיו הימני, שהוא 60, יורד אל הצומת שבחסר. הצומת הופך ל-`[50, 60]`. ב. המפתח הראשון מהאח הימני, שהוא 70, עולה לאב ומחליף את המפתח 60 שירד. האב הופך ל-`[30, 70]`. ג. האח הימני מאבד את המפתח הראשון שלו והופך ל-`[80, 90]`. לאחר פעולת הסיבוב, כל הצמתים בעץ עומדים בדרישות. העץ לאחר מחיקת 40 הוא: ``` [30, 70] / | \ [10, 20] [50, 60] [80, 90] ``` $\blacksquare$ **ב. שינוי התשובה עבור עץ מדרגה 4:** ב-**B-tree** מ**דרגה** $m=4$, מספר המפתחות המינימלי בכל צומת (שאינו השורש) הוא $\lceil m/2 \rceil - 1 = \lceil 4/2 \rceil - 1 = 2 - 1 = 1$. נבצע את אותה פעולת מחיקה על העץ המקורי, אך הפעם תחת ההנחה שדרגתו 4 (העץ המקורי שהנחנו תקף גם עבור דרגה 4). 1. **חיפוש ומחיקה:** אנו מוחקים את המפתח 40 מהצומת `[40, 50]`. הצומת נותר עם מפתח בודד: `[50]`. 2. **בדיקת חסר (underflow):** בצומת נותר מפתח אחד. מכיוון שהמינימום הנדרש לצומת ב-B-tree מדרגה 4 הוא 1, הצומת **אינו** במצב של **חסר**. לכן, אין צורך לבצע פעולות נוספות של סיבוב או מיזוג. פעולת המחיקה מסתיימת כאן. העץ לאחר מחיקת 40 הוא: ``` [30, 60] / | \ [10, 20] [50] [70, 80, 90] ``` ההבדל המהותי נובע מהשינוי בדרישת המינימום למספר המפתחות בצומת, אשר תלויה בדרגת העץ. $\blacksquare$