Analysis of the Standard Deletion Algorithms in Exact Fit Domain Binary
Search Trees
Joseph Culberson and J. Ian Munro
Algorithmica Vol. 5:295-311, 1990.
Abstract
It is well known that the expected search time in an N
node binary search generated by a random sequence of insertions is
O(log N). Little has been published about the asymptotic cost when
insertions and deletions are made following the usual algorithms with no
attempt to retain balance. We show that after a sufficient number of updates,
each consisting of choosing an element at random, removing it, and reinserting
the same value, that the average search cost is Theta (N^{1/2}).
joe@cs.ualberta.ca