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

נתון עץ ערכי מיקום $T$ אשר כל צומת בו מכיל מספר ממשי (המפתח). העץ היה נתון למתקפת סייבר של יריב זדוני, ויתכן שהוחלפו בו ערכי $size$ של הצמתים השונים, אך לא היו שינויים מעבר לכך. כתבו שגרה ליניארית הבודקת אם העץ הוא עדיין עץ ערכי מיקום תקני.

רמז: בצעו סריקה בסדר postorder ובדקו לכל צומת שמתקיים $size(v) = size(left(v)) + size(right(v)) + 1$. אל תשכחו לטפל בעלים (nil) — ערך ה-$size$ שלהם צריך להיות 0.

פתרון: **רעיון:** נבדוק את ערכי $size$ תוך כדי סריקת PostOrder. **אלגוריתם:** ``` 1. נסרוק את T בסדר postorder, כאשר בכל ביקור בצומת v נבצע: אם v = T[nil] וגם v.size ≠ 0: החזר FALSE אחרת אם size(V) ≠ size(left(V)) + size(right(V)) + 1: החזר FALSE החזר TRUE ``` **נכונות:** $size$ מוגדר על פי בניו של הצומת, ולכן בסריקת postorder (שבה מבקרים בבנים לפני האב) ניתן לבדוק את תיקותו של כל צומת. **סיבוכיות:** $\Theta(n)$. סריקת עץ היא ליניארית — כל צומת נבדק פעם אחת בזמן $O(1)$.