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

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

רמז: חשבו על שילוב של עץ חיפוש בינארי מאוזן (לניהול לפי מפתח) עם תור (queue) או מבנה נוסף לניהול סדר הכנסה (וותק). לכל מפתח, שמרו רשימה של האיברים עם אותו מפתח לפי סדר הכנסה.

פתרון: **מבנה הנתונים המוצע:** שילוב של עץ AVL (או עץ אדום-שחור) עם תור לכל מפתח. **מבנה:** - עץ חיפוש בינארי מאוזן (AVL) $T$ שבו כל צומת מייצג מפתח ייחודי. - בכל צומת בעץ עם מפתח $k$, מחזיקים תור (מימוש כרשימה מקושרת) $Q_k$ של כל האיברים עם מפתח $k$, לפי סדר הכנסה (הוותיק ביותר בראש התור). - כל איבר מחזיק גם מצביע לצומת בעץ שבו הוא נמצא. **$\text{BUILD}(S)$:** הסדרה ממוינת. בונים עץ AVL מאוזן מהסדרה הממוינת בזמן $O(n)$ (בנייה רקורסיבית: הבחר אמצע כשורש, בנה תת-עצים). עבור מפתחות זהים, כל העותקים נכנסים לתור של אותו צומת. **$\text{DELETE-OLD}(S, k)$:** חפש את $k$ בעץ ה-AVL בזמן $O(\lg n)$. בצומת המתאים, הוצא את האיבר מראש התור $Q_k$ (הוותיק ביותר) בזמן $O(1)$. אם התור התרוקן, מחק את הצומת מהעץ בזמן $O(\lg n)$. סה"כ: $O(\lg n)$. **$\text{INCREASE-KEY}(S, p, d)$:** האיבר $p$ נמצא בתור $Q_k$ של צומת עם מפתח $k$. 1. הסר את $p$ מ-$Q_k$ בזמן $O(1)$ (אם מחזיקים מצביעים דו-כיווניים ברשימה). אם $Q_k$ התרוקן, מחק את הצומת מהעץ: $O(\lg n)$. 2. המפתח החדש הוא $k' = k + d$. חפש את $k'$ בעץ: $O(\lg n)$. אם קיים, הכנס את $p$ לסוף $Q_{k'}$. אם לא קיים, צור צומת חדש עם מפתח $k'$ והכנס לעץ: $O(\lg n)$. סה"כ: $O(\lg n)$.