Reductions in binary search trees

DOI10.1016/j.tcs.2005.12.015zbMath1089.68136OpenAlexW1968413668MaRDI QIDQ2369002

María-Inés Fernández-Camacho, Jose Ramon Sanchez Couso

Publication date: 28 April 2006

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

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

zbMATH Keywords

Differential equationGenerating functionSingularity analysisAnalytic convergenceBottom-up algorithmComplex asymptotics

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Searching and sorting (68P10) Asymptotic enumeration (05A16) Growth estimates (40E10)

Related Items

The effects of semantic simplifications on random \textit{BST}-like expression-trees, Psi-series method for equality of random trees and quadratic convolution recurrences

Cites Work

• Algebraic simplification in computer algebra: an analysis of bottom-up algorithms
• On convergence rates in the central limit theorems for combinatorial structures
• Singularity analysis, Hadamard products, and tree recurrences
• Partial match queries in relaxed multidimensional search trees
• The height of a binary search tree: the limiting distribution perspective.
• Randomized search trees
• Singularity Analysis of Generating Functions
• A unifying look at data structures
• Average-case analysis of pattern-matching in trees under the BST probability model
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item