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

א) (13 נקודות) נתונה ערימת מינימום $A$ בגודל $n$, שמפתחותיה הם מספרים ממשיים. לצורך כלשהו הוספנו לכל המפתחות על גבי המסלול השמאלי את הקבוע $C > 0$. כתוב שגרה לתיקון המבנה $A$ כך שיחזור להיות ערימת מינימום חוקית (באופן שהערימה נשארת עם תוספת ה-$C$ למפתחות המסויימים). על השגרה לעבוד בזמן $O(\log^2 n)$. הערה: "המסלול השמאלי" מוגדר להיות המסלול היוצא מהשורש וממשיך רק שמאלה (אין פניות לבן הימני לאורך כל המסלול). דוגמא: בערימת המינימום שבאיור, המסלול השמאלי הוא המסלול 3-4-10-21. ב) (12 נקודות) נתון עץ חיפוש בינארי $T$ בגודל $n$, שמפתחותיו הם מספרים טבעיים שונים זה מזה. כתבו אלגוריתם למציאת שני צמתים שונים $x, y$ בעץ $T$, המקיימים את התנאי $key[x] + key[y] = 2key[root[T]]$. אם אין שני צמתים המקיימים את התנאי האלגוריתם מחזיר $FALSE$. על השגרה לעבוד בזמן $O(n)$. מותר להקצות $O(1)$ מקום נוסף. אנא דייקו בכתיבת השגרה ואל תסתפקו בכתיבת הרעיון בלבד. אנא דייקו בחישוב היעילות. הערות: * שימו לב לפתור באופן עדין ולהקפיד על סדר הפעולות. * אנא הקפידו על כתיבת רעיון, אלגוריתם, נכונות וסיבוכיות. * כל אחד מהסעיפים עומד בפני עצמו, וניתן לפתרון גם אם לא פתרתם הסעיף האחר.

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

