Maintaining a random binary search tree dynamically

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%.