mwang@watmath.UUCP (mwang) (07/15/85)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
ESSAY PRESENTATION
- Wednesday, July 17, 1985.
Miss Shya-yun Mao of the Computer Science Department,
will speak on ``Reorganization Heuristics for Search
Trees with Uniform Access Frequencies.''
TIME: 2:30 PM
ROOM: MC 6091A
ABSTRACT
This talk explores the performance of different heuris-
tic rules for dynamically reorganizing binary search
trees under the assumption that every node has the same
access probability, Three algorithms are presented and
analyzed. Two of these shift the accessed node to the
root; the third one shifts it up one level. The
results show that moving the node to the root is the
best heuristic rule. The ``simple'' move-to-root rule
does not affect the probability distribution of trees,
but the other two result in a worse probability distri-
bution. The effect of partial shifts between the ac-
cessed node and the root is also discussed; the ``sim-
ple'' move-to-root rule is still the best heuristic.