עץ חיפוש בינארי

לפני שנגדיר מהו עץ (Tree), נבחן את המוטיבציה לשימוש בו – מדוע ומתי כדאי להשתמש במבנה נתונים כזה. עבור מבני נתונים ליניאריים כגון מערכים (Arrays) בגודל $n$ ו-רשימות מקושרות (Linked Lists) בגודל $n$, קיימות בעיות, בעיקר בסיבוכיות הזמן של פעולות שונות:

עבור מערך או רשימה מקושרת בגודל $n$:

• הוספה היא $O(1)$
• חיפוש הוא $O(n)$
• מחיקה היא $O(n)$

עבור מערך ממוין בגודל $n$:

• חיפוש הוא $O(\log n)$
• הוספה היא $O(n)$
• מחיקה היא $O(n)$

לעומת זאת, כפי שנראה, עצים (כאשר הם מאוזנים) משלבים בצורה אלגנטית את היתרונות של שני מבני הנתונים הללו.

מהו עץ?

עץ הוא מבנה נתונים המורכב מצמתים (nodes) וקשתות (edges) עם יחסים היררכיים (הורה–ילד). כל צומת מכיל נתון כלשהו, וכן מצביעים (pointers) לצאצאים של אותו צומת.

מאפיינים של עץ:

• יש לו מבנה היררכי.
• לכל צומת $n$, פרט לשורש, יש הורה אחד בלבד.
• כל צומת מאחסן ערך.
• עלה (leaf) הוא צומת ללא ילדים.
• הצמתים מחוברים באמצעות קשתות (קווים).

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

מהו עץ בינארי?

עץ בינארי הוא סוג של עץ שבו לכל צומת יש לכל היותר שני ילדים, הנקראים הילד השמאלי ו-הילד הימני.

לצומת בעץ בינארי יש את המאפיינים הבאים:

• עומק (Depth) – עומק של צומת בעץ בינארי הוא מספר הקשתות במסלול הייחודי מהשורש אל אותו צומת.
• גובה (Height) – הגובה של צומת בעץ מוגדר כמספר הקשתות במסלול היורד הארוך ביותר מאותו צומת אל צומת עלה.

הגדרה רקורסיבית פורמלית של עץ בינארי (BT) היא כדלקמן:

1. מקרה בסיס: עץ ריק (המוצג לרוב כ-null או NIL) הוא עץ בינארי.
2. צעד רקורסיבי:
   1. צומת שורש המכיל נתונים כלשהם.
   2. תת-עץ שמאלי, שהוא בעצמו עץ בינארי.
   3. תת-עץ ימני, שהוא גם עץ בינארי.

כיצד עצים בינאריים עוזרים לנו?

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

במילים אחרות, בעץ בינארי שבו כל הרמות מלאות, יש $O(\log (n))$ רמות, כאשר $n$ הוא מספר הצמתים בעץ.

עץ חיפוש בינארי (Binary Search Tree)

בעץ חיפוש בינארי (BST), לכל צומת יכולים להיות לכל היותר שני ילדים (שמאלי וימני), והוא חייב לקיים תכונת סדר מסוימת.

תכונות מפתח

עבור כל צומת נתון בעץ חיפוש בינארי:

• כל הערכים בתת-העץ השמאלי חייבים להיות קטנים מערך הצומת עצמו.
• כל הערכים בתת-העץ הימני חייבים להיות גדולים מערך הצומת עצמו.
• גם תת-העץ השמאלי וגם תת-העץ הימני חייבים להיות בעצמם עצי חיפוש בינאריים.

פעולות בסיסיות על עץ חיפוש בינארי

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

חיפוש בעץ חיפוש בינארי

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

התהליך הוא כדלקמן:

1. מתחילים בצומת השורש.
2. משווים את ערך המטרה שאותו מחפשים לערך של הצומת הנוכחי.

3. קובעים את הצעד הבא על פי ההשוואה:

   1. אם ערך המטרה שווה לערך הצומת הנוכחי – החיפוש הצליח, וניתן להחזיר את הצומת.
   2. אם ערך המטרה קטן מערך הצומת הנוכחי – הערך נמצא ב-תת-העץ השמאלי, ולכן ממשיכים לחפש בילד השמאלי.
   3. אם ערך המטרה גדול מערך הצומת הנוכחי – הערך נמצא ב-תת-העץ הימני, ולכן ממשיכים לחפש בילד הימני.

4. חוזרים על תהליך ההשוואה והמעבר עד שאחד משני התנאים מתקיים:

   1. ערך המטרה נמצא.
   2. מגיעים לצומת NULL (או ריק), מה שאומר שערך המטרה אינו קיים בעץ.

חיפוש בעץ חיפוש בינארי ב-Ruby:

def tree_search(node, key)
  while node != nil && key != node.key
    if key < node.key
      node = node.left
    else
      node = node.right
    end
  end

  node
end	

הוספה לעץ חיפוש בינארי

הוספת ערך חדש לעץ חיפוש בינארי דומה מאוד לתהליך החיפוש.

התהליך הוא כדלקמן:

1. מתחילים בצומת השורש:

   • אם העץ ריק, הערך החדש הופך לצומת השורש.

2. משווים את הערך להוספה לערך הצומת הנוכחי:

   1. אם הערך קטן מערך הצומת הנוכחי – עוברים ל-ילד השמאלי.
   2. אם הערך גדול מערך הצומת הנוכחי – עוברים ל-ילד הימני.
3. חוזרים על ההשוואה והמעבר שמאלה או ימינה עד שמגיעים למיקום של ילד NULL.

4. מוסיפים את הצומת החדש:

   • מכניסים את הערך החדש במיקום הריק כצומת עלה.

הוספת ערך לעץ חיפוש בינארי ב-Ruby:

def insert(node, key)
  return Node.new(key) if node.nil?

  if key < node.value
    node.left = insert(node.left, key)
  elsif key > node.value
    node.right = insert(node.right, key)
  end

  node
end

מחיקה מעץ חיפוש בינארי

מחיקה בעץ חיפוש בינארי מורכבת יותר מהוספה, משום שיש לשמור על תכונת ה-BST גם לאחר הסרת הצומת.

מקרים למחיקה

כאשר רוצים למחוק צומת עם ערך נתון, קיימים שלושה מקרים עיקריים:

1. הצומת הוא עלה (ללא ילדים):

   • פשוט מסירים את הצומת.
   • אין צורך בהתאמות נוספות.

2. לצומת יש ילד אחד:

   • מחליפים את הצומת בילד שלו.
   • שומר על תקינות עץ החיפוש הבינארי.

3. לצומת יש שני ילדים (המקרה המורכב ביותר):

   • מחליפים את הצומת באחד מהבאים:

     1. היורש הסדרי (Inorder successor) – הצומת הקטן ביותר בתת-העץ הימני.
     2. הקודם הסדרי (Inorder predecessor) – הצומת הגדול ביותר בתת-העץ השמאלי.

   • לאחר מכן מוחקים את היורש/הקודם (שייכנס כעת למקרה 1 או 2).