AbstractThe most important methods for balancing search trees are periodical rebuilding of the whole tree, which takes Omega(N) time, and rebalancing the tree during each update operation, in O(log N) time. Recently, a new method called relaxed balancing has been proposed in which balancing and updates are uncoupled. Updates only leave balance information in the tree, thus enabling rebalancing later. In this paper, new algorithms for updating and rebalancing the tree, based on using the relaxed balance information, are given. It is shown that if M up-dates are performed in a red-black tree with N keys, the tree can be rebalanced in O(M log (N + M)) time. If the tree is originally empty, the rebalancing is performed in O(M) time.
Categories and Subject Descriptors: E.1 [Data Structures]; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; G.2.2 [Discrete Mathematics]: Graph Theory
Additional Key Words and Phrases: algorithms, balanced trees, data structures
Selected references
- Rudolf Bayer. Symmetric binary B-trees: Data structure and maintenance algorithms. Acta Informatica, 1:290-306, 1972.
- Rudolf Bayer and Edward M. McCreight. Organization and maintenance of large ordered indices. Acta Informatica, 1:173-189, 1972.
- Joan Boyar and Kim S. Larsen. Efficient rebalancing of chromatic search trees. Journal of Computer and System Sciences, 49(3):667-682, December 1994.
- Douglas Comer. The ubiquitous B-tree. ACM Computing Surveys, 11(2):121-137, June 1979.
- Leo J. Guibas and Robert Sedgewick. A dichromatic framework for balanced trees. In 19th Annual Symposium on Foundations of Computer Science, pages 8-21, Ann Arbor, Michigan, 16-18 October 1978. IEEE.
- J. Nievergelt and E. M. Reingold. Binary search trees of bounded balance. SIAM Journal on Computing, 2(1):33-43, March 1973.
- Otto Nurmi and Eljas Soisalon-Soininen. Uncoupling updating and rebalancing in chromatic binary search trees. In Proceedings of the Tenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 192-198, Denver, Colorado, 29-31 May 1991.
- Daniel Dominic Sleator and Robert Endre Tarjan. Self-adjusting binary search trees. Journal of the ACM, 32(3):652-686, July 1985.