Reductions in binary search trees

DOI10.1016/J.TCS.2005.12.015MaRDI QIDQ2369002zbMATH OpenOpenAlexFDO

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

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

Generating functionDifferential equationSingularity analysisAnalytic convergenceBottom-up algorithmComplex asymptotics

Mathematics Subject Classification ID

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

Recommendations

• Analysis of the standard deletion algorithms in exact fit domain binary search trees
• Randomized binary search trees
• scientific article; zbMATH DE number 1080355
• Random binary trees: from the average case analysis to the asymptotics of distributions
• Reductions of binary trees and lattice paths induced by the register function

Cites work

• scientific article; zbMATH DE number 3649136 (Why is no real title available?)
• scientific article; zbMATH DE number 3143813 (Why is no real title available?)
• scientific article; zbMATH DE number 3814037 (Why is no real title available?)
• scientific article; zbMATH DE number 3821741 (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 3565290 (Why is no real title available?)
• scientific article; zbMATH DE number 1142298 (Why is no real title available?)
• scientific article; zbMATH DE number 1984553 (Why is no real title available?)
• scientific article; zbMATH DE number 815575 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• scientific article; zbMATH DE number 3349081 (Why is no real title available?)
• A unifying look at data structures
• Algebraic simplification in computer algebra: an analysis of bottom-up algorithms
• Average-case analysis of pattern-matching in trees under the BST probability model
• On convergence rates in the central limit theorems for combinatorial structures
• Partial match queries in relaxed multidimensional search trees
• Randomized search trees
• Singularity Analysis of Generating Functions
• Singularity analysis, Hadamard products, and tree recurrences
• The height of a binary search tree: the limiting distribution perspective.

Cited in

(5)

• A Markov chain model for dynamic binary search tree behaviour
• scientific article; zbMATH DE number 2044508 (Why is no real title available?)
• scientific article; zbMATH DE number 3907783 (Why is no real title available?)
• Psi-series method for equality of random trees and quadratic convolution recurrences
• The effects of semantic simplifications on random \textit{BST}-like expression-trees

This page was built for publication: Reductions in binary search trees

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