© 1991 by British Computer Society
Weighting Without Waiting: the Weighted Path Length Tree
Computing Science Department, Glasgow University, Glasgow, G12 8QQ, UK
Over the years, much attention has been focused on algorithms to construct efficient binary search trees. There are three general philosophies: use the ordinary binary tree algorithm; devise a balance criterion to guarantee an upper of bound of 
(log n) on the time per operation; use a restructuring heuristic which guarantees an amortised complexity over a sequence of operations. If the access distribution of the keys is not equiprobable then the solutions in these categories are to date, respectively, naive, misguided and impractical. Instead we derive a solution to this problem by careful examination of the properties of a common transformation on trees, the rotation. Our algorithm is more general than Gonnet's balanced tree4 based on internal path length reduction as it can cope with weighted data. The resulting algorithm performs a rotation only when it is guaranteed to improve the weighted path length of the tree and thus the search time. Consequently we call the resulting data structure the Weighted Path Length (wpl) tree. The algorithm is as simple as that for any balanced binary tree whilst the tree structure produced appears to be very close to optimal. We substantiate these claims by presenting a simple derivation of the algorithm, a proof of the upper bound on the number of rotations performed, and the results of several simulations. By analogy with a result of Gonnet for the path length tree, we hypothesise that the weighted path length of our tree is always within a constant factor of the optimal.
Received November 1990. revised April 1991.
* Computing Science Department, Glasgow University, Glasgow, G12 8QQ, United Kingdom.