מבני נתונים ומבוא לאלגוריתמים - עצי חיפוש

• Init(D) - אתחול מבנה ריק. זמן: $O(1)$
• Insert(D, x) - הכנסת איבר $x$ למבנה. זמן: $O(\log n)$
• Delete(D, x) - מחיקת איבר $x$ מהמבנה (נתון מצביע לצומת למחיקה). זמן: $O(\log n)$
• Min-Gap(D) - החזרת ההפרש המינימלי בין שני מספרים סמוכים בגודלם הקיימים כרגע במבנה. לדוגמה: אם המבנה מכיל $\{1,5,9,20\}$, ההפרש המינימלי הוא 4 (בין 1 ל-5 או בין 5 ל-9). זמן ריצה נדרש: $O(1)$ במקרה הגרוע.

• פרטו באילו מבני נתונים אתם משתמשים (ייתכן שצריך יותר מאחד).
• הסבירו כיצד ממומשת כל פעולה, ובפרט כיצד נשמר המידע המאפשר לענות על Min-Gap בזמן קבוע.
• שימו לב: ההכנסות והמחיקות צריכות לעדכן את ה-Min-Gap בהתאם.

• שימו לב לפתור באופן עדין ולהקפיד על סדר הפעולות.
• אנא הקפידו על כתיבת רעיון, אלגוריתם, נכונות וסיבוכיות.
• בשאלה זו (בשלושת הסעיפים) מספיק הסבר נכונות אינטואיטיבי וקצר.
• כל אחד מהסעיפים עומד בפני עצמו, וניתן לפתרון גם אם לא פתרתם הסעיף האחר.

5 7 3 1 1 5 5 3 1 3 3 2 4

1 2 3 4 5 7 1 3 5 1 3 5 3

5 7 3 1 1 5 5 3 1 3 3 2 4

3 3 3 3 1 1 1 5 5 5 2 4 7

• בשאלות אלגוריתמיות יש להקפיד על כתיבת רעיון, אלגוריתם, נכונות וסיבוכיות.
• אלגוריתם = שגרה = סדרת פקודות מוגדרות היטב בעברית או באנגלית.
• שימו לב לדייק בנכונות ובחישוב היעילות.
• כל אחד מהסעיפים עומד בפני עצמו, וניתן לפתרון גם אם לא פתרתם הסעיף האחר.

• המבנה צריך להיות כזה שמאפשר את כל הפעולות המפורטות ביעילות הנדרשת, אך אין צורך לכתוב את כל השגרות, אלא רק את השגרות שהתבקשתם.

• בשאלות אלגוריתמיות אנא הקפידו על כתיבת רעיון, אלגוריתם, נכונות וסיבוכיות.
• כל אחד מהסעיפים עומד בפני עצמו, וניתן לפתרון גם אם לא פתרתם הסעיף האחר.

• המבנה צריך להיות כזה שמאפשר את כל הפעולות המפורטות ביעילות הנדרשת, אך אין צורך לכתוב את כל השגרות, אלא רק את השגרות שהתבקשתם.

• המבנה צריך להיות כזה שמאפשר את כל הפעולות המפורטות ביעילות הנדרשת, אך אין צורך לכתוב את כל השגרות, אלא רק את השגרות שהתבקשתם.

• שימו לב לפתור באופן עדין ולהקפיד על סדר הפעולות.
• אנא הקפידו על כתיבת רעיון, אלגוריתם, נכונות וסיבוכיות.
• כל אחד מהסעיפים עומד בפני עצמו, וניתן לפתרון גם אם לא פתרתם הסעיף האחר.