Technical Report TR94-09 Abstract

Asymmetry in Binary Search Tree Update Algorithms

Joseph C. Culberson and Patricia A. Evans

Date: May 1994

University of Alberta Computing Science Technical Report TR94-09

Abstract

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.

TR 94-09 (postscript)

It can also be retrieved by anonymous ftp ftp.cs.ualberta.ca pub/TechReports

Queries: email joe@cs.ualberta.ca or pevans@cs.uvic.ca

Joseph Culberson

May 17,1994