הרצאה 7 — עצי חיפוש בינאריים (BST)

1. המוטיבציה — Sequence ADT וה-"wish list"

בהרצאות הקודמות התחלנו עם מבני נתונים ל-ADTs פשוטים (sequence, stack, queue, priority queue), ניתחנו סיבוכיות, ולמדנו על אלגוריתמי מיון. עכשיו חוזרים ל-Sequence ADT עם תקווה לפעולות יעילות יותר.

סיבוכיות זמן — Array & Linked List

מה נשיג עם BST

2. הגדרה רקורסיבית: עץ, עץ בינארי, BST

3. תכונת ה-BST ועומק העץ

עומק BST

• עומק מקסימלי: \(O(n)\) — כשהעץ "מנוון" (chain).
• עומק מינימלי: \(\Omega(\log n)\) — עץ מאוזן.

4. מימוש BST (עם מצביעי הורה)

כל צומת מכיל:

• Key — המפתח.
• Data — מטען נוסף.
• L, R — מצביעים לבנים.
• P — מצביע להורה (Parent). שימושי לפעולות כמו Successor, Insert, Delete.

נשמור גם מצביע T לשורש העץ.

5. Find — חיפוש מפתח

מימוש רקורסיבי

Find(T, x):
case
  T = null  : return null
  T.key = x : return T
  T.key > x : return Find(T.left, x)
  T.key < x : return Find(T.right, x)

מימוש לא-רקורסיבי

Find(T, x):
while T ≠ null and T.key ≠ x:
  if x < T.key: T = T.left
  else:         T = T.right
return T

6. FindMin / FindMax

FindMin: ירידה רצופה שמאלה עד לצומת ללא בן שמאל.

FindMin(T):
if T.left = null then return T
else return FindMin(T.left)

// או לולאה:
FindMin(T):
while T.left ≠ null do T = T.left
return T

FindMax: סימטרי — ירידה רצופה ימינה.

7. היכן בעץ נמצאים האיברים הקטנים/גדולים מ-\(x\)?

איברים קטנים מ-\(x\)

• כל הצמתים בתת-העץ השמאלי של \(x\) (אם קיים).
• כל אבוֹת (ancestors) \(y\) של \(x\) כך ש-\(x\) בתת-העץ הימני של \(y\), וגם כל הצמתים בתת-העץ השמאלי של \(y\).

איברים גדולים מ-\(x\)

• כל הצמתים בתת-העץ הימני של \(x\) (אם קיים).
• כל אבוֹת \(y\) של \(x\) כך ש-\(x\) בתת-העץ השמאלי של \(y\), וגם כל הצמתים בתת-העץ הימני של \(y\).

8. Successor & Predecessor

Tree-Successor(x):
if x.right ≠ null then
    return FindMin(x.right)
else
    y ← x.parent
    while y ≠ null and x = y.right:
        x ← y
        y ← y.parent
    return y

Predecessor: סימטרי — חפש max בתת-עץ שמאלי, אחרת עלה עד שמגיעים מבן שמאלי.

9. Insert — הכנסה

Tree-Insert(T, z):
y ← null      // prev node
x ← T         // current node
While x ≠ null:
  y ← x
  if z.key < x.key
    then x ← x.left
    else x ← x.right
z.parent ← y
if y = null
  then T ← z
  elseif z.key < y.key
    then y.left ← z
    else y.right ← z

10. Delete — מחיקה (3 מקרים)

שלושת המקרים

1. ל-\(v\) אין בנים: מצביע אליו → null. דוגמה: Delete(5) — סתם מנקים.
2. ל-\(v\) בן אחד: מחליפים את המצביע ל-\(v\) במצביע לבן שלו. דוגמה: Delete(24) → הבן 11 תופס את מקומו.
3. ל-\(v\) שני בנים: מעתיקים את Successor (= ה-minimum בתת-עץ הימני) ל-\(v\), ואז מוחקים את ה-Successor רקורסיבית. ה-Successor לעולם אין לו בן שמאלי, ולכן ה-מחיקה הרקורסיבית נופלת למקרה 1 או 2.

