The move-to-root rule for self-organizing trees with Markov dependent requests∗
Stochastic Analysis and Applications · 1996
The move-to-root (MTR) heuristic is a self-organizing rule which attempts to keep a binary search tree in near-optimal form. It is a tree analogue of the well-studied move-to-front (MTF) scheme. We study a Markov move-to-root (MMTR) model, where the sequence of record requests is a Markov chain, and analyze several characteristics of the tree chain, including the stationary distribution, eigenvalues, and stationary expected search cost