Self-Organizing Binary Search Trees

DOI10.1145/322092.322094zbMath0388.68060OpenAlexW2078589215WikidataQ56066201 ScholiaQ56066201MaRDI QIDQ4170254

J. Ian Munro, Brian M. Allen

Publication date: 1978

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/322092.322094

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Information storage and retrieval of data (68P20) Discrete mathematics in relation to computer science (68R99)

Related Items

Self-Adjusting Binary Search Trees: What Makes Them Tick? ⋮ Compact Difference Bound Matrices ⋮ On top-down splaying ⋮ Amortized Computational Complexity ⋮ Expected Costs in Some Classes of Binary Search Trees ⋮ Optimum multiway search trees ⋮ Determining the mode ⋮ Unnamed Item ⋮ Optimal algorithms for sensitivity analysis in associative multiplication problems ⋮ Randomly balanced binary trees ⋮ Smooth Heaps and a Dual View of Self-Adjusting Data Structures ⋮ Unnamed Item ⋮ The move-to-root rule for self-organizing trees with Markov dependent requests^∗ ⋮ Chain-splay trees, or, how to achieve and prove \(\log \log N\)-competitiveness by splaying ⋮ Optimal binary search trees ⋮ In Pursuit of the Dynamic Optimality Conjecture