Python Language: Modify the implementation of the BinarySearchTreeMap class, so

Question

Python Language: Modify the implementation of the BinarySearchTreeMap class, so in addition to all the functionality it already allows, it will also support the following method: def get_ith_smallest(self, i) This method should support indexing. That is, when called on a binary search tree, it will return the i-th smallest key in the tree (for i=1 it should return the smallest key, for i=2 it should return the second smallest key, etc.). For example, your implementation should behave as follows: >>> bst = BinarySearchTreeMap() >>> bst[7] = None >>> bst[5] = None >>> bst[1] = None >>> bst[14] = None >>> bst[10] = None >>> bst[3] = None >>> bst[9] = None >>> bst[13] = None >>> bst.get_ith_smallest(3) 5 >>> bst.get_ith_smallest(6) 10 >>> del bst[14] >>> del bst[5] >>> bst.get_ith_smallest(3) 7 >>> bst.get_ith_smallest(6) 13 Implementation requirements: 1. The runtime of the existing operations should remain as before (worst case of ?(height)). The runtime of the get_ith_smallest method should also be worst case of ?(?eight). 2. You should raise an IndexError exception in case i is out of range.

Explanation / Answer

class BinarySearchTreeMap: class Item: def __init__(self, key, value=None): self.key = key self.value = value class Node: def __init__(self, item): self.item = item self.parent = None self.left = None self.right = None self.num_subtree_left = 0 self.num_subtree_right = 0 def num_children(self): count = 0 if (self.left is not None): count += 1 if (self.right is not None): count += 1 return count def disconnect(self): self.item = None self.parent = None self.left = None self.right = None self.num_subtree_left = None self.num_subtree_right = None def __init__(self): self.root = None self.size = 0 def __len__(self): return self.size def is_empty(self): return len(self) == 0 # raises exception if not found def __getitem__(self, key): node = self.subtree_find(self.root, key) if (node is None): raise KeyError(str(key) + " not found") else: return node.item.value # returns None if not found def subtree_find(self, subtree_root, key): curr = subtree_root while (curr is not None): if (curr.item.key == key): return curr elif (curr.item.key > key): curr = curr.left else: # (curr.item.key key): curr.num_subtree_left -= 1 curr = curr.left else: # (curr.item.key

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.