An insertion algorithm for a minimal internal path length binary search tree. (technical)

An Insertion Algorithm for a Minimal Internal Path Length Binary Search Tree

1. INTRODUCTION Methods that maintain balance in binary search trees have received considerable attention in computer science literature. Since a binary search tree that grows in a random manner will have, on the average, an expected search path lenght of approximately 1.386 log.sub.2.n [8], we can expect an improvement in excess of 25 percent in the search path length if the tree can be kept to a minimum height. The cost of maintaining a tree to achieve optimal or near optimal search performance can be justified if searching is the predominant activity in the tree, with insertions of new keys into the tree being a relatively infrequent activity. The algorithmic strategies that have previously been used to introduce and maintain balance in binary search trees have been either local or global rebalancing strategies.

In the local strategies, a reasonable notion of balance is introduced and the binary tree insertion algorithm is modified to detect a deviation from balance during an insertion and to restore the tree to balance by performing sequences of subtree rotations. The most popular local balancing strategies have been those for AVL, or height balanced, trees [1] and for bounded balance (BB), or weight balanced trees [10]. A recent algorithm performs subtree rotations whenever the total internal path length of the tree is reduced [5].

The global balancing algorithms inspect all of the nodes in a tree in order to reconstruct a balanced tree. The global strategies produce either a perfectly balanced tree [2, 3, 9] or a route balanced tree [4, 11] (i.e., a tree with minimal internal path length). Several global tree balancing algorithms are discussed in [3], including two that adopt parallel procedures.

We introduce a balancing algorithm for binary search trees whose overall performance in terms of the trees produced and the run-time behavior of the algorithm, is between that of the local and global balancing algorithms. The trees produced by this algorithm have minimal internal path length and are balanced with respect to both the number of complete levels and the number of levels in the two subtrees of each node in a tree. In the worst case, this algorithm requires time that is linear in the number of nodes in the tree (i.e., becomes global, in a sense); the worst-case behavior occurs only as the tree comes close to actually being a complete tree. Rather than performing subtree rotations as the local balancing algorithms do, or detachning and reattaching nodes as the global algorithms do, this algorithm maintains its notion of balance by moving key values within the existing tree; if an insertion would introduce imbalance, then keys are …