A note on the height of binary search trees
From MaRDI portal
Publication:3990603
DOI10.1145/5925.5930zbMath0741.05062OpenAlexW2048858877WikidataQ56688553 ScholiaQ56688553MaRDI QIDQ3990603
Publication date: 28 June 1992
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/5925.5930
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Searching and sorting (68P10) Random graphs (graph-theoretic aspects) (05C80) Parallel algorithms in computer science (68W10) Data structures (68P05)
Related Items
Behavior near the extinction time in self-similar fragmentations. II: Finite dislocation measures., Partition Functions of Discrete Coalescents: From Cayley’s Formula to Frieze’s ζ(3) Limit Theorem, A note on the Horton-Strahler number for random binary search trees, Longest Path Distance in Random Circuits, Average case analysis for tree labelling schemes, Smoothed analysis of binary search trees, Random sequential bisection and its associated binary tree, Average-case analysis of quicksort and binary insertion tree height using incompressibility, Depth Properties of scaled attachment random recursive trees, On random cartesian trees, Note on the heights of random recursive trees and random m‐ary search trees, Applications of the theory of records in the study of random trees, Analytic methods in asymptotic enumeration, On the concentration of the height of binary search trees, A note on the growth of random trees, An Improved Bound for Random Binary Search Trees with Concurrent Insertions, Randomized search trees, Fast error-tolerant quartet phylogeny algorithms, Hypergeometrics and the cost structure of quadtrees, Retracted: Strong limiting behavior in binary search trees, The height of record‐biased trees, The effects of semantic simplifications on random \textit{BST}-like expression-trees, DEGREE-BASED GINI INDEX FOR GRAPHS, Zip-zip trees: making zip trees more balanced, biased, compact, or persistent, Long and short paths in uniform random recursive dags, General Edgeworth expansions with applications to profiles of random trees, Erasure-Resilient Property Testing, On the Most Likely Voronoi Diagram and Nearest Neighbor Searching, Maximal flow in branching trees and binary search trees, Search trees: metric aspects and strong limit theorems, Weighted height of random trees, The height of increasing trees, Random binary trees: from the average case analysis to the asymptotics of distributions, Unnamed Item, Efficient algorithms for parallel sorting on mesh multicomputers, Martingales and large deviations for binary search trees, Average-case analysis on simple families of trees using a balanced probability model, Limiting theorems for the nodes in binary search trees, Scaling limits of Markov branching trees with applications to Galton-Watson and random unordered trees, D?E?K=(1000)8, Optimal binary search trees, On Robson's convergence and boundedness conjectures concerning the height of binary search trees, Uniform distribution modulo one and binary search trees, On the silhouette of binary search trees, Limit laws for local counters in random binary search trees, A functional limit theorem for the profile of \(b\)-ary trees, Unnamed Item, Random Records and Cuttings in Binary Search Trees, The variance of the height of binary search trees, On weighted depths in random binary search trees, On the internal path length ofd-dimensional quad trees, An almost sure result for path lengths in binary search trees, Optimal parallel quicksort on EREW PRAM, The height of Mallows trees, On the Lambert \(w\) function, Split trees -- a unifying model for many important random trees of logarithmic height: a brief survey, A phase transition for the heights of a fragmentation tree, One-sided variations on interval trees, On a random search tree: asymptotic enumeration of vertices by distance from leaves, The properties of random trees, The variance of the average depth of a pure birth process converges to 7, Universal Limit Laws for Depths in Random Trees, Correction terms for the height of weighted recursive trees, Search problems in groups and branching processes, Towards convergence rate analysis of random forests for classification, EXTREMAL WEIGHTED PATH LENGTHS IN RANDOM BINARY SEARCH TREES, The height of random k‐trees and related branching processes, The height of a binary search tree: the limiting distribution perspective., Extreme value statistics and traveling fronts: Various applications, Constant bounds on the moments of the height of binary search trees, On the expected height of fringe-blanced trees
