The analysis of a fringe heuristic for binary search trees

DOI10.1016/0196-6774(85)90003-3MaRDI QIDQ3696534zbMATH OpenOpenAlexFDO

Authors Patricio V. Poblete, J. Ian Munro

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

zbMATH Keywords

searching

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Information storage and retrieval of data (68P20) Graph theory (including graph drawing) in computer science (68R10)

Cited in

(19)

• Some average measures in m-ary search trees
• Height balance distribution of search trees
• Unbalanced multiway trees improved by partial expansions
• 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
• Central limit theorems for urn models
• Transforming unbalanced multiway trees into a practical external data structure
• Fringe analysis for extquick: An in situ distributive external sorting algorithm
• On rotations in fringe-balanced binary trees
• Limit laws for local counters in random binary search trees
• Two Applications of Urn Processes The Fringe Analysis of Search Trees and The Simulation of Quasi-Stationary Distributions of Markov Chains
• Universal Limit Laws for Depths in Random Trees
• An almost sure result for path lengths in binary search trees
• Improved search heuristics for the sa-tree
• Gkd-trees: Binary trees that combine multi-dimensional data handling, node size and fringe reorganization
• Optimal binary search trees
• Balancing \(m\)-ary search trees with compressions on the fringe
• Probabilistic analysis of bucket recursive trees

This page was built for publication: The analysis of a fringe heuristic for binary search trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3696534)