ALCOMFT-TR-01-167

Salvador Roura
A New Method for Balancing Binary Search Trees
Barcelona. Work package 4. June 2001.

Abstract: A new balancing method for binary search trees is presented, which achieves logarithmic worst-case cost on searches and updates. The method uses the sizes of the subtrees as balancing information; therefore operations by rank are efficiently performed without any changes in the data structure. Compared to weighted binary search trees, which also achieve logarithmic worst-case cost by making use of the sizes of the subtrees, the operations involved with our method are likely to be less costly in most real situations.

Postscript file: ALCOMFT-TR-01-167.ps.gz (65 kb).