Binary search trees · עצי חיפוש בינאריים
Binary search trees
- A binary search tree (BST) stores values so they stay sorted and are fast to find.
- Each node holds a value and links to up to two children: a
leftand aright. - The top node is the root. A node with no children is a leaf.
עצי TODO בינאריים
- עץ TODO בינארי (BST) מאחסן ערכים כך שהם נשארים ממוינים ומהירים למציאה.
- כל צומת מחזיק ערך ומקשר עד שני ילדים:
leftו-right. - הצומת העליון הוא השורש. צומת ללא ילדים הוא עליה.
The BST rule
- For every node: everything in its left subtree is smaller, everything in its right is larger.
- This one rule is what lets you find a value by going left or right — never both.
הכלל של עץ TODO בינארי
- עבור כל צומת: כל מה שיש בצד שמאל שלו הוא קטן יותר, וכל מה שיש בצד ימין הוא גדול יותר.
- הכלל היחיד הזה הוא מה שמאפשר לך למצוא ערך על ידי הלכה שמאלה או ימינה — לעולם לא שתיהן.
5
/ \
3 8
/ \ \
1 4 9
left < node < right, at every node
A node
- We model a node as a small object with a
value, aleft, and aright. - A brand-new node has no children yet, so
leftandrightstart asNone.
צומת
- אנו דמוייים צומת כאובייקט קטן עם
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
Inserting a value
- Start at the root. If the tree is empty, the new value becomes the root.
- If the value is smaller than the current node, go left; otherwise go right.
- Repeat until you reach an empty spot, and put the new node there.
הוסעת ערך
- התחל בשורש. אם העץ ריק, הערך החדש הופך לשורש.
- אם הערך קטן מהצומת הנוכחי, לך שמאל; אחרת לך ימינה.
- חזור על כך עד שתגיע למקום ריק, והנח את הצומת החדש שם.
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 traversal gives sorted order
- In-order traversal visits: the left subtree, then the node, then the right subtree.
- Because of the BST rule, this visits the values in sorted order — for free.
- It is naturally recursive: traverse left, take the value, traverse right.
נסיעה בסדר (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]
Searching is fast
- To find a value, compare it with the node, then go left or right — skipping half the tree each step.
- In a balanced tree this takes about
O(log n)steps, much faster than scanning a list. - A badly-shaped tree (values inserted already sorted) can degrade to a line —
O(n).
חיפוש מהיר
- כדי למצוא ערך, השווא אותו לצומת, ואז לך שמאלה או ימינה — מדלג מחצי העץ בכל צעד.
- בעץ מאוזן זה לוקח כ-
O(log n)צעדים, הרבה מהר יותר מסריקה של רשימה. - עץ בעל צורה גרועה (ערכים שהוכנסו כבר במיון) יכול להתדרדר לקו —
O(n).
Common mistakes
- In a binary search tree: left child < node < right child.
- An unbalanced tree loses the speed advantage.
טעויות נפוצות
- בעץ חיפוש בינארי: ילד שמאל < צומת < ילד ימין.
- עץ לא מאוזן מאבד את יתרון המהירות.
Now you try
- Build the three core operations:
insert,in_order, andcontains. - The
Nodeclass (and a workinginsert, where you need it) is provided. - Press Check answer to test it on several trees.
כעת תנסו בעצמכם
- בנה את שלושת הפעולות הבסיסיות:
insert,in_orderוcontains. - מוספקת כיתה
Node(וגם קוד עובדinsert, כאשר יש צורך). - לחץ על בדיקת תשובה כדי לבחון את זה במספר עצים.
Searching a BST · חיפוש בעץ BST
Left is smaller, right is bigger — so each step skips half the tree. · שמאל קטן יותר, ימין גדול יותר — ולכן בכל צעד מעלים מחצית מעץ.
The Node class is provided. Write insert(root, value) that adds value to the BST and returns the root. If root is None, return a new Node(value). If value < root.value go left, otherwise go right — and reassign that child to the result of inserting into it. · הקלאס Node מסופק. כתוב insert(root, value) שיוסיף value ל-BST ויחזיר את השורש. אם root הוא None, החזר עץ Node(value) חדש. אם value < root.value יש ללכת שמאל, אחרת ימין — והחלף את הילד ההוא בתוצאת ההכנסה אליו.
Click Run to see the output here. · לחץ על הרץ כדי לראות את התוצא כאן.
Node and a working insert are provided. Write in_order(root) that returns a list of the values from an in-order traversal: left subtree, then this node's value, then right subtree. Thanks to the BST rule the list comes out sorted. An empty tree (None) gives []. · מסופקים Node וinsert פעילים. כתוב in_order(root) שמחזיר רשימה של הערכים מטיול בסדר ימני-שמאלי: תת-עץ שמאלי, ולאחר מכן ערך הצומת הנוכחי, ולאחר מכן תת-עץ ימני. בזכות כלל BST הרשימה תצא מסודרת. עץ ריק (None) מחזיר [].
Click Run to see the output here. · לחץ על הרץ כדי לראות את התוצא כאן.
Node and a working insert are provided. Write contains(root, value) that returns True if value is in the tree, else False. Use the BST rule: if it equals this node return True; if it is smaller search left, otherwise search right; an empty branch (None) means it is not there. · Node ופונקציית insert פעילה מסופקים. כתוב contains(root, value) שמחזיר True אם value נמצא בעץ, אחרת False. השתמש בכלל ה-BST: אם שווה לנוכחי החזר True; אם קטן יותר חפש שמאל, אחרת חפש ימין; ענף ריק (None) פירושו שהוא אינו שם.
Click Run to see the output here. · לחץ על הרץ כדי לראות את התוצא כאן.