עץ בינארי

מושגים שונים והבהרות

השוואה בין עץ בינארי (Binary Tree) לעץ חיפוש בינארי (Binary Search Tree, BST)

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

  • הגדרה – עץ שבו לכל צומת (Node) יש לכל היותר שני ילדים:
    • ילד שמאלי (Left Child)
    • ילד ימני (Right Child)
      מבנה זה אינו מחייב שום סדר בין תת‑העצים שלו.‏(geeksforgeeks.org, he.wikipedia.org)
  • לעץ בינארי ניתן לייחס תכונות נוספות (מלא, מושלם, כמעט־מושלם, מאוזן) אך הן אינן חלק מהגדרה בסיסית זו.

מהו עץ חיפוש בינארי (BST)?

  • הגדרה – עץ בינארי המקיים תכונת סדר (Binary‑Search‑Tree Property):
    • לכל צומת v‑―‑כל המפתחות שבתת‑העץ השמאלי קטנים ממפתחו של v.
    • כל המפתחות שבתת‑העץ הימני גדולים ממפתחו של v.
      התכונה מאפשרת חיפוש, הכנסה ומחיקה בזמן O(h) כאשר h הוא גובה העץ.‏(geeksforgeeks.org, en.wikipedia.org, he.wikipedia.org)
  • מונחים מקובלים:
    • עברית – עץ חיפוש בינארי
    • אנגלית – Binary Search Tree (ראשי־תיבות BST)

איזון (Balancing) וגובה (Height)

  • גובה (Height) – מספר הקשתות במסלול הארוך ביותר מהשורש (Root) אל עלה (Leaf).
  • גורם איזון (Balance Factor) – height(left) − height(right) של תת‑עצים.
  • עץ מאוזן – עץ שבו גבהי תת‑העצים בכל צומת אינם שונים ביותר מקבוע c (לרוב c=1).‏(geeksforgeeks.org)

עץ AVL

  • הגדרה – עץ AVL (על שם Adelson‑Velsky ו‑Landis) הוא עץ חיפוש בינארי מאוזן‐עצמית (Self‑Balancing BST) שבו │balance factor│ ≤ 1 בכל צומת.‏(geeksforgeeks.org, geeksforgeeks.org)
  • פעולות הכנסה/מחיקה מבוצעות כ‑BST רגיל, ואחריהן סיבובים (Rotations) לשמירת האיזון.

האם אפשר לומר “עץ AVL הוא BST מאוזן?”

כן. עץ AVL מקיים both – תכונת הסדר של BST וגם תנאי איזון קפדני. לכן הוא דוגמה קלאסית ל‑Balanced BST.

מילון מושגים

מונח עברי Term (EN) הגדרה קצרה
צומת Node יחידת המידע הבסיסית בעץ, הכוללת מפתח וקישורים לילדים
שורש Root הצומת העליון שאין לו הורה
עלה Leaf צומת ללא ילדים
תת‑עץ Subtree עץ הנובע מצומת כלשהו וצאצאיו
גובה Height אורך המסלול הארוך ביותר מן הצומת אל עלה
גורם איזון Balance Factor הפרש גבהים בין תת‑העץ השמאלי לימני
עץ מאוזן Balanced Tree עץ ש‑ balance factor  בכל צומת חסום בקבוע. בד”כ 1
עץ AVL AVL Tree Self‑balancing BST with balance factor ≤ 1

סיכום קצר

עץ בינארי מתאר מבנה בלבד; עץ חיפוש בינארי מוסיף סדר, ו‑עץ AVL מוסיף איזון אוטומטי. לכן: כל AVL הוא BST, וכל BST הוא עץ בינארי, אך לא להפך.

מהו עץ מנוון (Degenerate Tree) או עץ פתולוגי (Pathological Tree)?

הגדרה – עץ בינארי שבו כל צומת שאינו עלה מחזיק ילד אחד בלבד – או שמאלי או ימני, אף פעם לא שניהם. במילים אחרות: עץ Pathological/ Degenerate, בנוי למעשה כ‑Linked List.

מקבילות באנגלית

עברית אנגלית מקובלת הערה
דגנרט Degenerate Tree מתאר עץ “פתולוגי” שבו h≈n-1
  Pathological Tree שם כללי למצבים קיצוניים

מאפיינים מרכזיים

  • גובה h≈n−1 → פעולות חיפוש/הכנסה/מחיקה על BST עלולות לרדת ל‑O(n).
  • נוצר למשל כאשר מוסיפים מפתחות בסדר עולה/יורד לעץ חיפוש בינארי.
  • מקובל לראות בו anti‑pattern; עצים מאוזנים (AVL, Red‑Black, Treap, Splay) נועדו למנוע מצב כזה.

דוגמה

הכנסת הערכים [1,2,3,4,5] ל‑BST ריק בתורם:

1
 \
  2
   \
    3
     \
      4
       \
        5

העץ הנ”ל הוא דגנרט – כל צומת מחזיק בן ימני יחיד.

השוואה מהירה

תכונה BST מאוזן טיפוסי עץ דגנרט
מספר ילדים לצומת פנימי ≤ 2 (לעיתים 2) 1 בלבד
גובה ממוצע O(log n) O(n)
ביצועי חיפוש גרועים נדיר תמיד במקרה הגרוע

מקורות

  1. Wikipedia – Degenerate Tree
  2. GeeksforGeeks – Degenerate (Binary) Tree
  3. קורס “מבני נתונים”, אונ’ ת”א – יחידה 3, שקופיות “עצים פתולוגיים”