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

ניצול שטח האחסון בקדקודי B-Tree הוא כ־50%. כדי להעלות את אחוז הניצול, מוצע המבנה הבא: נגדיר $B'$-Tree מסדר $m$ בדומה ל־B-Tree מסדר $m$ רק שעבור כל קדקוד שאינו השורש נדרוש שמספר בניו $k$ יקיים $\frac{2}{3}m \leq k \leq m$ ולא רק $\frac{1}{2}m \leq k \leq m$. כדי לטפל בפיצולים, לא נאפשר פיצול של קדקוד בודד ל־2 קדקודים, אלא תמיד נפצל קדקוד גולש (עם overflow) יחד עם אחד מאחיו המלאים (אך לא גולשים), דהיינו, 2 קדקודים יהפכו ל־3 קדקודים, כ"א מלא עד כדי 2/3. (לא נטפל במחיקות ואיחודים בשאלה זו.) א) בדוגמה הבאה (בה מצוייר רק חלק מ־$B'$-Tree), הנח/י $m = 7$: (בתרשים נתון קודקוד אב $C$ עם המפתחות 7, 110, 300, 350. לקודקוד זה בן שמאלי $A$ עם המפתחות 10, 15, 20, 50, 70, 82, ובן ימני $B$ עם המפתחות 200, 220, 230, 240, 250, 260). נניח שנוסיף את הערך 60 מה שיגרום גלישה בקדקוד $A$. צייר/י את חלק העץ הרלוונטי אחרי פיצול 2 הקדקודים $A$ ו־$B$ ל־3 קדקודים, כולל התיקונים הדרושים בקדקוד $C$. ב) מה עושים אם השכן של קדקוד גולש אינו מלא? ג) לשורש אין אחים. אם נרצה שבניו של השורש אחרי פיצול גם יקיימו את התנאי ש־$\frac{2}{3}m \leq k$, איך צריך לשנות את התנאי לשורש (היות ויש רק שורש אחד, אין בעיה לחרוג מהמגבלות על הקדקודים רק עבור השורש)?

רמז: עבור סעיף א', אסוף את כל המפתחות מהקודקוד הגולש, אחיו המלא, והמפתח המפריד מהאב, וחלק אותם מחדש לשלושה קודקודים חדשים ושני מפתחות שיעלו לאב. עבור סעיף ג', חשוב כמה מפתחות (ובנים) צריך שיהיו בשורש כדי שבפיצול של 1 ל-2, שני הבנים החדשים יעמדו בדרישת המינימום.

