Self-Organizing Binary Search Trees
Brian Allen, Ian Munro · Journal of the ACM · 1978
Heurlsttcs are considered which attempt to maintain a binary search tree in a near optimal form, assuming that elements are requested with fixed, but unknown, independent probabilities.A "move to root'" heuristic is shown to yield an expected search time within a constant factor of that of an optimal static binary search tree.On the other hand, a closely related "simple exchange" technique is shown not to have this property.The rate of convergence of the move to root heuristic is discussed Also considered is the more general case m whmh elements not in the tree may have nonzero probabihty of being requested.