Extremal cost binary trees
Helen Cameron · 1992
This thesis is concerned with the performance of various classes of binary search trees under different cost measures. We examine the path length of binary trees, balance in AVL trees, and the path length of red-black trees. We provide characterizations of the binary trees with the maximum path length among all binary trees with a given height (the length of a longest root-to-leaf path), size (the number of nodes), and fringe thickness (the difference between the height and the length of a shortest root-to-leaf path). These results provide bounds on the path length of binary trees whose path lengths fall between the (known) bounds of $\Omega(N\log\sb2 N)$ and $O(N\sp2)$ for binary trees of size N. Next, we examine the numbers of critical nodes in AVL trees, where a node is critical if its two subtrees have different heights. We characterize a family of AVL trees of a given height and size that have the maximum numbers of critical nodes. Using a correspondence between AVL trees and brother trees, we obtain the characterization via a family of brother trees with the largest space costs for their heights and numbers of nodes. Finally, we examine the path length of red-black trees. We show that the internal path length of a red-black tree of size N is bounded above by $2N(\log\sb2N\log\sb2\log\sb2N) - O(N)$ and that this bound is tight by introducing a class of red-black trees, the C(k,h) trees, that asymptotically achieve the bound.