Asymmetry in Binary Search Tree Update Algorithms
Joseph C. Culberson, Evans, Patricia · 1994
In this paper we explore the relationship between asymmetries in deletion algorithms used in updating binary search trees, and the resulting long term behavior of the search trees. We show that even what would appear to be negligible asymmetric effects accumulate to cause long term degeneration. This persists even in the face of other effects that would appear to counteract the long term effects. On the other hand, eliminating the asymmetry completely seems to give us trees that have a smaller IPL than is expected for trees built by a random sequence of insertions. But even then there are surprises in that the backbone becomes longer than expected. 1 Introduction Binary search trees are one of the oldest and most frequently used data structures for solving the dictionary and other problems [2, 11, 6, 9]. The average case efficiency of these structures has been well studied, when only insertions are involved. The usual insertion algorithm simply inserts new values at the leaf...