A Short Note on Perfectly Balanced Binary Search Trees | Zendy

A. P. Korah | Zendy; M. R. Kaimal | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

A Short Note on Perfectly Balanced Binary Search Trees

Author(s) -

A. P. Korah,

M. R. Kaimal

Publication year - 1992

Publication title -

the computer journal

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.319

H-Index - 64

eISSN - 1460-2067

pISSN - 0010-4620

DOI - 10.1093/comjnl/35.6.660

Subject(s) - optimal binary search tree , binary search tree , binary tree , computer science , self balancing binary search tree , tree (set theory) , binary number , algorithm , binary search algorithm , random binary tree , tree traversal , search tree , search algorithm , interval tree , mathematical optimization , mathematics , tree structure , combinatorics , arithmetic

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 used 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

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research