To search, Click below search items. |
| All Published Papers Search Service |
|
|
|
Title |
Binary Search Tree Balancing Methods: A Critical Study |
|
Author |
Suri Pushpa, Prasad Vinod |
| Citation |
Vol. 7 No. 8 pp. 237-243 |
|
Abstract |
Binary search tree is a best-suited data structure for data storage and retrieval when entire tree could be accommodated in the primary memory. However, this is true only when the tree is height-balanced. Lesser the height faster the search will be. Despite of the wide popularity of Binary search trees there has been a major concern to maintain the tree in proper shape. In worst case, a binary search tree may reduce to a linear link list, thereby reducing search to be sequential. Unfortunately, structure of the tree depends on nature of input. If input keys are not in random order the tree will become higher and higher on one side. In addition to that, the tree may become unbalanced after a series of operations like insertions and deletions. To maintain the tree in optimal shape many algorithms have been presented over the years. Most of the algorithms are static in nature as they take a whole binary search tree as input to create a balanced version of the tree. In this paper, few techniques have been discussed and analyzed in terms of time and space requirement. |
|
Keywords |
Binary Search Tree, Tree Balancing, Dynamic Balancing, Static Balancing |
|
URL |
