On the Markov chain for the move-to-root rule for binary search trees

DOI10.1214/aoap/1177004824zbMath0822.60058OpenAlexW1976674167MaRDI QIDQ1894612

Robert P. Dobrow, James Allen Fill

Publication date: 10 August 1995

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1214/aoap/1177004824

zbMATH Keywords

Markov chainseigenvaluesbinary search treeslumpingmove-to-front rulemove-to-root ruleself-organizing searchsimple exchange

Mathematics Subject Classification ID

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

Related Items

The normal distribution is \(\boxplus\)-infinitely divisible, Unnamed Item, Markov chains, ${\mathscr R}$-trivial monoids and representation theory, Dyck path enumeration