Summary. We discuss two simple strategies for constructing binary search trees: "Place the most frequently occurring name at the root of the tree, then proceed similary on the subtrees "and" choose the root so as to equalize the total weight of the left and right subtrees as much as possible, then proceed similarly on the subtres." While the former rule may yield extremely inefficient search trees, the latter rule always produces nearly optimal trees. "One of the popular methods for retrieving information by its 'name' is to store the names in a binary tree. We are given n names B1, B~ ..... /3, and 2n+ t frequencies fll ..... ft., ~o ..... c% with ~.flt+~ :r t, Here fit is the frequency of encountering name B t, and 0r i is the frequency of encountering a name wich lies between B i and Bi+ 1, cr o and 0% have obvious interpretations" [4] . We may always assume w.l.o.g, that fli+~i+fli+l =~0 for all i. Otherwise, the i-th (or the (i+t)-th) key might as well be removed. A binary search tree T is a tree with n interior nodes (nodes having two sons), which we denote by circles, and n+ t leaves, which we denote by squares. The interior nodes are labelled by the Bi in increasing order from left to right and the leaves are labelled by the intervals (Bi, Bi+l) in increasing order from left to right. Let b t be the distance of interior node B i from the root and let a t be the distance of leaf (Bi, Bi+t) from the root. To retrieve a name X, bt+ 1 comparisons are needed if X= B i and a t comparisons are required if B i < X < Bi+ 1. Therefore we define the weighted path length of tree T as: Knuth [4] gives an algorithm for constructing an optimum binary search tree, i.e. a tree with minimal weighted path length. His algorithm has 0 (n ~) time complexity and 0 (n ~) space complexity. This is prohibitive for most applications. He also describes two rules of thumb for constructing binary search trees, both of which can be implemented in 0 (n log n) time and 0 (n) space (in the appendix we sketch such an implementation). Recently M. Fredman [t] improved on this and exhibited an algorithm which works in 0 (n) units of time and space. Rule I : Place the most frequently occurring name at the root of the tree, then proceed similary on the subtrees. Rule II : Choose the root so as to equalize the total weight of the left and right subtrees as much as possible, then proceed similarly on the subtrees.
Kurt Mehlhorn obtained a faster, O(n) time algorithm, which approximates the optimal tree REF .
Nearly optimal binary search trees
Acta Informatica
Acta Informatica
Computer Science Mathematics