עץ חיפוש בינארי
עץ חיפוש בינארי (Binary Search Tree, BST) הוא עץ בינארי שבו לכל צומת מתקיימים התנאים הבאים:
1. לכל צומת יש לכל היותר שני ילדים - אחד שמאלי ואחד ימני.
2. הערכים בתת־העץ השמאלי של צומת כלשהו הם קטנים מהערך בצומת.
3. הערכים בתת־העץ הימני של צומת כלשהו הם גדולים מהערך בצומת.
4. כל תת־עץ עצמו הוא גם עץ חיפוש בינארי.
תרגול
מה יקרה אם תכניסי לעץ חיפוש בינארי רצף מספרים ממוין (עולה)? איזה מבנה יווצר?
___________________________________________________________________________ציירי את העץ שיווצר מהכנסת המספרים הבאים לעץ חיפוש בינארי משמאל לימין:
5,8,19,2,1,3,25,7מה הערך המינימלי בעץ חיפוש בינארי ואיך מגיעים אליו?
___________________________________________________________________________מה הערך המקסימלי בעץ חיפוש בינארי ואיך מגיעים אליו?
___________________________________________________________________________כמה צעדים מקסימליים יידרשו לחיפוש ערך בעץ בגובה h?
___________________________________________________________________________האם חיפוש בעץ חיפוש בינארי תמיד יותר יעיל מהחיפוש ברשימה? הסבירי גם מתי לא.
___________________________________________________________________________עקבי אחר העץ הבא:
רשמי את סדר הביקור עבור InOrder בעץ BST - ומה המשמעות של התוצאה?
___________________________________________________________________________המשמעות:___________________________________________________________________ רשמי את סדר הביקור עבור PreOrder בעץ BST - ומה המשמעות של התוצאה?
___________________________________________________________________________המשמעות:___________________________________________________________________
מה ההבדל בין preorder לבין postorder בהקשר של ________________________________? BST
תרגול כתיבת קוד
1. כתבי פעולה אשר תקבל BST ומספר שלם, הפעולה תוסיף את המספר למקום המתאים בעץ
2. כתבי פעולה אשר תקבל BST ותחזיר את האיבר הגדול ביותר בעץ
3. כתבי פעולה המקבלת BST ומספר שלם ומחזירה האם המספר מופיע בעץ.
● מהי סיבוכיות הפעולה אם ידוע שהעץ מאוזן?
● מהי סיבוכיות הפעולה כשלא ידוע אם העץ מאוזן, במקרה הגרוע ביותר?
4. כתבי פעולה אשר תקבל BST אשר ידוע כי אינו מכיל ערכים כפולים, ומספר שלם. הפעולה תסיר מהעץ את הצומת שערכה שווה למספר(יש לבדוק את כל שלושת המקרים: עלה, צומת עם ילד אחד, צומת עם שני ילדים).