שאלת מבחן במבני נתונים ומבוא לאלגוריתמים - האוניברסיטה הפתוחה 2025 - תכנון מבנה נתונים

שאלה מותאמת לסמסטר הלימוד שאלה 5 (25 נקודות) – שאלה על החומר המלא ללא מיקוד. תכננו מבנה $S$, שהוא עץ א"ש מורחב, שמפתחותיו הם מספרים טבעיים, ושניתן לבצע עליו את הפעולות הבאות: $BUILD(S, A)$: בניית $S$ ממערך ממוין $A$ בגודל $n$, בזמן ריצה $O(n)$. $INSERT(S, k)$: מכניס את המפתח $k$ למבנה. זמן הריצה $O(\log n)$. $HEAVIEST-PATH(S)$: החזרת סכום מפתחותיו של המסלול הפשוט הכבד ביותר שמתחיל בשורש ומסתיים בעלה, בזמן ריצה $O(1)$. (מסלול פשוט = מסלול שאינו עובר באף צומת יותר מפעם אחת). דוגמא: בעץ זה, המסלול הכבד ביותר המתחיל בשורש הוא המסלול 5-2-4-3, וסכום מפתחותיו הוא 14. (הצמתים השחורים בעץ שחורים באיור והצמתים האדומים בעץ אפורים באיור) א) (9 נקודות) כאמור נרצה להשתמש בעץ אדום שחור מורחב על מנת לפתור את הבעיה. באיזה שדה הרחבה תשתמשו בכל צומת ומהי משמעותו. אם יש מבנים ומשתני עזר נוספים - מהי משמעותם ואיך הם מאותחלים? ב) (3 נקודות) הראו שהשדה המרחיב עומד בתנאי 14.1. ג) (4 נקודות) כתבו את שגרת $HEAVIEST-PATH(S)$. ד) (9 נקודות) כתבו את שגרת $BUILD(S, A)$. יש לפרט כיצד מאותחלים שדות מרחיבים. הערות: * המבנה צריך להיות כזה שמאפשר את כל הפעולות המפורטות ביעילות הנדרשת, אך אין צורך לממש פעולות שלא נדרשתם לממש.

רמז: כדי למצוא את המסלול הכבד ביותר מהשורש ב-$O(1)$, יש לאגור את המידע הרלוונטי בשורש עצמו. חשבו איזה מידע כל צומת צריך לשמור על תת-העץ שלו כדי שניתן יהיה לחשב את המידע עבור אביו.

פתרון: א) **שדה ההרחבה ומשמעותו** נרחיב כל צומת `x` בעץ בשדה נוסף, **`x.heaviest`**. **משמעות השדה**: `x.heaviest` יכיל את סכום המפתחות של **המסלול הפשוט הכבד ביותר** (כלומר, בעל סכום המפתחות המקסימלי) שמתחיל בצומת `x` ומסתיים באחד מהעלים בתת-העץ המושרש ב-`x`. **אתחול ומשתני עזר**: כחלק ממבנה עץ אדום-שחור, קיים צומת זקיף `T.nil`. נאתחל את השדה המרחיב שלו לערך בסיס: `T.nil.heaviest = 0`. אתחול זה מבטיח שכאשר צומת `x` הוא עלה (שילדיו הם `T.nil`), המסלול הכבד ביותר ממנו לעלה (הוא עצמו) יהיה פשוט המפתח שלו, כיוון שההמשך דרך ילדיו הפיקטיביים יוסיף 0 לסכום. ב) **הוכחה שהשדה המרחיב עומד בתנאי 14.1** תנאי 14.1 (מתוך הספר "מבוא לאלגוריתמים" של קורמן וחבריו) דורש שניתן יהיה לחשב את ערך השדה המרחיב בצומת `x` אך ורק על סמך מידע המצוי בצומת `x` עצמו ובשדות המרחיבים של ילדיו. השדה `x.heaviest` מקיים תנאי זה, מכיוון שניתן לחשבו באמצעות הנוסחה הרקורסיבית הבאה: $x.heaviest = x.key + \max(x.left.heaviest, x.right.heaviest)$ הנוסחה משתמשת רק ב-`x.key` (שדה של `x` עצמו), `x.left.heaviest` (השדה המרחיב של הילד השמאלי), ו-`x.right.heaviest` (השדה המרחיב של הילד הימני). לכן, התנאי מתקיים. תכונה זו מאפשרת לתחזק את השדה ביעילות בזמן פעולות המשנות את מבנה העץ (הכנסה, מחיקה וסיבובים) על ידי עדכון ערכי השדה במסלול מהצומת שהשתנה כלפי מעלה אל השורש.$\blacksquare$ ג) **שגרת HEAVIEST-PATH(S)** הפעולה `HEAVIEST-PATH(S)` צריכה להחזיר את סכום המסלול הכבד ביותר מהשורש לעלה. לפי הגדרת השדה המרחיב שלנו, ערך זה שמור בשדה `heaviest` של שורש העץ, `S.root`. **פסאודו-קוד:** ``` HEAVIEST-PATH(S) return S.root.heaviest ``` מאחר שזוהי גישה ישירה לשדה אחד בשורש, זמן הריצה הוא $O(1)$. ד) **שגרת BUILD(S, A)** כדי לבנות את העץ ממערך ממוין $A$ בזמן ריצה $O(n)$, נשתמש בגישה רקורסיבית הבונה **עץ חיפוש בינארי מאוזן לחלוטין**. בכל שלב, ניקח את האיבר האמצעי בתת-המערך הנוכחי בתור שורש תת-העץ, ונבנה רקורסיבית את תתי-העצים השמאלי והימני מהחצאים המתאימים של המערך. במהלך החזרה מהרקורסיה (סריקת post-order), נאתחל את השדות המרחיבים ונצבע כל צומת בשחור. עץ חיפוש בינארי מלא שכל צמתיו שחורים מקיים את כל חמש תכונות עץ אדום-שחור. **פסאודו-קוד:** ``` BUILD(S, A) n = A.length S.root = BUILD-RECURSIVE(A, 1, n) BUILD-RECURSIVE(A, i, j) if i > j return T.nil mid = floor((i+j)/2) x = new Node(A[mid]) x.left = BUILD-RECURSIVE(A, i, mid - 1) x.right = BUILD-RECURSIVE(A, mid + 1, j) // עדכון השדה המרחיב x.heaviest = x.key + max(x.left.heaviest, x.right.heaviest) // קביעת צבע x.color = BLACK return x ``` **ניתוח זמן ריצה**: הפונקציה `BUILD-RECURSIVE` מבקרת בכל איבר במערך $A$ בדיוק פעם אחת כדי ליצור עבורו צומת. כל קריאה, ללא הקריאות הרקורסיביות, לוקחת זמן $O(1)$. לכן, נוסחת הנסיגה לזמן הריצה היא $T(n) = 2T(n/2) + O(1)$, ופתרונה, על פי משפט האב, הוא $T(n) = O(n)$.$\blacksquare$