On the Most Probable Shape of a Search Tree Grown from a Random Permutation
From MaRDI portal
Publication:3310623
DOI10.1137/0605010zbMath0529.05002OpenAlexW2069347409MaRDI QIDQ3310623
Hosam M. Mahmoud, Boris G. Pittel
Publication date: 1984
Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0605010
Trees (05C05) Searching and sorting (68P10) Permutations, words, matrices (05A05) Combinatorial probability (60C05)
Related Items
On growing random binary trees, Random sequential bisection and its associated binary tree, 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, On the joint distribution of the insertion path length and the number of comparisons in search trees, Second phase changes in random \(m\)-ary search trees and generalized quicksort: Convergence rates, Limit laws for local counters in random binary search trees, Width and mode of the profile for some random trees of logarithmic height, On weighted depths in random binary search trees, On a random search tree: asymptotic enumeration of vertices by distance from leaves, The properties of random trees, Limiting probabilities for vertices of a given rank in 1-2 trees, Universal Limit Laws for Depths in Random Trees, EXTREMAL WEIGHTED PATH LENGTHS IN RANDOM BINARY SEARCH TREES, On the average internal path length of m-ary search trees
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On growing random binary trees
- Limiting behavior of a process of runs
- The average height of binary trees and other simple trees
- Subadditive ergodic theory
- On the Average Shape of Binary Trees
- More Combinatorial Properties of Certain Trees
- On the height of trees
- On the Distribution of the Number of Vertices in Strata of a Random Tree