Tree-Delete(T, z):
1  if z.left = null or z.right = null
2     then y ← z
3     else y ← Tree-Successor(z)
4  if y.left ≠ null
5     then x ← y.left
6     else x ← y.right
7  if x ≠ null
8     x.parent ← y.parent
9  if y.parent = null
10    then T.root ← x
11    else if y = (y.parent).left
12       then (y.parent).left  ← x
13       else (y.parent).right ← x
14 if y ≠ z
15    then z.key ← y.key   // also copy all data fields
16 return y

סמלים: \(y\) — הצומת שבאמת נמחק; \(x\) — בנו היחיד של \(y\) (או null).

11. Join & Split

Join(T₁, x, T₂)

סיבוכיות: O(1).

Split(T, x)

אלגוריתם:

1. סרוק את המסלול מ-root ל-\(x\).
2. חבר את תת-העץ השמאלי של \(x\) עם כל העצים משמאל למסלול → \(T_1\).
3. חבר את תת-העץ הימני של \(x\) עם כל העצים מימין למסלול → \(T_2\).

סיבוכיות: O(h).

12. מעבר על עצים: Preorder, Inorder, Postorder

שלושה מעברים נפוצים, מוגדרים רקורסיבית:

1. Preorder (DLR): צומת, אז ילדים (שמאל קודם).
2. Inorder (LDR): בן שמאל, צומת, בן ימין.
3. Postorder (LRD): ילדים, אז צומת.

Inorder — אלגוריתם ודוגמה

inorder-tree-walk(T):
if T ≠ null then
  inorder-tree-walk(T.left)
  print T.key
  inorder-tree-walk(T.right)

Postorder — שימוש להערכת ביטויים מתמטיים

בעץ בינארי מלא שבו כל צומת פנימי = פעולה בינארית וכל עלה = מספר, postorder מחשב את ערך הביטוי:

• (11+(2*7))+(3*10) = 11 + 14 + 30 = 55
• ((11+2)*(7+3))*10 = 13 * 10 * 10 = 1300

Preorder — שימושים

• יצירת עותק של עץ.
• Serializing של BST (לשמירה בקובץ).
• הדפסת מבנה תיקיות (תיקייה לפני התוכן).

13. בניית BST — חסם תחתון Ω(n log n)

Naïve insert

• סיבוכיות: \(\Theta(nh)\).
• Best case: \(\Theta(n \log n)\).
• Worst case: \(\Theta(n^2)\) (כשהמפתחות ממויינים מראש → עץ מנוון).

הוכחה (בשלילה):
נניח שאפשר לבנות BST ב-o(n log n).
נבצע Inorder ב-Θ(n) ונקבל את n המפתחות בסדר ממויין.
זה אומר שניתן למיין n מפתחות ב-o(n log n) ע"י השוואות —
סתירה לחסם התחתון Ω(n log n) של מיון מבוסס-השוואות!  ∎

14. בניית BST מאיברים ממויינים — Θ(n)

BuildBST(A, q, r):
if q > r then return null
else
  m = ⌊(q+r)/2⌋
  create a new node v
  v.data = A[m]
  v.left  = BuildBST(A, q, m-1)
  v.right = BuildBST(A, m+1, r)
return v

15. Augmented Data — שדות נוספים

שאלות נפוצות שאפשר לענות עליהן בעזרת augmented data

• Rank — מהי הדרגה של מפתח נתון?
• Select — מהו המפתח בעל דרגה \(k\)?
• חישוב סכום של כל המפתחות הגדולים/קטנים ממפתח נתון.
• חישוב הממוצע של ה-10% התחתונים.

Size augmentation

בכל צומת \(v\) נשמור:

• \(v.\text{size}\) = מספר הצמתים בתת-העץ ששורשו \(v\) (כולל \(v\) עצמו).

