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

השאלה מיועדת רק לסטודנטים שלמדו בסמסטר 2025א הציעו מבנה נתונים $S$ אשר מייצג פריטי לבוש בחנות בגדי-מנמ"א, ושבאמצעותו ניתן לבצע את הפעולות הבאות עם זמני הריצה המצויים ליד כל שגרה. פריט לבוש מיוצג ע"י רשומה המכילה שני שדות: ברקוד (`Barcode`) - סדרה ייחודית של 8 ספרות בבסיס 10, ומחיר (`Price`) - מספר ממשי. `BUILD(S, A)` : בניית $S$ מתוך מערך לא ממוין בגודל $n$, בזמן $O(n)$. `INSERT(S, z)` : הכנסת פריט הלבוש $z$ למבנה $S$, בזמן $O(\log n)$. `SEARCH(S, Barcode)` : חיפוש איבר עם הברקוד `Barcode` במבנה $S$ בזמן $O(\log n)$. `DELETE(S, z)` : מחיקת הפריט שאליו מצביע $z$ מהמבנה $S$, בזמן $O(\log n)$. `MAX(S, Barcode1, Barcode2)` : החזרת המחיר היקר ביותר לפריט מבין כל הפריטים שהברקוד שלהם הוא בטווח $[Barcode1 \dots Barcode2]$, בזמן $O(\log n)$. תוכלו להניח שפריטים עם הברקודים $Barcode1, Barcode2$ קיימים ב-$S$. `SALE(S, NewSale, ItemPrice)` : ביטול כל מבצע קודם, ועדכון מבצע חדש של הורדת `NewSale` ₪ מכל פריט שמחירו יקר יותר מ-`ItemPrice` ₪, בזמן $O(1)$. א) (9 נקודות) נרצה להשתמש בעץ אדום שחור מורחב על מנת לפתור את הבעיה. תארו מהם מפתחות העץ, באיזה שדה הרחבה תשתמשו בכל צומת ומהו משמעותו. אם יש משתני עזר- איך הם מאותחלים? מומלץ לשרטט. ב) (8 נקודות) הראו באמצעות נוסחא שהשדה המרחיב עומד בתנאי 14.1. ג) (8 נקודות) כתבו את שגרת `BUILD(S, A)`. ניתן להשתמש במערך עזר בגודל $O(n)$. יש לפרט איך מאתחלים שדות מרחיבים.

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

