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

נגדיר את המבנה של **עץ בינרי אוגר** – עץ בינרי המכיל בכל צומת $z$ שדה אוגר $add[z]$ (בנוסף למפתח כמובן). בהינתן עץ בינרי אוגר $A$, ניתן לבנות ממנו עץ בינרי רגיל $T$: עבור כל צומת $z$ ב-$A$, מחברים את הערך $add[z]$ לכל המפתחות בתת-העץ המושרש ב-$z$; נאמר ש-$A$ מייצג את $T$. כתבו אלגוריתם הרץ בזמן $O(n)$, המבדק אם עץ הבינרי האוגר $A$ מייצג עץ חיפוש בינרי.

רמז: בצעו מעבר inorder על העץ. עקבו אחרי סכום מצטבר של ערכי $add$ מהשורש לצומת הנוכחי. המפתח האמיתי של כל צומת הוא $key[z]$ + סכום ה-$add$ בנתיב מהשורש אליו. בדקו שהמפתחות האמיתיים בסדר עולה.

פתרון: **הרעיון:** נבצע מעבר inorder, כאשר בכל צומת נחשב את המפתח האמיתי (key + סכום ה-add מהשורש). נבדוק שהמפתחות האמיתיים עולים. ``` IS-BST(A): prev = -∞ return CHECK(root[A], 0) CHECK(z, cumulative_add): if z == NIL: return TRUE cumulative_add = cumulative_add + add[z] // בדיקת תת-עץ שמאלי if not CHECK(left[z], cumulative_add): return FALSE // בדיקת הצומת הנוכחי real_key = key[z] + cumulative_add if real_key ≤ prev: return FALSE prev = real_key // בדיקת תת-עץ ימני return CHECK(right[z], cumulative_add) ``` **הערה:** `prev` הוא משתנה גלובלי. **סיבוכיות:** מעבר inorder מבקר כל צומת בדיוק פעם אחת, ובכל צומת מבצע $O(1)$ עבודה. סה"כ $O(n)$.