עדכון השדה

• Node insert: צומת חדש \(x\) הוא תמיד עלה — \(x.\text{size} = 1\). הגדל ב-1 את \(v.\text{size}\) לכל \(v\) במסלול מ-\(x\) ל-root.
• Node delete: הקטן ב-1 את \(v.\text{size}\) לכל \(v\) במסלול מ-root לצומת שנמחק. במקרה של 2 בנים — הצומת שבאמת נמחק הוא ה-Successor.

16. SELECT(T, k) — האיבר ב-rank \(k\)

רעיון

\(r[x]\) = דרגת \(x\) בתת-העץ ששורשו \(x\). בעזרת שדה \(\text{size}\): \(r[x] = (x.\text{left}).\text{size} + 1\).

SELECT(x, k):
if (x = null) return null
if x.left ≠ null
  then r ← (x.left).size + 1
  else r ← 1
if k = r:        return x
else if k < r:   return SELECT(x.left,  k)
else:            return SELECT(x.right, k - r)

17. RANK(T, x) — דרגה של איבר נתון

רעיון: סופרים את המפתחות שקטנים מ-\(x\)

1. הוסף את האיברים בתת-העץ השמאלי של \(x\) (= \(x.\text{left}.\text{size}\)), \(+1\) ל-\(x\) עצמו.
2. עבור על המסלול \(p\) מ-\(x\) ל-root: לכל \(v \in p\), אם \(v\) הוא בן ימני — הוסף את ה-size של תת-העץ השמאלי של אבא של \(v\), \(+1\) על האבא עצמו.

RANK(T, x):
if x.left ≠ null
  then r ← (x.left).size + 1
  else r ← 1
y ← x
while y.parent ≠ null:
  if y = (y.parent).right
    then if (y.parent).left ≠ null
      then r ← r + ((y.parent).left).size + 1
      else r ← r + 1
  y ← y.parent
return r

18. Sum of Keys < \(x\)

הרחבה חדשה: \(v.\text{sum}\)

בכל צומת \(v\): \(v.\text{sum}\) = סכום כל המפתחות בתת-העץ ששורשו \(v\). (אנלוגי ל-size, אבל סוכמים מפתחות במקום סופרים צמתים.)

SumSmaller(x, k):
if x = null then return 0
if k = x.key
  then s ← (x.left).sum
elseif k < x.key
  then s ← SumSmaller(x.left, k)
else
  s ← x.key + (x.left).sum + SumSmaller(x.right, k)
return s

19. סיכום ונקודות מפתח

• BST = עץ בינארי + תכונה שמאל < שורש < ימין. מימוש Sequence ADT עם Find/Insert/Delete ב-\(O(h)\).
• גובה: בין \(\Omega(\log n)\) (מאוזן) ל-\(O(n)\) (מנוון). שמירת איזון — בהמשך.
• Find, FindMin, FindMax, Successor, Insert, Delete — כולם O(h).
• Join: \(O(1)\) (כשידוע שכל \(T_1 < x < T_2\)). Split: \(O(h)\).
• 3 מקרי מחיקה: אין בנים / בן אחד / שני בנים (= העתק successor ומחק רקורסיבית).
• Inorder על BST = סדר ממויין. שימוש זה נותן חסם תחתון \(\Omega(n \log n)\) לבניית BST מ-keys לא-ממויינים.
• בניית BST מ-סדרה ממויינת: \(\Theta(n)\) ע"י חציון רקורסיבי — והעץ יוצא מאוזן.
• Augmented data: שמירה של שדות נוספים (size, sum, …) מאפשרת לענות על שאלות מורכבות יותר ב-\(O(h)\). עדכון השדות תוך כדי Insert/Delete הוא גם ב-\(O(h)\).
• SELECT(T, k) ו-RANK(T, x) ע"י size augmentation — שניהם \(O(h)\).
• SumSmaller(T, x) ע"י sum augmentation — \(O(h)\).