פתרון: ### סעיף א' נשתמש בעץ אדום-שחור מורחב. להלן תיאור המבנה: * **מפתחות העץ:** המפתחות שעל פיהם העץ ממוין הם הערכים של שדה ה-**`Barcode`**. כלומר, העץ מאורגן לפי סדר הברקודים. * **שדה הרחבה:** כל צומת `x` בעץ יורחב ויכיל שדה נוסף בשם `x.max_price`. * **משמעות השדה:** השדה `x.max_price` יכיל את המחיר הגבוה ביותר מבין כל הפריטים בתת-העץ המושרש ב-`x`. ערך זה מתייחס למחיר המקורי המאוחסן בצמתים (`Price`), ואינו משקף בהכרח את המחיר לאחר מבצע. עדכון שדה זה יתבצע בעת הכנסה, מחיקה וסיבובים בעץ. * **משתני עזר:** נשתמש בשני משתני עזר גלובליים למבנה הנתונים כולו, אשר יאפשרו את פעולת ה-`SALE` ב-$O(1)$: 1. `GlobalSaleAmount`: ישמור את סכום ההנחה של המבצע הנוכחי (`NewSale`). יאותחל ל-0. 2. `GlobalSaleThreshold`: ישמור את סף המחיר של המבצע (`ItemPrice`). יאותחל לערך שמבטיח שאף פריט אינו עומד בתנאי (למשל, אינסוף חיובי). כאשר תתבצע קריאה ל-`SALE(S, NewSale, ItemPrice)`, שני משתני עזר אלו יתעדכנו לערכים החדשים. המחיר **האמיתי** של פריט כלשהו יחושב בזמן ריצה (למשל, בפעולת `MAX`) על ידי בדיקת מחירו המאוחסן מול משתני העזר הגלובליים. להלן איור סכמטי של צומת בעץ: ``` +---------------------------+ | x.key | (Barcode) +---------------------------+ | x.price | | x.color | | x.p | | x.left | | x.right | +---------------------------+ | x.max_price | (Augmented Field) +---------------------------+ ``` ### סעיף ב' תכונה 14.1 (מתבססת על הספר CLRS) קובעת כי ערך השדה המרחיב בצומת `x` חייב להיות ניתן לחישוב על סמך המידע המצוי בצומת `x` עצמו ובשני ילדיו, `x.left` ו-`x.right`. עבור השדה `x.max_price` שהגדרנו, ניתן לחשב את ערכו באמצעות הנוסחה הבאה: $x.max\_price = \max(x.Price, x.left.max\_price, x.right.max\_price)$ כאשר מוסכם שעבור צומתי `NIL` (עלי העץ), `NIL.max_price = -\infty`. נוסחה זו תלויה אך ורק במחיר של הצומת `x` עצמו ובערכי השדה המרחיב של ילדיו. לכן, תנאי 14.1 מתקיים. תכונה זו מבטיחה שניתן לתחזק את השדה המרחיב ביעילות בזמן פעולות המשנות את מבנה העץ (הכנסה, מחיקה וסיבובים) על ידי עדכון ערכי `max_price` של הצמתים המושפעים מלמטה למעלה, מבלי להוסיף לסיבוכיות האסימפטוטית של הפעולות. $\blacksquare$ ### סעיף ג' ניתן לבנות את מבנה הנתונים `S` מהמערך `A` בגודל `n` בזמן $O(n)$ באופן הבא: **`BUILD(S, A)`** 1. **מיון המערך (Sort):** תחילה, נמיין את המערך `A` על פי שדה ה-`Barcode`. מכיוון שערכי הברקוד הם מספרים שלמים בני 8 ספרות, כלומר בטווח ידוע ומוגבל, ניתן להשתמש ב**מיון ספירה (Radix Sort)**. מיון ספירה על מספרים שלמים עם מספר קבוע של ספרות (`d=8`) פועל בזמן ריצה של $O(d \cdot (n+k))$, כאשר $k$ הוא בסיס הספירה (10). מאחר ש-`d` ו-`k` הם קבועים, הסיבוכיות הכוללת של המיון היא $O(n)$. 2. **בניית עץ מאוזן (Build Balanced Tree):** לאחר שהמערך ממוין, נבנה ממנו עץ חיפוש בינארי מאוזן באופן מושלם. ניתן לעשות זאת באמצעות פונקציה רקורסיבית `BuildFromSorted(A, start, end)`: a. מוצאים את אינדקס האמצע: `mid = floor((start + end) / 2)`. b. האיבר `A[mid]` יהיה שורש תת-העץ הנוכחי. c. תת-העץ השמאלי של השורש ייבנה על ידי קריאה רקורסיבית `BuildFromSorted(A, start, mid - 1)`. d. תת-העץ הימני של השורש ייבנה על ידי קריאה רקורסיבית `BuildFromSorted(A, mid + 1, end)`. e. **איתחול שדות מרחיבים:** לאחר שהקריאות הרקורסיביות לבניית תתי-העצים חוזרות, נאחל את השדה `max_price` של צומת האב `A[mid]` לפי הנוסחה מסעיף ב'. הסיבוכיות של בניית עץ מאוזן ממערך ממוין, כולל איתחול השדות המרחיבים, היא $O(n)$. 3. **צביעת העץ (Coloring):** העץ שנבנה בשלב 2 הוא מאוזן גבהים. כדי להפכו לעץ אדום-שחור חוקי, ניתן פשוט לצבוע את **כל** הצמתים בעץ בצבע **שחור**. עץ בינארי מאוזן שכל צמתיו שחורים מקיים את כל תכונות עץ אדום-שחור (בפרט, תכונת הגובה השחור ותכונת האדום). שלב זה דורש מעבר על כל הצמתים ולכן לוקח $O(n)$. הסיבוכיות הכוללת של `BUILD` היא סכום סיבוכיות השלבים, $O(n) + O(n) + O(n) = O(n)$.