Weighted height of random trees

DOI10.1007/s00236-008-0069-0zbMath1147.68058OpenAlexW2112729204MaRDI QIDQ934911

Erin McLeish, Nicolas Broutin, Luc P. Devroye

Publication date: 30 July 2008

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00236-008-0069-0

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)

Related Items (5)

Embedding small digraphs and permutations in binary trees and split trees ⋮ The total path length of split trees ⋮ Minima in branching random walks ⋮ A functional limit theorem for the profile of \(b\)-ary trees ⋮ Split trees -- a unifying model for many important random trees of logarithmic height: a brief survey

Uses Software

• PATRICIA
• Quicksort

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Large deviations for a general class of random vectors
• Large deviations for the weighted height of an extended class of trees
• Branching processes in the analysis of the heights of trees
• Large deviation theorems for empirical probability measures
• A fixed point theorem for distributions
• On the expected height of fringe-blanced trees
• A strong law for the height of random binary pyramids
• A note on the growth of random trees
• The contraction method for recursive algorithms
• Partial match queries in relaxed multidimensional search trees
• Dynamical sources in information theory: A general analysis of trie structures
• The growth and spread of the general branching random walk
• A note on growing binary trees
• Ignoring ignorance and agreeing to disagree
• Squarish k-d Trees
• Optimal Sampling Strategies in Quicksort and Quickselect
• Emergence of Scaling in Random Networks
• On Random Binary Trees
• Two Probability Models of Pyramid or Chain Letter Schemes Demonstrating that Their Promotional Claims are Unreliable
• An Analysis of the Height of Tries with Random Weights on the Edges
• On the convergence of supercritical general (C-M-J) branching processes
• A note on the height of binary search trees
• Multidimensional binary search trees used for associative searching
• On Large Deviations from the Invariant Measure
• The asymptotic shape of the branching random walk
• Universal Limit Laws for Depths in Random Trees
• Note on the heights of random recursive trees and random m‐ary search trees
• On the average performance of orthogonal range search in multidimensional data structures
• Probability metrics and recursive algorithms
• The Ubiquitous Digital Tree
• More Combinatorial Properties of Certain Trees
• A Method for the Construction of Minimum-Redundancy Codes
• Convex Analysis
• Increasing the efficiency of quicksort
• File structures using hashing functions
• Algorithms and Computation
• Randomized binary searching with tree structures
• The height of increasing trees
• Quicksort
• Large deviations

This page was built for publication: Weighted height of random trees