Rates of convergence for the move-to-root Markov chain for binary search trees

DOI10.1214/aoap/1177004825zbMath0822.60059OpenAlexW2062191336MaRDI QIDQ1894613

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/1177004825

zbMATH Keywords

Markov chainsbinary search treesconvergence to stationaritymove-to-front rulemove-to-root ruleself-organizing search

Mathematics Subject Classification ID

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

Related Items (2)

Limits and rates of convergence for the distribution of search cost under the move-to-front rule ⋮ Unnamed Item

This page was built for publication: Rates of convergence for the move-to-root Markov chain for binary search trees