שאלה על החומר המלא ללא מיקוד.
האוניברסיטה הפתוחה התחילה בתוכנית מלגות חדשה, שבה נמצאים n סטודנטים.
לכל סטודנט בתוכנית ידועה הכנסתו החודשית, והמלגה הראשונית שהוא מקבל.
ההכנסה החודשית היא מספר ייחודי (אין שני סטודנטים עם אותה הכנסה חודשית).
הציעו מבנה נתונים S התומך בפעולות הבאות בזמני הריצה המצוינים:
INSERT(salary,amount): הכנסת סטודנט חדש שהכנסתו החודשית היא salary, ושערך המלגה הנוכחית שהאוניברסיטה מעניקה לו היא amount, בזמן O(logn).
INCREASE−AMOUNT(salary,increase): הוספת הסכום החיובי increase למלגת כל סטודנט שהכנסתו החודשית קטנה או שווה ל-salary ונמצא במבנה, בזמן O(logn). תוכלו להניח שקיים במבנה סטודנט שהכנסתו החודשית היא salary.
ASSESS−AMOUNT(salary): החזרת המלגה הכוללת לסטודנט שהכנסתו החודשית היא salary, בזמן O(logn). תוכלו להניח שקיים במבנה סטודנט שהכנסתו היא salary.
כדי לפתור את הבעיה נחזיק עץ אדום-שחור T עם n איברים. כל צומת V מייצג סטודנט, ומכיל:
V.salary: הכנסתו החודשית של הסטודנט, שהיא ייחודית וגם מפתח העץ.
V.amount: המלגה הראשונית שהסטודנט מקבל.
V.increase: תוספת מלגה לכל האיברים בתת העץ השמאלי של V. לא כולל V עצמו.
א) (5 נקודות) קבעו האם השדה V.increase עומד בתנאי 14.1. אם כן כתבו נוסחא.
ב) (10 נקודות) הראו שהשדה V.increase ניתן לתחזוק תוך שמירה על הזמנים הנדרשים.
ג) (10 נקודות) כתבו את שגרת INCREASE−AMOUNT(salary,increase).
דוגמא: שחר נמצא בתוכנית המלגות, עם הכנסה חודשית 52 ₪, ומלגה ראשונית 600 ₪.
נבצע INCREASE−AMOUNT(60,1000) ואז INCREASE−AMOUNT(75,100).
כעת ASSESS−AMOUNT(52) יחזיר 1700 ₪ (כי הכנסתו של שחר קטנה מ-60 ₪, ומ-75 ₪).
כעת נכניס את דניאל לתוכנית. הכנסתה החודשית של דניאל היא 59 ש"ח, והמלגה הראשונית שהיא מקבלת היא 1200 ₪. כעת ASSESS−AMOUNT(59) יחזיר 1200 ₪.
הערות:
המבנה צריך להיות כזה שמאפשר את כל הפעולות המפורטות ביעילות הנדרשת, אך אין צורך לכתוב את כל השגרות, אלא רק את השגרות שהתבקשתם.