Efficient algorithms to globally balance a binary search tree
- 1 July 1984
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 27 (7) , 695-702
- https://doi.org/10.1145/358105.358191
Abstract
A binary search tree can be globally balanced by readjustment of pointers or with a sorting process in O ( n ) time, n being the total number of nodes. This paper presents three global balancing algorithms, one of which uses folding with the other two adopting parallel procedures. These algorithms show improvement in time efficiency over some sequential algorithms [1, 2, 7] when applied to large binary search trees. A comparison of various algorithms is presented.Keywords
This publication has 3 references indexed in Scilit:
- Efficient algorithms to create and maintain balanced and threaded binary search treesSoftware: Practice and Experience, 1985
- Multidimensional binary search trees used for associative searchingCommunications of the ACM, 1975
- Optimizing binary trees grown with a sorting algorithmCommunications of the ACM, 1972