On growing random binary trees

DOI10.1016/0022-247X(84)90141-0zbMath0593.60014MaRDI QIDQ1076401

Boris G. Pittel

Publication date: 1984

Published in: Journal of Mathematical Analysis and Applications (Search for Journal in Brave)

zbMATH Keywords

random binary trees; nested binary trees

Mathematics Subject Classification ID

05C05: Trees

60K35: Interacting random processes; statistical mechanics type models; percolation theory

60C05: Combinatorial probability

68W99: Algorithms in computer science

Related Items

On random cartesian trees, Note on the heights of random recursive trees and random m‐ary search trees, On Random Generation of the Symmetric Group, The variance of the height of binary search trees, On Robson's convergence and boundedness conjectures concerning the height of binary search trees, Random sequential bisection and its associated binary tree, A diffusion limit for a class of randomly-growing binary 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, On the expected height of fringe-blanced trees, A note on the growth of random trees, The properties of random trees, The height of a binary search tree: the limiting distribution perspective., Smoothed analysis of binary search trees, Martingales and large deviations for binary search trees, On the Most Probable Shape of a Search Tree Grown from a Random Permutation, Limit laws for local counters in random binary search trees, EXTREMAL WEIGHTED PATH LENGTHS IN RANDOM BINARY SEARCH TREES, Universal Limit Laws for Depths in Random Trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Limiting behavior of a process of runs
• Postulates for subadditive processes
• Subadditive ergodic theory
• Asymptotic Development of the Stirling Numbers of the First Kind
• On the Most Probable Shape of a Search Tree Grown from a Random Permutation
• On the Average Shape of Binary Trees
• Percolation Processes and Related Topics
• 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
• A Minimax Analogue of the Weak Law of Large Numbers