ON THE MARKOV CHAIN FOR THE MOVE-TO-ROOT RULE FOR BINARY SEARCH TREES
成果类型：
Article
署名作者：
Dobrow, Robert P.; Fill, James Allen
署名单位：
Johns Hopkins University; National Institute of Standards & Technology (NIST) - USA
刊物名称：
ANNALS OF APPLIED PROBABILITY
ISSN/ISSBN：
1050-5164
DOI：
10.1214/aoap/1177004824
发表日期：
1995
页码：
1-19
关键词：
摘要：
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.