The analysis of a fringe heuristic for binary search trees
From MaRDI portal
Publication:3696534
DOI10.1016/0196-6774(85)90003-3zbMath0576.68052OpenAlexW2087284534MaRDI QIDQ3696534
J. Ian Munro, Patricio V. Poblete
Publication date: 1985
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0196-6774(85)90003-3
Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Information storage and retrieval of data (68P20)
Related Items (18)
On rotations in fringe-balanced binary trees ⋮ Gkd-trees: Binary trees that combine multi-dimensional data handling, node size and fringe reorganization ⋮ Fringe analysis for extquick: An in situ distributive external sorting algorithm ⋮ Some average measures in m-ary search trees ⋮ Central limit theorems for urn models ⋮ Balancing \(m\)-ary search trees with compressions on the fringe ⋮ Height balance distribution of search trees ⋮ Probabilistic analysis of bucket recursive trees ⋮ Unbalanced multiway trees improved by partial expansions ⋮ Optimal binary search trees ⋮ Limit laws for local counters in random binary search trees ⋮ An almost sure result for path lengths in binary search trees ⋮ Transforming unbalanced multiway trees into a practical external data structure ⋮ Universal Limit Laws for Depths in Random Trees ⋮ Two Applications of Urn Processes The Fringe Analysis of Search Trees and The Simulation of Quasi-Stationary Distributions of Markov Chains ⋮ An analytic approach for the analysis of rotations in fringe-balanced binary search trees ⋮ The analysis of heuristics for search trees ⋮ On the expected height of fringe-blanced trees
This page was built for publication: The analysis of a fringe heuristic for binary search trees
