Asymmetry in Binary Search Tree Update Algorithms

• Author(s) / Creator(s)

  • Culberson, Joseph
  • Evans, Patricia

• Technical report TR94-09. 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. | TRID-ID TR94-09

• Date created

  1994

• Subjects / Keywords

  • Deletion algorithms
  • IPL
  • Binary search trees
  • Asymmetries

• Type of Item

  Report

• DOI

  https://doi.org/10.7939/R3Z31NV6X

• License

  Attribution 3.0 International