Binary Search Trees
This research is all
concerned with the development of an analysis and simulations of the effect of
mixed deletions and insertions in binary search trees. Previously it was
believed
that the average depth of a node in a tree subjected to updates was decreased
towards an optimal O(log n) when using the
usual algorithms (See e.g. Knuth Vol. 3 [8] )
This was supported to some extent by a complete analysis for trees of only
three nodes by Jonassen and Knuth [7] in 1978.
Eppinger [6] performed some simulations showing that this
was likely false, and conjectured, based on the experimental evidence, that
the depth grew as O(log^3 n),
but offered no analysis or explanation as to why
this should occur. Essentially, this problem concerning
one of the most widely used data structures had remained open for 20 years.
Both my MSc [1] and Ph.D. [2]
focused on this problem.
This research indicates that in fact the depth grows as O(n^{1/2}).
A proof under certain simplifying assumptions was given in the theoretical
analysis in Algorithmica [3],
while a set of simulations was presented together with a
less formal analysis of the more general case,
in the Computer Journal [4] ,
intended for a wider audience.
A complete analysis for the most general case is still open.
More recently P. Evans [5]
has demonstrated that asymmetry may be even more
dangerous in smaller doses! Algorithms with only occasional asymmetric moves
tend to develop trees with larger skews, although the effects take much
longer.
Publications
- Joseph Culberson.
Updating Binary Trees. MSc Thesis, University of Waterloo
Department of Computer Science, 1984.
(Available as Waterloo Research Report CS-84-08.)
Abstract
- Joseph Culberson.
The Effect of Asymmetric Deletions on Binary Search Trees.
Ph. D. Thesis University of Waterloo Department of Computer Science,
May 1986.
(Available as Waterloo Research Report CS-86-15.)
Abstract
- Joseph Culberson J. Ian Munro.
Analysis of the standard deletion algorithms in exact fit domain
binary search trees.
Algorithmica, vol 6, 295-311, 1990.
Abstract
- Joseph Culberson J. Ian Munro.
Explaining the behavior of binary search trees under prolonged
updates: A model and simulations.
The Computer Journal, vol 32(1), 68-75, February 1989.
Abstract
- Joseph C. Culberson and Patricia A. Evans
Asymmetry in Binary Search Tree Update Algorithms
Technical Report TR94-09
Other References
- Jeffery L. Eppinger. An empirical study of insertion and deletion
in binary trees. Communications of the ACM
vol. 26, September 1983.
- Arne T. Jonassen and Donald E. Knuth
A trivial algorithm whose analysis isn't.
Journal of Computer and System Sciences,
16:301-322, 1978.
- D. E. Knuth Sorting and Searching Volume III,
The Art of Computer Programming
Addison-Wesley Publishing Company,
Inc., Reading, Massachusetts, 1973.
Joseph Culberson
May 10, 1994