Recitation 4
Contents |
Conjecture
Conjecture from lecture: To find whether there are any keys within 3 of our query k, we only need to insert along a path.
Proof: once we visit a node, one of three things happen: we stop, because the key is within 3 of k; we go to the left; or we go to the right. If we go to the left, the key was greater than k+3; thus, so is everything in its right subtree, and we can ignore it. If we go to the right, the key was less than k-3, and likewise, we can ignore its left subtree.
Delete-Min
Implemented by walking down the left path, removing the leftmost node, and promoting its right child (if any); O(h) time, where h is the height of the tree.
Subtree Size and Rank
Whenever we visit a node while inserting, we increment its subtree size counter by 1. We decrease it by 1 when visiting for a delete-min operation.
Rank of a key k can be computed by finding k, and adding up the left subtree sizes + 1 when a right child pointer is followed.
Python Object Orientation
A brief summary of how to define a Python class:
class classname(object): def __init__(self, arg1, arg2): # defines a constructor taking arguments arg1 and arg2 # instance variables usually initialized here def fun1(self, arg1): # if obj is an object of class classname, # fun1 can be called as obj.fun1(arg) or classname.fun1(obj, arg) ....
Example code for a BST with subtree sizes: http://courses.csail.mit.edu/6.006/fall07/source/bstsize.py