We present a perfect balancing method for a binary search tree. During the updates the algorithm allows the structure to grow gracefully and maintains the optimal shape without degeneration. The algorithm uses swapping as the basic operation. Since the tree produced by the algorithm is optimal it can favourably be compared with that produced by other balancing algorithms. In worst case situation, the algorithm takes O(n) time, n being the total number of nodes in the tree. This is an added significance when it is compared with the static optimal binary search trees.
A. P. Korah and Dr. Kaimal, M. R., “A Short Note on Perfectly Balanced Binary Search Trees”, Comput. J., vol. 35, pp. 660-662, 1992.