שיעור 12: עצים ו-BST
חשבו על אילן יוחסין, או תיקיות בתוך תיקיות: יש 'למעלה' שממנו מסתעפים פריטים 'מתחת'. זה 'עץ' — כל נקודה היא 'צומת' (node). ב'עץ חיפוש בינארי' (BST) לכל צומת, שמאל קטן ממנו וימין גדול ממנו — בדיוק כמו לחפש מילה במילון, פותחים באמצע ומדלגים על חצי. כשהעץ מאוזן, החיפוש הוא O(log n).
BST הוא כמו לחפש מילה במילון: פותחים באמצע, ואם המילה 'מוקדמת' יותר מדלגים על כל החצי הימני בבת אחת. כל השוואה חוסכת חצי מהעבודה — אבל רק אם הדפים מחולקים שווה בשווה.
- מחלקה (class)
- תבנית לקופסה קטנה עם שדות. class TreeNode מגדירה קופסה עם שלושה שדות: val (הערך) ו-left/right (הילדים). TreeNode(5) יוצרת קופסה כזו, ו-self הוא פשוט "הקופסה הנוכחית" (כמו בשיעור הקודם על רשימות מקושרות).
- עץ חיפוש בינארי
- עץ בינארי שבו לכל צומת, כל הערכים בתת-העץ השמאלי קטנים ממנו וכל הערכים בתת-העץ הימני גדולים ממנו.
- סריקת עץ
- מעבר על כל צמתי העץ בסדר מוגדר. inorder (שמאל, צומת, ימין) על BST מחזיר את הערכים ממוינים.
- עץ מאוזן
- עץ שגובהו כ-log n, כך שחיפוש לוקח O(log n). עץ 'מתמתח' (skewed) מאבד את היתרון ומגיע ל-O(n).
