Explaining the Behaviour of Binary Search Trees Under Prolonged Updates:
A Model and Simulations
Joseph Culberson and J. Ian Munro
The Computer Journal Vol. 32, No. 1:68-75, 1989.
abstract
In this paper we present an extensive study into the long-term behaviour of
binary search trees subjected to updates using the usual deletion algorithms
taught in introductory textbooks. We develop a model of the behaviour of such
trees which leads us to conjecture that the asymptotic average search path
length is Theta(N^{1/2}). We present results of large simulations
which strongly support this conjecture. However, introducing a simple
modification to ensure symmetry in the algorithms, the model predicts no such
long-term deterioration. Simulations in fact indicate that asymptotically the
average path length of such trees is less than the 1.386...log_2 N
average path length generated from random insertion sequences.
joe@cs.ualberta.ca