Exercise 5: AVL Trees

CMPUT 275 Wi18 - INTRO TO TANGIBLE COMPUT II
Combined LBL Wi18
Exercise 5: AVL Trees
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
node.num shoudl be 1; if node is one of the "empty" nodes with key == None then node.num
should be 0.
Assignment https://eclass.srv.ualberta.ca/mod/assign/view.php...
1 of 3 2018-04-14, 1:01 p.m.
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.
Submission status
Feedback
Attempt number This is attempt 1 ( 1 attempts allowed ).
Submission status Submitted for grading
Grading status Graded
Due date Monday, 12 March 2018, 11:55 PM
Time remaining Assignment was submitted 1 day 2 hours early
Last modified Sunday, 11 March 2018, 9:09 PM
File submissions
Export to portfolio
avl_dict.py
Submission comments Comments (0)
Grade 55.00 / 100.00
Graded on Saturday, 7 April 2018, 6:32 PM
Graded by Somjit Nath
Assignment https://eclass.srv.ualberta.ca/mod/assign/view.php...
2 of 3 2018-04-14, 1:01 p.m.
AssignmentFeedback comments Correct num. Wrong ith_key, error while running. https://eclass.srv.ualberta.ca/mod/assign/view.php...
3 of 3 2018-04-14, 1:01 p.m.