The left-right-imbalance of binary search trees

DOI10.1016/J.TCS.2006.10.033MaRDI QIDQ868958zbMATH OpenOpenAlexFDO

Authors Markus Kuba, Alois Panholzer

Publication date 26 February 2007

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2006.10.033

zbMATH Keywords

imbalancelimiting distributionbinary search trees

Mathematics Subject Classification ID

Trees (05C05) Data structures (68P05) Combinatorial probability (60C05)

Recommendations

• Left and right pathlengths in random binary trees
• Left and right length of paths in binary trees or on a question of Knuth
• Left and right length of paths in binary trees
• scientific article; zbMATH DE number 852055
• Distribution of distances in random binary search trees.

Cites work

• scientific article; zbMATH DE number 3863589 (Why is no real title available?)
• scientific article; zbMATH DE number 4041254 (Why is no real title available?)
• scientific article; zbMATH DE number 53861 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3560401 (Why is no real title available?)
• scientific article; zbMATH DE number 718142 (Why is no real title available?)
• scientific article; zbMATH DE number 815575 (Why is no real title available?)
• A Note on the Theory of Moment Generating Functions
• A general limit theorem for recursive algorithms and combinatorial structures
• A limit theorem for “quicksort”
• Applications of the theory of records in the study of random trees
• Binary Trees, Left and Right Paths, WKB Expansions, and Painlevé Transcendents
• Distances and Finger Search in Random Binary Search Trees
• Exact and asymptotic distributions in digital and binary search trees
• Left and right pathlengths in random binary trees
• Limit laws for embedded trees: Applications to the integrated superBrownian excursion
• Mixed Poisson approximation of node depth distributions in random binary search trees
• On convergence rates in the central limit theorems for combinatorial structures
• On the analysis of stochastic divide and conquer algorithms
• Phase Change of Limit Laws in the Quicksort Recurrence under Varying Toll Functions
• Poisson approximations for functionals of random trees
• Singularity Analysis of Generating Functions
• Singularity analysis, Hadamard products, and tree recurrences
• The rotation correspondence is asymptotically a dilatation

Cited in

(7)

• Unbalanced subtrees in binary rooted ordered and un-ordered trees
• On rotations in fringe-balanced binary trees
• An Analysis of the Height of Tries with Random Weights on the Edges
• Branching random walks on binary search trees: convergence of the occupation measure
• Imbalance in random digital trees
• Left and right length of paths in binary trees or on a question of Knuth
• General Edgeworth expansions with applications to profiles of random trees

This page was built for publication: The left-right-imbalance of binary search trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q868958)