פתרון: ### סעיף א **רעיון:** הוספת קבוע $C>0$ למפתחות על המסלול השמאלי עלולה להפר את **תכונת ערימת המינימום**. הפרה כזו יכולה להתרחש רק בצמתים על המסלול עצמו, מכיוון שרק המפתחות שלהם השתנו. עבור צומת $v$ על המסלול, מפתח בן שמאלי שלו (אם קיים) נמצא גם הוא על המסלול, ולכן לשניהם הוסף $C$. היחס ביניהם נשמר. הבעיה יכולה להיווצר רק בין $v$ לבין בנו הימני (שאינו על המסלול). לכן, יש צורך לתקן את תכונת הערימה עבור כל צומת על המסלול השמאלי. נעשה זאת על ידי קריאה ל-`Min-Heapify` על כל צומת במסלול, מהעלה ועד לשורש, כדי להבטיח שתנאי הקדם של `Min-Heapify` (שהעצים התלויים בבנים הם ערימות חוקיות) מתקיים בכל קריאה. **אלגוריתם:** ``` Fix-Left-Path-Heap(A, C): // Step 1: Find all nodes on the left path and add C to their keys path_nodes = [] i = 1 // Start from root while i <= A.heap_size: A[i] = A[i] + C path_nodes.append(i) i = Left(i) // i = 2*i // Step 2: Fix the heap property from bottom to top along the path for i in reversed(path_nodes): Min-Heapify(A, i) ``` כאשר `Min-Heapify(A, i)` היא הפעולה הסטנדרטית לתיקון ערימה בצומת `i`. **נכונות:** לאחר הוספת $C$ למפתחות במסלול השמאלי, תכונת ערימת המינימום עלולה להיות מופרת רק בצמתים $v$ הנמצאים על המסלול. בפרט, ייתכן ש-$key[v]$ יהיה גדול מ-$key[right(v)]$. האלגוריתם עובר על צמתי המסלול מהעמוק ביותר (העלה) כלפי מעלה (השורש). נוכיח באינדוקציה הפוכה על עומק הצמתים במסלול, שלאחר הפעלת `Min-Heapify(A, v)`, תת-העץ המושרש ב-$v$ הוא ערימת מינימום חוקית. * **בסיס:** יהי $v_k$ הצומת העמוק ביותר על המסלול. בניו (אם קיימים) אינם על המסלול ולכן תתי-העצים שלהם הם ערימות מינימום חוקיות. לכן, תנאי הקדם של `Min-Heapify(A, v_k)` מתקיים, ולאחר ביצוע הפעולה, תת-העץ המושרש ב-$v_k$ הוא ערימת מינימום חוקית. * **צעד:** נניח שהטענה נכונה עבור כל צומת $v_j$ על המסלול שעומקו גדול מזה של $v_i$. כאשר אנו מפעילים `Min-Heapify(A, v_i)`, תת-העץ המושרש בבנו הימני הוא ערימה חוקית (כי הוא לא השתנה), ותת-העץ המושרש בבנו השמאלי, $v_{i+1}$, הוא ערימה חוקית לפי הנחת האינדוקציה. לכן, תנאי הקדם מתקיימים, והפעולה תהפוך את תת-העץ המושרש ב-$v_i$ לערימת מינימום חוקית. כאשר הלולאה מסתיימת עם השורש ($v_0$), כל העץ הוא ערימת מינימום חוקית. $\blacksquare$ **סיבוכיות:** * אורך המסלול השמאלי הוא $O(\log n)$. מציאת הצמתים והוספת $C$ למפתחותיהם לוקחת $O(\log n)$ זמן. * הלולאה השנייה רצה $O(\log n)$ פעמים. בכל איטרציה, עבור צומת $v_i$ בעומק $i$, אנו מפעילים `Min-Heapify` שזמן ריצתו הוא פרופורציונלי לגובה תת-העץ שלו, כלומר $O(\log n - i)$. * הזמן הכולל הוא סכום זמני הריצה של `Min-Heapify` על כל צמתי המסלול: $T(n) = \sum_{i=0}^{\lfloor \log_2 n \rfloor} O(\log n - i) = O(\sum_{j=0}^{\lfloor \log_2 n \rfloor} j) = O(\log^2 n)$. הסיבוכיות הכוללת היא $O(\log^2 n)$. ### סעיף ב **רעיון:** המטרה היא $2 \cdot key[root]$. **סריקה פנימית** (in-order) של **עץ חיפוש בינארי** מניבה את המפתחות בסדר ממוין, ולכן הבעיה שקולה למציאת זוג איברים בסדרה ממוינת שסכומם שווה לערך קבוע. נשתמש ב**גישת שני המצביעים**: מצביע $x$ מתחיל מהאיבר הקטן ביותר ומצביע $y$ מהאיבר הגדול ביותר. בכל צעד בודקים את הסכום $key[x] + key[y]$: אם הוא קטן מהמטרה מקדמים את $x$ לעוקבו (successor), ואם הוא גדול ממנה מחזירים את $y$ לקודמו (predecessor). כדי לעמוד בדרישת **$O(1)$ מקום נוסף** איננו משתמשים במחסניות. בעץ חיפוש בינארי סטנדרטי (כפי שמוגדר בספר הקורס) לכל צומת יש מצביע אב $p$, ולכן ניתן לממש את `TREE-SUCCESSOR` ו-`TREE-PREDECESSOR` תוך שימוש ב-$O(1)$ מקום בלבד, ללא מבני עזר. הערה מבנית: היות שהמטרה היא $2 \cdot key[root]$, השורש מחלק את העץ — כל המפתחות בתת-העץ השמאלי קטנים מ-$key[root]$ וכל המפתחות בתת-העץ הימני גדולים ממנו. לכן כל זוג חוקי מורכב בהכרח מצומת אחד מכל צד (שני צמתים מצד שמאל יתנו סכום הקטן מהמטרה, ושניים מימין — גדול ממנה), ובפרט אף אחד מהשניים אינו השורש (שכן בן-הזוג שלו היה צריך להיות בעל מפתח $key[root]$, וזה בלתי אפשרי שכן המפתחות שונים זה מזה). **אלגוריתם:** ``` FIND-SUM-PAIR(T): if T.root == NIL: return FALSE target = 2 * T.root.key x = TREE-MINIMUM(T.root) // הצומת בעל המפתח הקטן ביותר y = TREE-MAXIMUM(T.root) // הצומת בעל המפתח הגדול ביותר while x != y and x.key < y.key: s = x.key + y.key if s == target: return (x, y) else if s < target: x = TREE-SUCCESSOR(x) // מגדילים את הקצה הקטן else: y = TREE-PREDECESSOR(y) // מקטינים את הקצה הגדול return FALSE ``` **נכונות:** המצביע $x$ מצביע תמיד על המפתח הקטן ביותר שטרם נשלל, ו-$y$ על הגדול ביותר שטרם נשלל. נסמן $v_x = x.key$ ו-$v_y = y.key$. * אם $v_x + v_y = target$ — מצאנו זוג. מאחר שהמצביעים טרם נפגשו, $x \ne y$. * אם $v_x + v_y < target$ — יש להגדיל את הסכום. הגדלת $v_y$ אינה אפשרית כי הוא הגדול ביותר שנותר, ולכן חובה להגדיל את $v_x$, כלומר לעבור לעוקב של $x$. כל זוג אחר הכולל את $v_x$ ייתן סכום קטן עוד יותר, ולכן ניתן לפסול את $x$ לצמיתות. * אם $v_x + v_y > target$ — באופן סימטרי, חובה להחליף את $y$ בקודמו. מאחר שהמפתחות שונים זה מזה, מתקיים $x.key < y.key$ אם ורק אם $x$ קודם ל-$y$ בסדר הממוין. לכן תנאי העצירה מבטיח שלא נשתמש באותו צומת פעמיים, ושכל הזוגות הרלוונטיים נבדקים. אם המצביעים נפגשים מבלי שנמצא זוג — זוג כזה אינו קיים, והאלגוריתם מחזיר $FALSE$. $\blacksquare$ **סיבוכיות:** * **מקום:** האלגוריתם משתמש במספר קבוע של מצביעים ומשתנים ($x, y, s, target$) בלבד. מצביעי האב הם חלק ממבנה העץ הקיים ואינם הקצאה נוספת. לכן סיבוכיות המקום היא $O(1)$, כנדרש. * **זמן:** `TREE-MINIMUM` ו-`TREE-MAXIMUM` עולים $O(h)$. בלולאה, $x$ מתקדם אך ורק קדימה (דרך `TREE-SUCCESSOR`) ו-$y$ אך ורק אחורה (דרך `TREE-PREDECESSOR`). סדרה של קריאות `TREE-SUCCESSOR` החל מהמינימום עוברת על כל קשת בעץ לכל היותר פעמיים, ולכן עלותה הכוללת היא $O(n)$ (תרגיל 12.2-7 בספר), וכך גם עבור `TREE-PREDECESSOR` החל מהמקסימום. סך כל הקריאות חסום ב-$O(n)$, ומכאן שזמן הריצה הכולל הוא $O(n)$, כנדרש.