Analysis of the space of search trees under the random insertion algorithm
From MaRDI portal
Publication:4203825
DOI10.1016/0196-6774(89)90023-0zbMath0685.68060OpenAlexW1978795682MaRDI QIDQ4203825
Hosam M. Mahmoud, Boris G. Pittel
Publication date: 1989
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0196-6774(89)90023-0
Related Items (21)
Multivariate normal limit laws for the numbers of fringe subtrees in \(m\)-ary search trees and preferential attachment trees ⋮ (Un)expected path lengths of asymmetric binary search trees ⋮ Second phase changes in random \(m\)-ary search trees and generalized quicksort: Convergence rates ⋮ Unnamed Item ⋮ The asymptotic distribution of cluster sizes for supercritical percolation on random split trees ⋮ DEGREE PROFILE OF m-ARY SEARCH TREES: A VEHICLE FOR DATA STRUCTURE COMPRESSION ⋮ Balancing \(m\)-ary search trees with compressions on the fringe ⋮ Quad-\(k\mathrm d\) trees: a general framework for \(k\mathrm d\) trees and quad trees ⋮ A general limit theorem for recursive algorithms and combinatorial structures ⋮ A weakly 1-stable distribution for the number of random records and cuttings in split trees ⋮ Probabilistic analysis of bucket recursive trees ⋮ The size of random fragmentation trees ⋮ Page usage in a quadtree index ⋮ The total path length of split trees ⋮ The fluctuations of the giant cluster for percolation on random split trees ⋮ Dependence and phase changes in random m‐ary search trees ⋮ Phase changes in randomm-ary search trees and generalized quicksort ⋮ Multiway Trees of Maximum and Minimum Probability under the Random Permutation Model ⋮ Inversions in Split Trees and Conditional Galton–Watson Trees ⋮ Normal convergence problem? Two moments and a recurrence may be the clues ⋮ Functional limit theorems for multitype branching processes and generalized Pólya urns.
This page was built for publication: Analysis of the space of search trees under the random insertion algorithm
