| Optimal Rebalancing of Binary Search Trees (1996) | |||||||||||||||||
Abstract | |||||||||||||||||
| We give, for any reasonable function f , a scheme for rebalancing a binary search tree with amortized O(f(n)) work per update while guaranteeing a height bounded by dlog(n + 1) +1=f(n)e for all n. As a corollary, in the semi-dynamic case, height dlog(n+1)e can be guaranteed with amortized O(log n) work per insertion. Both results match existing lower bounds, and hence provide an exact characterization of the amortized cost of rebalancing a binary search tree. 1 Introduction The binary search tree is one of the most fundamental and best studied data structures in computer science. Much research has been centered around rebalancing schemes for keeping low height at a reasonable cost during insertions and deletions, and a multitude of schemes exist for keeping a height of c Delta log(n), 1 for some constant c ? 1, while updating in time O(log n). Examples include AVL-trees [1] with c = 1:44, red-black trees [9] with c = 2, BB(ff)-trees [7, 13] with 2 c 3:45 (depending on ff), and m... | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||