Back close

A Short Note on Perfectly Balanced Binary Search Trees

Publication Type : Journal Article

Publisher : The British Computer Society

Source : Comput. J., The British Computer Society, Volume 35, Number 6, p.660-662 (1992)

Url : http://comjnl.oxfordjournals.org/content/35/6/660.abstract?maxtoshow=&hits=10&RESULTFORMAT=&fulltext=A+Short+Note+on+Perfectly+Balanced+Binary+Search+Trees&searchid=1&FIRSTINDEX=0&resourcetype=HWCIT

Campus : Amritapuri

School : Department of Computer Science and Engineering, School of Computing

Department : Computer Science

Year : 1992

Abstract : 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.

Cite this Research Publication : 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

Admissions Apply Now