שאלת מבחן במבוא למדעי המחשב - אוניברסיטת תל אביב 2016 - עצים בינאריים

**עץ חיפוש בינארי - מימוש איטרטיבי ומבנה מעגלי** להלן תזכורת למחלקה "עץ בינארי" שראינו בכיתה, וכן לפונקציה lookup: ```python class Tree_node(): def __init__(self, key, val): self.key = key self.val = val self.left = None self.right = None def __repr__(self): return "[" + str(self.left) + \ " (" + str(self.key) + "," + str(self.val) + ") " \ + str(self.right) + "]" def lookup(root, key): if root == None: return None elif key == root.key: return root.val elif key < root.key: return lookup(root.left, key) else: return lookup(root.right, key) ``` **א.** השלימו את המימוש האלטרנטיבי הבא ל-lookup, שלא עושה שימוש ברקורסיה (מימוש איטרטיבי): ```python def lookup_iterative(root, key): _______________ ``` **ב.** התבוננו כעת בקוד הבא, שמשתמש במחלקה באופן שחורג (מאוד!) מהשימוש הסטנדרטי שלה: ```python Node1 = Tree_node(5,"a") Node2 = Tree_node(4,"b") Node3 = Tree_node(9,"c") Node1.left = Node2 Node1.right = Node3 Node3.left = Node1 Node3.right = Tree_node(11,"d") ``` (i) מה יקרה אם נבצע את הקריאה lookup_iterative(Node1, 4)? (ii) מה יקרה אם נבצע את הקריאה lookup_iterative(Node1, 7)? (iii) מה יקרה אם נבצע את הקריאה lookup_iterative(Node1, 12)? **ג.** כתבו מחדש את הקוד של lookup_iterative מסעיף א, כך שיחזיר תשובה נכונה גם במקרים הבעייתיים מבין אלו שהודגמו לעיל. כלומר יש לקיים את התכונה הבאה: אם קיים רצף של Tree_nodes, נסמנו $N_0,...N_m$, כך ש-$N_m.key = key$, ולכל $i = 1...m$ מתקיים $N_i = N_{i-1}.left$ או $N_i = N_{i-1}.right$, אז על הפונקציה להחזיר את $N_m.val$. אחרת על הפונקציה להחזיר None. דרישה: על הקוד להיות ללא רקורסיה (איטרטיבי). ניתן להניח שכל מפתח מופיע לכל היותר פעם אחת, וכן שלכל צומת, המפתח של בנו השמאלי המיידי קטן יותר, והמפתח של בנו הימני המיידי גדול יותר. אין להניח הנחות נוספות לגבי המבנה או סדר הופעת המפתחות. ```python def lookup_iterative_corrected(root, key): _______________ ```

רמז: בסעיף א: השתמשו בלולאת while שממשיכה כל עוד root אינו None ו-key שונה מ-root.key. בסעיף ב: שימו לב שהמבנה מכיל מעגל (Node3.left = Node1), כך שחיפוש ערך שלא קיים ייכנס ללולאה אינסופית. בסעיף ג: השתמשו בקבוצת visited (set) כדי לזהות צמתים שכבר ביקרנו בהם ולהימנע מלולאה אינסופית.

פתרון: **א.** ```python def lookup_iterative(root, key): while root is not None: if key == root.key: return root.val elif key < root.key: root = root.left else: root = root.right return None ``` **ב.** המבנה שנוצר: Node1(5) -> left=Node2(4), right=Node3(9). Node3(9) -> left=Node1(5), right=Node(11). יש מעגל: Node1 -> Node3 -> Node1. (i) lookup_iterative(Node1, 4): key=4 < 5, עוברים ל-Node2(4). key==4, מחזירים "b". **התוצאה: "b"**. (ii) lookup_iterative(Node1, 7): key=7 > 5, עוברים ל-Node3(9). key=7 < 9, עוברים ל-Node1(5) (כי Node3.left = Node1). key=7 > 5, עוברים ל-Node3(9). **לולאה אינסופית** - התוכנית נתקעת. (iii) lookup_iterative(Node1, 12): key=12 > 5, עוברים ל-Node3(9). key=12 > 9, עוברים ל-Node(11). key=12 > 11, עוברים ל-None. **התוצאה: None**. **ג.** ```python def lookup_iterative_corrected(root, key): visited = set() while root is not None and id(root) not in visited: if key == root.key: return root.val visited.add(id(root)) if key < root.key: root = root.left else: root = root.right return None ``` הסבר: שומרים קבוצה של צמתים שכבר ביקרנו בהם. אם מגיעים לצומת שכבר ביקרנו בו, פירושו שנכנסנו למעגל, ולכן המפתח לא קיים ומחזירים None.