RATES OF CONVERGENCE FOR THE MOVE-TO-ROOT MARKOV CHAIN 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/1177004825
发表日期：
1995
页码：
20-36
关键词：
摘要：
The move-to-root 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 scheme (also known as the weighted random-to-top card shuffle or Tsetlin library) for self-organizing lists. We study convergence of the move-to-root Markov chain to its stationary distribution and show that move-to-root converges two to four times faster than move-to-front for many examples. We also discuss asymptotics for expected search cost. For equal weights, cn/ ln n steps are necessary and sufficient to drive the maximum relative error to 0.
来源URL：