עצי חיפוש בינאריים
עצי TODO בינאריים
- עץ TODO בינארי (BST) מאחסן ערכים כך שהם נשארים ממוינים ומהירים למציאה.
- כל צומת מחזיק ערך ומקשר עד שני ילדים:
leftו-right. - הצומת העליון הוא השורש. צומת ללא ילדים הוא עליה.
הכלל של עץ TODO בינארי
- עבור כל צומת: כל מה שבענף השמאלי שלו הוא קטן יותר, וכל מה שבענף הימני הוא גדול או שווה (בשיעור זה נשלחים ערכים שווים לימין).
- הכלל היחיד הזה הוא מה שמאפשר לך למצוא ערך על ידי הלכה שמאלה או ימינה — לעולם לא שתיהן.
5
/ \
3 8
/ \ \
1 4 9
left < node <= right, at every node
צומת
- אנו דמוייים צומת כאובייקט קטן עם
value,leftוright. - לצומת חדש אין עדיין ילדים, ולכן
leftוrightמתחילים כNone.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
n = Node(5)
print(n.value) # 5
print(n.left) # None
הוסעת ערך
- התחל בשורש. אם העץ ריק, הערך החדש הופך לשורש.
- אם הערך קטן מהצומת הנוכחי, לך שמאל; אחרת לך ימינה.
- חזור על כך עד שתגיע למקום ריק, והנח את הצומת החדש שם.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(root, value):
if root is None:
return Node(value)
if value < root.value:
root.left = insert(root.left, value)
else:
root.right = insert(root.right, value)
return root
root = None
for v in [5, 3, 8, 1]:
root = insert(root, v)
print(root.value) # 5
print(root.left.value) # 3
print(root.right.value) # 8
נסיעה בסדר (In-order) נותנת סדר ממוין
- נסיעה בסדר מבקרת: את צד שמאל, ואז את הצומת, ואז את צד ימין.
- בגלל כלל BST, זה מבקר על הערכים בסדר ממוין — בחינם.
- זה טבעית רקורסיבי: נסה שמאל, קח את הערך, נסה ימין.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(root, value):
if root is None:
return Node(value)
if value < root.value:
root.left = insert(root.left, value)
else:
root.right = insert(root.right, value)
return root
def in_order(root):
if root is None:
return []
return in_order(root.left) + [root.value] + in_order(root.right)
root = None
for v in [5, 3, 8, 1, 4]:
root = insert(root, v)
print(in_order(root)) # [1, 3, 4, 5, 8]
חיפוש מהיר
- כדי למצוא ערך, השווא אותו לצומת, ואז לך שמאלה או ימינה — מדלג מחצי העץ בכל צעד.
- בעץ מאוזן זה לוקח כ-
O(log n)צעדים, הרבה מהר יותר מסריקה של רשימה. - עץ בעל צורה גרועה (ערכים שהוכנסו כבר במיון) יכול להתדרדר לקו —
O(n).
טעויות נפוצות
- בעץ חיפוש בינארי: ילד שמאלי < צומת <= ילד ימני (ערכים שווים הולכים לימין כאן).
- עץ לא מאוזן מאבד את יתרון המהירות.
כעת תנסו בעצמכם
- בנה את שלושת הפעולות הבסיסיות:
insert,in_orderוcontains. - מוספקת כיתה
Node(וגם קוד עובדinsert, כאשר יש צורך). - לחץ על בדיקת תשובה כדי לבחון את זה במספר עצים.
חיפוש בעץ BST
שמאל קטן יותר, ימין גדול יותר — ולכן בכל צעד מעלים מחצית מעץ.
רמת קושי 5/5 · 400 מטבעות + בונוס קטן בהשלמה הראשונה היום
הקלאס Node מסופק. כתוב insert(root, value) שיוסיף value ל-BST ויחזיר את השורש. אם root הוא None, החזר עץ Node(value) חדש. אם value < root.value יש ללכת שמאל, אחרת ימין — והחלף את הילד ההוא בתוצאת ההכנסה אליו.
לחץ על הרץ כדי לראות את התוצא כאן.
רמת קושי 5/5 · 400 מטבעות + בונוס קטן בהשלמה הראשונה היום
מסופקים Node וinsert פעילים. כתוב in_order(root) שמחזיר רשימה של הערכים מטיול בסדר ימני-שמאלי: תת-עץ שמאלי, ולאחר מכן ערך הצומת הנוכחי, ולאחר מכן תת-עץ ימני. בזכות כלל BST הרשימה תצא מסודרת. עץ ריק (None) מחזיר [].
לחץ על הרץ כדי לראות את התוצא כאן.
רמת קושי 5/5 · 400 מטבעות + בונוס קטן בהשלמה הראשונה היום
Node ופונקציית insert פעילה מסופקים. כתוב contains(root, value) שמחזיר True אם value נמצא בעץ, אחרת False. השתמש בכלל ה-BST: אם שווה לנוכחי החזר True; אם קטן יותר חפש שמאל, אחרת חפש ימין; ענף ריק (None) פירושו שהוא אינו שם.
לחץ על הרץ כדי לראות את התוצא כאן.