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

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

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

פתרון: בהינתן עץ B מסדר $m=7$, מספר המפתחות המקסימלי בצומת הוא $m-1=6$ ומספר המפתחות המינימלי (למעט השורש) הוא $\lceil m/2 \rceil - 1 = 3$. הצמתים A ו-B הנתונים מכילים 6 מפתחות כל אחד, ולכן הם צמתים מלאים. **מעקב אחר הכנסת המפתחות 60 ו-210:** **1. הכנסת המפתח 60:** - נחפש את המיקום המתאים למפתח 60. החיפוש יוביל אותנו לצומת A, מכיוון ש-$7 < 60 < 110$. - צומת A מלא, ולכן הכנסה תגרום ל-**overflow** (גלישה). נכניס זמנית את המפתח 60 למערך ממוין עם מפתחות A, ונקבל: `{10, 15, 20, 50, 60, 70, 82}`. - כעת יש 7 מפתחות. נבצע **פיצול (split)**: המפתח החציוני, **50**, יקודם לצומת האב C. המפתחות הנותרים יתחלקו לשני צמתים חדשים: - צומת חדש `A'` יכיל את המפתחות שמשמאל לחציון: `{10, 15, 20}`. - צומת חדש `A''` יכיל את המפתחות שמימין לחציון: `{60, 70, 82}`. - צומת C יקבל את המפתח 50 ויעדכן את המפתחות והמצביעים שלו. מפתחותיו יהיו `{7, 50, 110, 300, 350}`. לאחר הכנסת 60, העץ ייראה כך (באזור הרלוונטי): - אב C: `{7, 50, 110, 300, 350}` - ילדים של C (משמאל לימין): ..., `A'={10,15,20}`, `A''={60,70,82}`, `B={200,...,260}`, ... **2. הכנסת המפתח 210:** - נחפש את המיקום המתאים ל-210. החיפוש יוביל לצומת B, מכיוון ש-$110 < 210 < 300$. - צומת B מלא, ולכן נבצע פיצול. המפתחות הזמניים הם: `{200, 210, 220, 230, 240, 250, 260}`. - המפתח החציוני הוא **230**. הוא יקודם לצומת האב C. הצומת B יתפצל לשניים: - צומת חדש `B'` יכיל את `{200, 210, 220}`. - צומת חדש `B''` יכיל את `{240, 250, 260}`. - צומת C יקבל את המפתח 230 ומפתחותיו יהיו `{7, 50, 110, 230, 300, 350}`. כעת צומת C מלא גם הוא, עם 6 מפתחות. המבנה הסופי של העץ באזור הרלוונטי: - אב C: `{7, 50, 110, 230, 300, 350}` - ילדים של C (משמאל לימין): ..., `A'={10,15,20}`, `A''={60,70,82}`, `B'={200,210,220}`, `B''={240,250,260}`, ... **ניתוח סיבוכיות זמן מופחתת של פעולת הכנסה:** במקרה הגרוע, פעולת הכנסה עשויה לגרום ל**פיצולים מדורגים (cascading splits)** מהעלה ועד לשורש, בעלות של $O(m \log_m n)$. עם זאת, מקרה זה נדיר. **ניתוח מופחת (amortized analysis)** מראה שהעלות הממוצעת נמוכה בהרבה. פיצול של צומת מלא יוצר שני צמתים חדשים שהם "חצי מלאים". נדרשות כ- $m/2$ הכנסות נוספות לאותו אזור בעץ כדי למלא אותם מחדש ולגרום לפיצול נוסף. לכן, ניתן "למרוח" את העלות הגבוהה של הפיצול על פני ההכנסות הרבות והזולות שאינן גורמות לפיצול. העלות המופחתת של הפיצולים היא $O(1)$ לכל הכנסה. העלות הדומיננטית היא עלות חיפוש העלה, שהיא $O(\log_m n)$. לכן, סיבוכיות הזמן המופחתת של הכנסה לעץ B היא $O(\log_m n)$. $\blacksquare$