6.851 Advanced Data Structures, Spring 2010
Erik D. Demaine, André Schulz · 2010
Homework is subject to a one-page-in, one-page-out rule; that is, assignments will be kept to one page, but you may only turn in a single page in response. Your single page must be typeset with L ATEX. A template is available on the course website. 2 Overview Today’s topic is the question of dynamic optimality; that is, of whether there is a single “best” binary search tree. (A more rigorous definition of “best ” follows.) 3 Binary search trees The binary search tree is typically viewed as a comparison data structure: smaller things are placed to the left, and larger things are placed to the right. However, the binary search tree can also be treated as a model of computation. This model defines several unit-cost operations. From a given position in the tree, it takes O(1) time to walk to either the left or right child, to walk to the parent, or to rotate a node and its parent. (Rotation is a simple tree operation in which a node x takes the place of its parent y, with y becoming a child of x. The two subtrees of x and the other subtree of y are redistributed such that the structure of the binary search tree is preserved.)