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.
Efficient algorithms to globally balance a binary search tree
The Latest from CACM
Shape the Future of Computing
ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.
Get InvolvedCommunications of the ACM (CACM) is now a fully Open Access publication.
By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.
Learn More
Join the Discussion (0)
Become a Member or Sign In to Post a Comment