מיריעצים בינאריים ועץ חיפוש שמאלה קטן, ימינה גדול
בעץ בינארי לכל צומת יש עד שני בנים: שמאלי וימני. בעץ חיפוש בינארי יש עוד כלל: כל מה שמשמאל קטן מהצומת, וכל מה שמימין גדול ממנו. בזכות הכלל הזה מוצאים ערך בכמה בדיקות בלבד. כאן בונים עץ, מחפשים בו וסופרים בדיקות, ובסוף סורקים אותו ברקורסיה. כדאי להכיר קודם את הרשימה המקושרת ואת הרקורסיה.
הרעיון
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
שורש, בנים ועלים
הצומת העליון הוא השורש. לכל צומת יש left ו-right. צומת בלי בנים הוא עלה. בבן שחסר יש None.
הכנסה וחיפוש
מתחילים בשורש. קטן מהצומת? הולכים שמאלה. גדול? ימינה. בהכנסה ממשיכים עד מקום ריק. בחיפוש עוצרים כשמוצאים, או כשמגיעים ל-None.
שלוש סריקות
תחילית (preorder): צומת, שמאל, ימין. תוכית (inorder): שמאל, צומת, ימין. סופית (postorder): שמאל, ימין, צומת. בעץ חיפוש הסריקה התוכית יוצאת ממוינת.
מעבדה: בונים עץ ומחפשים
התוכנית מכניסה ערכים לעץ, אחד אחרי השני, ואז מחפשת ערך. הזיזו את המחוונים. לחצו "שורה הבאה": בזמן החיפוש הצמתים שנבדקו נצבעים בצהוב, והצומת הנוכחי מסומן במסגרת.
נסו את אלה:
הריצו בעצמכם
אפשר לשנות את הקוד ולהריץ פייתון אמיתי. בפעם הראשונה הטעינה לוקחת כמה שניות.
טעויות שכולם עושים
שוכחים את התנאי לעצירה
בלי בדיקת None, הרקורסיה מגיעה לבן שחסר ומנסה לקרוא node.left של None.
✗ AttributeError
def inorder(node):
inorder(node.left)
...✓ עוצרים ב-None
def inorder(node):
if node is None:
return
inorder(node.left)לא שומרים את מה ש-insert מחזיר
insert מחזיר את השורש. אם לא מציבים אותו בחזרה, הצומת החדש לא מתחבר לעץ.
✗ העץ נשאר ריק
insert(root, v)✓ מתחבר
root = insert(root, v)מחפשים בשני הצדדים
בעץ חיפוש יודעים לאן ללכת. חיפוש בשני הצדדים עובד, אבל מבזבז את כל היתרון.
✗ בודק הכל
return find(node.left, t) or find(node.right, t)✓ צד אחד
if t < node.value:
return find(node.left, t)
return find(node.right, t)מבלבלים בין הסריקות
מה שקובע הוא איפה נמצאת שורת ההדפסה: לפני שתי הקריאות, ביניהן, או אחריהן.
✗ זו תחילית
print(node.value)
inorder(node.left)
inorder(node.right)✓ תוכית
inorder(node.left)
print(node.value)
inorder(node.right)דוגמה פתורה: סריקה ברקורסיה
עץ קטן עם 5 צמתים. בחרו סריקה ועברו צעד אחרי צעד. כל קריאה לפונקציה עם None חוזרת מיד. המספר הקטן ליד כל צומת אומר באיזה סדר הוא הודפס.
תרגול
שאלות שכולם שואלים
מה זה עץ חיפוש בינארי?
עץ שבו לכל צומת יש עד שני בנים, וכל הערכים בתת העץ השמאלי קטנים ממנו, וכל הערכים בתת העץ הימני גדולים ממנו. הכלל הזה מאפשר לחפש מהר: בכל צעד הולכים רק לצד אחד. נסו במעבדה.
מה ההבדל בין סריקה תחילית, תוכית וסופית?
בכולן מבקרים בכל הצמתים, וההבדל הוא מתי מטפלים בצומת עצמו. תחילית: קודם הצומת ואחר כך הבנים. תוכית: שמאל, צומת, ימין. סופית: קודם שני הבנים ואחר כך הצומת.
למה סריקה תוכית של עץ חיפוש יוצאת ממוינת?
כי בכל צומת קודם מדפיסים את כל מה שמשמאל, שכולו קטן ממנו, אחר כך את הצומת, ואחר כך את כל מה שמימין, שכולו גדול ממנו. כך זה בכל רמה בעץ. תרגלו למטה.