פתרון: א) עבור $m=7$, מספר הבנים המינימלי לקודקוד שאינו השורש הוא $k_{min} = \lceil \frac{2}{3}m \rceil = \lceil \frac{14}{3} \rceil = 5$. מספר המפתחות המינימלי הוא $k_{min}-1=4$ והמקסימלי הוא $m-1=6$. הקודקודים $A$ ו-$B$ מלאים (6 מפתחות כ"א). הוספת המפתח 60 לקודקוד $A$ גורמת לו לגלוש, מכיוון שכעת יש בו 7 מפתחות: {10, 15, 20, 50, 60, 70, 82}. לפי האלגוריתם, יש לפצל את הקודקוד הגולש $A$ יחד עם אחיו המלא $B$. התהליך כולל מיזוג המפתחות של $A$ (לאחר ההוספה), המפתחות של $B$, והמפתח המפריד ביניהם מהאב $C$ (שהוא 110). 1. **איסוף המפתחות**: - מפתחות $A$ (עם 60): {10, 15, 20, 50, 60, 70, 82} (7 מפתחות) - מפתח מפריד מ-$C$: {110} (מפתח 1) - מפתחות $B$: {200, 220, 230, 240, 250, 260} (6 מפתחות) סה"כ יש $7+1+6 = 14$ מפתחות. 2. **חלוקה ל-3 קודקודים**: יש לחלק את 14 המפתחות ל-3 קודקודים חדשים ו-2 מפתחות שיעלו לאב. כל קודקוד חדש יכיל 4 מפתחות (המספר המינימלי), וסה"כ $3 \times 4 = 12$ מפתחות יחולקו בין הבנים. רשימת המפתחות הממוינת: {10, 15, 20, 50, **60**, 70, 82, 110, 200, **220**, 230, 240, 250, 260}. המפתחות שיעלו לאב הם אלו שמפרידים בין 3 קבוצות של 4 מפתחות. אלו הם המפתח ה-5 (60) והמפתח ה-10 (220) ברשימה. 3. **הקודקודים החדשים**: - קודקוד חדש $A'$: {10, 15, 20, 50} - קודקוד חדש $B'$: {70, 82, 110, 200} - קודקוד חדש $C'$: {230, 240, 250, 260} כל אחד מהקודקודים החדשים מכיל 4 מפתחות, ולכן יהיו לו 5 בנים, מה שמקיים את תנאי המינימום ($k=5$). 4. **עדכון האב $C$**: - המפתחות המקוריים של $C$: {7, 110, 300, 350} - מסירים את המפתח 110 שהפריד בין $A$ ל-$B$ וירד למטה. - מוסיפים את שני המפתחות החדשים שעלו, 60 ו-220. - המפתחות החדשים ב-$C$: {7, 60, 220, 300, 350}. המצב הסופי של חלק העץ הרלוונטי הוא: - **קודקוד אב $C$** עם המפתחות: {7, 60, 220, 300, 350} - המצביע בין 7 ל-60 מוביל לקודקוד **$A'$** עם המפתחות: {10, 15, 20, 50} - המצביע בין 60 ל-220 מוביל לקודקוד **$B'$** עם המפתחות: {70, 82, 110, 200} - המצביע בין 220 ל-300 מוביל לקודקוד **$C'$** עם המפתחות: {230, 240, 250, 260} ב) אם השכן של קודקוד גולש אינו מלא, לא ניתן לבצע את פיצול ה-2-ל-3, מכיוון שאין מספיק מפתחות כדי להבטיח שכל שלושת הקודקודים החדשים יעמדו בתנאי המינימום. במקרה כזה, נשתמש בטכניקה הסטנדרטית של **גלגול (rotation)** מפתחות, בדומה ל-B-Tree רגיל. מעבירים מפתח מהקודקוד הגולש, דרך האב, אל השכן שאינו מלא. פעולה זו מאזנת מחדש את מספר המפתחות בין שני האחים ופותרת את הגלישה ללא צורך בפיצול. ג) לשורש אין אחים, ולכן אם הוא גולש, חובה לפצל אותו. פיצול רגיל של 1-ל-2 עלול ליצור שני בנים שאינם מקיימים את תנאי המילוי של 2/3. לדוגמה, עבור $m=7$ פיצול של שורש עם 7 מפתחות ייצור שני בנים עם 3 מפתחות כל אחד (4 בנים), בעוד הנדרש הוא מינימום 4 מפתחות (5 בנים). כדי להבטיח שבניו של השורש לאחר פיצול יקיימו את התנאי, עלינו לשנות את הכלל עבור השורש ולאפשר לו להכיל יותר מפתחות לפני שהוא מתפצל. נדרוש שהשורש יתפצל רק כאשר מספר בניו $k_{root}$ מגיע לגודל כזה שחלוקתו ל-2 תיתן קודקודים תקינים. נסמן את מספר הבנים המינימלי לקודקוד רגיל $k_{min} = \lceil \frac{2}{3}m \rceil$. לאחר פיצול 1-ל-2 של השורש, לכל בן חדש יהיו לפחות $\lfloor k_{root}/2 \rfloor$ בנים. כדי לקיים את הדרישה, עלינו לדרוש $\lfloor k_{root}/2 \rfloor \geq k_{min}$. התנאי הפשוט ביותר המבטיח זאת הוא $k_{root} \geq 2k_{min}$. לכן, יש לשנות את התנאי כך שהשורש יורשה לגדול עד שיש לו $2k_{min}-1 = 2\lceil\frac{2}{3}m\rceil-1$ מפתחות (ו-$2\lceil\frac{2}{3}m\rceil$ בנים). רק כאשר מנסים להוסיף לשורש כזה מפתח נוסף, הוא יתפצל ל-2, ושני בניו החדשים יכילו כל אחד לפחות $k_{min}$ בנים, ויקיימו את תנאי המבנה. $\blacksquare$