In this problem, we will introduce another framework for describing the structure of a binary search tree (BST), and use that framework to prove a better upper bound on the rotation distance between two BSTs on n nodes than the bound of 2n - 2 we proved in class.
Suppose we have a convex (n+2)-gon (e.g., for n = 6, we have an octagon). Suppose furthermore that we triangulate this polygon. Pick one start edge of this polygon. Let the triangle that contains this edge represent the root of an n node BST. Now starting from this triangle, walk across the two non-start edges (one veers to the right and one veers to the left, starting from the start edge). Let the edge on the right recursively represent the root of the right subtree (as represented by the smaller polygon) of the BST and the edge on the left recursively represent the root of the left subtree (See Figure). A 3-gon represents a BST with one node. Convince yourself that an (n+2)-gon describes a BST with n nodes.
a. What does a BST rotation correspond to in this model?
b. Consider 2 triangulated (n+2)-gons A and B with the same vertex labels. For n > 10, prove that there exists a vertex x for which degree(x, A) + degree(x, B) is strictly greater than 3 (degree(x, A) means the degree of x in A, counting only internal edges, the ones used in the triangulation).
c. Use (b) to prove that the rotation distance between two BSTs of n > 10 nodes is at most 2n - 6.
Recall the analysis of the splaying algorithm from class in which we defined the the size of node x to be the sum of the weights of the nodes in x's subtree, and defined the rank of x to be the floor of log(size(x)).
Suppose we modify the splaying algorithm so that we only perform the splay step when rank of the current node equals the rank of its grandparent g(x) (assuming g(x) exists), else we simply move up the tree to g(x) and continue the splay from there. So unlike normal splaying, the node accessed does not necessarily end up at the root of the tree.
a. Is the balance theorem still true for this tree?
b. Give and prove an upper bound on the number of rotations that can be performed starting from an initial tree with n nodes, or show that an infinite number of rotations can occur.