Optimum lopsided binary trees
Sanjiv Kapoor, Edward M. Reingold · Journal of the ACM · 1989
Binary search trees with costs α and β, respectively, on the left and right edges (lopsided search trees) are considered. The exact shape, minimum worst-case cost, and minimum average cost of lopsided trees ofninternal nodes are determined for nonnegative α and β; the costs are both roughly logp(n+ 1) wherepis the unique real number in the interval (1. 2] satisfying 1/pα+ 1/pβ= 1. Search procedures are given that come within a small additive constant of the lower bounds. Almost-optimum algorithms for the lopsided case of unbounded searching are also obtained. Some extensions to nonconstant costs are briefly sketched.