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

הציעו מבנה-נתונים $N$ של עץ אדום-שחור מורחב אשר מתחזק $n$ מספרים טבעיים ייחודיים ותומך בשגרות הבאות בזמני הריצה המצוינים ליד כל שגרה: - $\text{Insert}(N,k)$: הכנסת המפתח $k$ למבנה $N$, זמן ריצה: $O(\lg n)$ - $\text{Delete}(N,x)$: מחיקת האבר אליו מצביע $x$ מהמבנה $N$, זמן ריצה: $O(\lg n)$ - $\text{Med\_Even}(N)$: החזרת החציון התחתון מבין ערכי המפתחות של הצמתים שגובהם בעץ זוגי. זמן ריצה נדרש: $O(\lg n)$ - $\text{Average\_Even}(N)$: מחזיר את ממוצע ערכי המפתחות של הצמתים שגובהם בעץ זוגי. זמן ריצה: $O(\lg n)$ הדרכה: עליכם להגדיר שדות הרחבה מתאימים לעץ אדום-שחור. יש להראות את קיום תנאי משפט 14.1 אך אין צורך להוכיחו. אין צורך לכתוב פסאודוקוד אך יש לפרט את אופן פעולת השגרות במדויק. נתחו בקצרה נכונות וסיבוכיות.

רמז: הרחב כל צומת בשדות: גובה הצומת, מספר הצמתים עם גובה זוגי בתת-העץ, וסכום המפתחות של צמתים עם גובה זוגי בתת-העץ. עבור $\text{Med\_Even}$ השתמש ברעיון דומה לעץ סדר סטטיסטי.

פתרון: **שדות ההרחבה לכל צומת $x$:** 1. $x.h$ — גובה הצומת (אורך המסלול הארוך ביותר מ-$x$ לעלה). 2. $x.\text{even\_count}$ — מספר הצמתים בתת-העץ של $x$ (כולל $x$) שגובהם זוגי. 3. $x.\text{even\_sum}$ — סכום המפתחות של הצמתים בתת-העץ של $x$ שגובהם זוגי. **חישוב השדות (קיום תנאי משפט 14.1):** כל שדה ניתן לחישוב מ-$x$, $x.left$, $x.right$ בזמן $O(1)$: $$x.h = 1 + \max(x.left.h,\; x.right.h)$$ (עבור $\text{NIL}$: $h = -1$) נגדיר $\mathbb{1}_x = 1$ אם $x.h \mod 2 = 0$, ו-$0$ אחרת. אזי: $$x.\text{even\_count} = x.left.\text{even\_count} + x.right.\text{even\_count} + \mathbb{1}_x$$ $$x.\text{even\_sum} = x.left.\text{even\_sum} + x.right.\text{even\_sum} + \mathbb{1}_x \cdot x.key$$ כל השדות מחושבים בזמן $O(1)$ מנתוני הצומת וילדיו, ולכן תנאי משפט 14.1 מתקיים. בפרט, בעת סיבובים (rotations) ניתן לעדכן את השדות ב-$O(1)$ לכל צומת שמושפע, ולאורך מסלול לשורש ב-$O(\lg n)$. **שימו לב:** בעת סיבוב או שינוי מבני, גובה צמתים עלול להשתנות. אולם כל שינוי מתפשט כלפי מעלה לאורך מסלול בודד לשורש, ולכן עדכון כל השדות לאורך המסלול הוא $O(\lg n)$. --- **פעולת השגרות:** **Insert(N,k) ו-Delete(N,x):** מבצעים הכנסה/מחיקה רגילה בעץ אדום-שחור. לאחר כל שינוי מבני (כולל סיבובים ותיקוני צבעים), מעדכנים את שלושת שדות ההרחבה לאורך המסלול מהצומת שהשתנה ועד השורש. סיבוכיות: $O(\lg n)$. **Average\_Even(N):** $$\text{Average\_Even}(N) = \frac{N.root.\text{even\_sum}}{N.root.\text{even\_count}}$$ סיבוכיות: $O(1)$. **Med\_Even(N):** נרצה למצוא את החציון התחתון מבין המפתחות של צמתים עם גובה זוגי. נגדיר $r = \lceil N.root.\text{even\_count} \;/\; 2 \rceil$ (דרגת החציון התחתון). נמצא את המפתח ה-$r$-י בגודלו מבין צמתים עם גובה זוגי בדומה לחיפוש סדר סטטיסטי: $\text{FindEvenRank}(x, r)$: 1. חשב $\ell = x.left.\text{even\_count}$ (מספר צמתי-גובה-זוגי בתת-העץ השמאלי). 2. חשב $\mathbb{1}_x$ (האם $x$ עצמו בגובה זוגי). 3. אם $r \leq \ell$: חפש רקורסיבית ב-$x.left$ עם דרגה $r$. 4. אחרת אם $r \leq \ell + \mathbb{1}_x$ (ו-$\mathbb{1}_x = 1$): החזר $x.key$. 5. אחרת: חפש רקורסיבית ב-$x.right$ עם דרגה $r - \ell - \mathbb{1}_x$. **נכונות:** מכיוון שהעץ הוא עץ חיפוש בינארי, כל המפתחות בתת-העץ השמאלי קטנים מ-$x.key$ וכל המפתחות בתת-העץ הימני גדולים. לכן ה-$r$-קטן-ביותר מבין צמתי גובה-זוגי נמצא: בשמאל אם $r \leq \ell$, ב-$x$ עצמו אם הוא זוגי והדרגה מתאימה, או בימין אחרת. **סיבוכיות:** בכל שלב יורדים רמה אחת בעץ. עומק העץ $O(\lg n)$, לכן הסיבוכיות $O(\lg n)$.