To search, Click below search items. |
| All Published Papers Search Service |
|
|
|
Title |
Insertion and Deletion on Binary Search Tree using Modified Insert Delete Pair: An Empirical Study |
|
Author |
Suri Pushpa, Prasad Vinod, Jilani Abdul Khader |
| Citation |
Vol. 7 No. 12 pp. 269-272 |
|
Abstract |
Recently, a new version of the insert-delete pair has been proposed that maintains a random binary search tree in such a way that all the grandparents in the tree always have both of their sub-trees full. For a tree with ‘n’ nodes, if such an arrangement is made, it is straightforward that even an arbitrary sequence of insertion and deletion would not cause the tree to grow beyond n/2. Compare this with conventional insert delete algorithms where a tree may grow up to the height of n-1 reducing search to be sequential. Lesser the height of the tree, lesser would be its internal path-length, and hence faster the search would be. To study the behavior of the Binary Search tree with proposed insert delete pair, we have simulated a binary search tree with 1024 nodes. In this article we provide some empirical results to show that the proposed insert-delete pair maintains the tree in better shape, with considerable reduction in the internal path-length. |
|
Keywords |
Tree Balancing, Binary Search Tree, Tree Path-Length |
|
URL |
