On the Markov chain for the move-to-root rule for binary search trees. (English) Zbl 0822.60058

Summary: The move-to-root (MTR) heuristic is a self-organizing rule that attempts to keep a binary search tree in near-optimal form. It is a tree analogue of the move-to-front (MTF) scheme for self-organizing lists. Both heuristics can be modeled as Markov chains. We show that the MTR chain can be derived by lumping the MTF chain and give exact formulas for the transition probabilities and stationary distribution for MTR. We also derive the eigenvalues and their multiplicities for MTR.


60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
68P10 Searching and sorting
68P05 Data structures
Full Text: DOI