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

א) נתון B-tree מסדר 9 בעל 4 רמות. האם הכנסת איבר חדש $x$, והוצאתו מיד אח"כ תחזיר אותנו תמיד לצורת העץ המקורית? ב) נתון B-tree מסדר 9 בעל 4 רמות. האם הוצאת איבר $x$ והכנסתו מיד אח"כ תחזיר אותנו תמיד לצורת העץ המקורית?

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

פתרון: שתי הטענות אינן נכונות. סדרת הפעולות המתוארת לא תמיד תחזיר את העץ למצבו המקורי. הסיבה המרכזית היא שאלגוריתמי האיזון של **עץ B** (B-tree) אינם בהכרח הפיכים, ובמצבים מסוימים קיימת יותר מדרך חוקית אחת לאזן את העץ. **א) הכנסה ואחריה מחיקה** לא, פעולה זו לא תמיד תחזיר את העץ לצורתו המקורית. **הסבר ודוגמה נגדית:** נבנה דוגמה נגדית עבור B-tree מסדר 9 (כלומר, כל צומת מכיל בין 4 ל-8 מפתחות, פרט לשורש). נניח שקיים מצב בו לאחר **הכנסה** שגרמה לפיצול צומת, ה**מחיקה** גורמת לתת-קיבולת (underflow) בצומת שניתן לאזן בשתי דרכים שונות (מיזוג עם אח שמאלי או מיזוג עם אח ימני). אם האלגוריתם יבחר בדרך שאינה "הפוכה" לפיצול המקורי, העץ יתקבל במבנה שונה. נניח את המצב ההתחלתי הבא: * **שורש:** `[100, 200]` * **ילדים:** `C1`, `C2`, `C3` כאשר: * `C1` מכיל 5 מפתחות (יותר מהמינימום). * `C2` הוא צומת **מלא** המכיל 8 מפתחות (למשל, `[110, 120, ..., 180]`). * `C3` מכיל 4 מפתחות (המספר המינימלי). 1. **הכנסת איבר חדש `x=185`:** * האיבר `185` מוכנס לצומת `C2`, מה שגורם לו להצפה (overflow) עם 9 מפתחות. * צומת `C2` **מתפצל**: המפתח החציוני `150` עולה לשורש, והצומת מתפצל לשני צמתים חדשים, `C2a` ו-`C2b`, שכל אחד מהם מכיל 4 מפתחות (המספר המינימלי). * **העץ החדש:** * **שורש:** `[100, 150, 200]` * **ילדים:** `C1`, `C2a=[110..140]`, `C2b=[160..180, 185]`, `C3` 2. **מחיקת האיבר `x=185`:** * האיבר `185` נמחק מהצומת `C2b`, מה שמותיר אותו עם 3 מפתחות בלבד – מצב של **תת-קיבולת (underflow)**. * כדי לאזן את `C2b`, יש לבחון את אחיו. גם אחיו השמאלי (`C2a`) וגם אחיו הימני (`C3`) מכילים את מספר המפתחות המינימלי (4), ולכן לא ניתן לבצע השאלה. * חייבים לבצע **מיזוג**. לאלגוריתם יש שתי אפשרויות חוקיות: למזג את `C2b` עם `C2a` או למזג את `C2b` עם `C3`. * **אפשרות 1 (הפוכה לפיצול):** מיזוג `C2b` עם `C2a` יחד עם המפתח `150` מהשורש יחזיר אותנו למצב המקורי. * **אפשרות 2 (מובילה למצב שונה):** נניח שהאלגוריתם בוחר למזג את `C2b` עם אחיו הימני, `C3`. הפעולה כוללת מיזוג `C2b`, `C3`, והמפתח המפריד ביניהם מהשורש (`200`). * **העץ הסופי:** * **שורש:** `[100, 150]` * **ילדים:** `C1`, `C2a`, וצומת חדש ממוזג המכיל 8 מפתחות. * העץ הסופי שונה מהעץ המקורי (למשל, מפתחות השורש שונים). מכיוון שקיימת דרך ביצוע חוקית שאינה מחזירה את העץ למצבו המקורי, התשובה היא לא. $\blacksquare$ **ב) מחיקה ואחריה הכנסה** לא, גם פעולה זו לא תמיד תחזיר את העץ לצורתו המקורית. **הסבר ודוגמה נגדית:** הסיבה דומה: פעולת ה**מחיקה** עלולה לגרום לאיזון מחדש (למשל, **השאלה** מצומת אח - rotation) המשנה את מבנה העץ. ה**הכנסה** שבאה לאחר מכן עשויה שלא לגרום לפעולת איזון כלל, ובכך להשאיר את העץ במבנה החדש והשונה. נניח את המצב ההתחלתי הבא (עבור עץ מסדר 9): * **שורש:** `[100, 200]` * **ילדים:** `C1`, `C2`, `C3` כאשר: * `C1` מכיל 4 מפתחות (מינימום). * `C2` מכיל 5 מפתחות (יותר מהמינימום). * `C3` מכיל 4 מפתחות (מינימום). 1. **מחיקת איבר `x` מהצומת `C3`:** * נניח שאנו מוחקים מפתח מצומת `C3`. הוא נותר עם 3 מפתחות, מצב של **תת-קיבולת**. * כדי לאזן את `C3`, האלגוריתם בודק את אחיו, `C2`. מכיוון של-`C2` יש יותר ממספר המפתחות המינימלי, ניתן לבצע **השאלה** (rotation). * בפעולת ההשאלה, מפתח מההורה (`200`) יורד ל-`C3`, והמפתח הגדול ביותר מ-`C2` (נניח `150`) עולה להורה במקום `200`. * **העץ החדש:** * **שורש:** `[100, 150]` * **ילדים:** `C1` (נותר עם 4 מפתחות), `C2` (נותר עם 4 מפתחות), `C3` (כעת עם 4 מפתחות). * העץ מאוזן וחוקי, אך שונה מהמבנה המקורי (מפתחות השורש וחלוקת המפתחות בין `C2` ו-`C3` השתנו). 2. **הכנסת האיבר `x` בחזרה:** * האיבר `x` יוכנס למקומו המתאים בעץ החדש (למשל, לצומת `C3`). * צומת `C3` יכיל כעת 5 מפתחות. מאחר שזהו מספר חוקי (בין 4 ל-8), **לא תתבצע פעולת איזון נוספת** (כמו פיצול). * העץ הסופי נותר במבנה אליו הגיע לאחר פעולת ההשאלה, והוא שונה מהעץ המקורי. מכיוון שהצלחנו למצוא תרחיש בו העץ לא חוזר למצבו המקורי, התשובה היא לא. $\blacksquare$