Reductions in binary search trees

DOI10.1016/J.TCS.2005.12.015zbMATH Open1089.68136OpenAlexW1968413668MaRDI QIDQ2369002FDOQ2369002

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

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

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)

Cites Work

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

Cited In (5)

• A Markov chain model for dynamic binary search tree behaviour
• Title not available (Why is that?)
• Title not available (Why is that?)
• The effects of semantic simplifications on random \textit{BST}-like expression-trees
• Psi-series method for equality of random trees and quadratic convolution recurrences

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)