Efficient algorithms to globally balance a binary search tree
Hsi Chang, S. Sitharama Iyangar · Communications of the ACM · 1984
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.