Skip to search boxSkip to navigationSkip to main content

Maintaining a random binary search tree dynamically

  • Prasad Vinod
    ,
  • Suri Pushpa
    ,
  • Carsten Maple
Research Output:
Chapter in Book/Report/Conference proceeding
Conference contribution
 Peer-review

Abstract

Binary tree is a graph, without cycle, that is frequently used in computer science for fast data access and retrieval. To ensure faster insertion and deletion, the tree height has to be kept to a minimum. A random tree starts losing its randomness after a series of insertions and deletions and, in the worst case, a tree with n nodes, could grow up to the height of n - 1. In this paper, we present modified insertion and deletion algorithms to maintain the tree in better shape dynamically. Without applying any complex rebalancing technique, or using considerable amount of space, both algorithms maintain the tree in such a way that even a series of insertions and asymmetric deletions do not cause the tree to grow beyond n/2. A comparative study of traditional and modified insert algorithms shows that for random input, the modified insert algorithm produces a tree with 20% to 30% reduction in height, forcing the average number of comparisons required for a successful search to go down by 15% to 20%.

Publication Information

Output type

Research Output:
Chapter in Book/Report/Conference proceeding
Conference contribution
 Peer-review

Original language

English

Publication milestones

  • Published - 01/01/2006

Publication status

Published - 01/01/2006

Publisher

Institute of Electrical and Electronics Engineers Inc., United States

Publication IDs

  • handle.net: 10547/270916
  • Scopus: 45149098565

Host publication title

nan

Access to documents

Publication metrics