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.