The purpose of this exercise is to have you exploit the fact that AVL trees are balanced to quickly answer certain queries that dictionaries based on hash tables cannot.
You will add a new method to the class AVLDict in the file avl_dict.py (link) we developed in class.
def ith_key(self, index: int):
"""
Returns the key that would be at the given index in the sorted list of all keys of t he tree.
Raises an IndexError if the index is out of range (i.e. < 0 or = len(self)).
Running time: O(log n) where the tree has n items.
"""
That is, you should not actually get the list of all items and return the one at the given index. That approach would run in O(n) time (aside: this is a helpful approach for testing your solution). Rather, you will need to slightly modify the internal implementation of the AVL tree to support this function efficiently.
An example of how a working solution could be used.
from avl_dict import AVLDict
d = AVLDict()
d["arrival"] = "hello"
d["departure"] = "goodbye"
d.ith_key(0)
"arrival"
d.ith_key(1) "departure"
d["cancel"] = "cancelled"
d.ith_key(1)
"cancel"
d.ith_key(2) "departure"
del d["arrival"]
d.ith_key(0) "cancel"
Requirements
For each AVLNode, also maintain an integer "num". This should be such that node.num is the
number of nodes in the subtree rooted at "node". For example, if node is a leaf node, then
1 of 3 node.num shoudl be 1; if node is one of the "empty" nodes with key == None then2018node-04.num-14, 1:01 p.m.
should be 0.
Assignment
https://eclass.srv.ualberta.ca/mod/assign/view.php...
Implement the new ith_key() function so it runs in O(log n) time.
Remove the import bstviz statement at the top before you submit.
Hints
You can maintain this number in a very similar way to how the "height" of an AVLNode was maintained through insertion, deletion, and rotations.
Don't forget to set the "num" value of the node properly when inserting a new key during update!
Now, assuming each node is correctly storing its corresponding value "num", how can you search from the root toward the correct node by comparing "num" with "index"? Draw some examples to help you see how you could do it.
Your solution will be eligible for partial credit if it correctly maintains the "num" value of an AVLNode, even if it does not correctly implement the ith_key function. Your final solution must run in O(log n) time to be eligible for full marks.
Submit only your modified version of avl_dict.py. Do not zip it. As usual, adhere to the code submission guidelines and practice clean style with appropriate comments.
