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

בהינתן שלם חיובי $d$, הציעו מבנה נתונים $S$ שבאמצעותו ניתן לבצע את הפעולות הבאות בזמנים הנדרשים ($n$ מציין את מספר האיברים של $S$): - $\text{BUILD}(S)$: בניית המבנה $S$ מתוך סדרה של $n$ איברים **ממוינים**; זמן הריצה: $\Theta(n)$ - $\text{INSERT}(S, k)$: הכנסת איבר חדש בעל המפתח $k$ למבנה $S$; זמן הריצה: $\Theta(\lg n + d)$ - $\text{DELETE}(S, p)$: מחיקת האיבר שאליו מצביע $p$ מהמבנה $S$; זמן הריצה: $\Theta(\lg n + d)$ - $\text{D-SUCCESSOR}(S, p)$: מציאת העוקב ה-$d$ של האיבר שאליו מצביע $p$; זמן הריצה: $\Theta(1)$ **הסבר:** העוקב ה-$d$ של איבר נתון ב-$S$ מוגדר באופן רקורסיבי: העוקב הראשון הוא העוקב הרגיל; העוקב ה-$d$ הוא העוקב הרגיל של העוקב ה-$(d-1)$. **הערה:** $d$ נתון מראש אך אין להתייחס אליו כקבוע בניתוח הזמנים.

רמז: חשבו על עץ חיפוש בינרי מאוזן (כגון AVL או עץ אדום-שחור), שבו כל צומת מחזיק מצביע נוסף ל-D-SUCCESSOR שלו. בנייה ממערך ממוין אפשרית ב-$\Theta(n)$. עדכון מצביעי ה-D-SUCCESSOR בזמן INSERT/DELETE דורש $O(d)$ עדכונים.

פתרון: **המבנה המוצע:** עץ חיפוש בינרי מאוזן (AVL / Red-Black Tree) עם שדה נוסף בכל צומת: מצביע $\text{d-succ}$ לעוקב ה-$d$ שלו. בנוסף, נשמור רשימה מקושרת דו-כיוונית של כל האיברים בסדר ממוין (in-order), כך שלכל צומת יש גם מצביע לעוקב ולקודם ברשימה. **BUILD($S$):** הקלט ממוין. בונים עץ AVL מאוזן ממערך ממוין ב-$\Theta(n)$ (בנייה רקורסיבית: האמצעי הוא השורש, חצי שמאלי תת-עץ שמאלי, חצי ימני תת-עץ ימני). במקביל בונים את הרשימה המקושרת. לכל צומת $i$, ה-$\text{d-succ}$ שלו הוא הצומת ה-$d$ מקומות קדימה ברשימה – ניתן לחשב זאת בסריקה אחת ב-$\Theta(n)$. סה"כ: $\Theta(n)$. **D-SUCCESSOR($S$, $p$):** פשוט מחזירים $p.\text{d-succ}$. זמן: $\Theta(1)$. **INSERT($S$, $k$):** 1. הכנסה רגילה לעץ AVL ב-$\Theta(\lg n)$. 2. מוצאים את העוקב והקודם של $k$ ברשימה (זמינים מהעץ) ומכניסים את $k$ לרשימה. 3. עדכון מצביעי $\text{d-succ}$: יש לעדכן את $\text{d-succ}$ של $d$ הצמתים שלפני $k$ ברשימה, ולקבוע את $\text{d-succ}$ של $k$ עצמו. סה"כ $O(d)$ עדכונים, כשכל עדכון הוא $O(1)$ (הולכים ברשימה). סה"כ: $\Theta(\lg n + d)$. **DELETE($S$, $p$):** 1. מחיקה רגילה מעץ AVL ב-$\Theta(\lg n)$. 2. מסירים את $p$ מהרשימה המקושרת. 3. עדכון מצביעי $\text{d-succ}$: $d$ הצמתים שלפני $p$ ברשימה צריכים עדכון של ה-$\text{d-succ}$ שלהם (כל אחד "מקפיץ" מעבר ל-$p$). סה"כ $O(d)$ עדכונים. סה"כ: $\Theta(\lg n + d)$. **נכונות:** כל הפעולות שומרות על תכונות העץ המאוזן, על הרשימה הממוינת, ועל נכונות מצביעי ה-$\text{d-succ}$.