Smoothed analysis of binary search trees

DOI10.1016/j.tcs.2007.02.035zbMath1120.68043OpenAlexW2157661221MaRDI QIDQ2371805

Bodo Manthey, K. Ruediger Reischuk

Publication date: 9 July 2007

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

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

zbMATH Keywords

permutationsbinary search treessmoothed analysisdiscrete perturbations

Mathematics Subject Classification ID

Searching and sorting (68P10) Data structures (68P05)

Related Items (9)

Smoothed Analysis of Local Search Algorithms ⋮ On Smoothed Analysis of Quicksort and Hoare’s Find ⋮ An Improved Bound for Random Binary Search Trees with Concurrent Insertions ⋮ Beyond the worst-case analysis of random priority: smoothed and average-case approximation ratios in mechanism design ⋮ Universality for Eigenvalue Algorithms on Sample Covariance Matrices ⋮ On smoothed analysis of quicksort and Hoare's find ⋮ Smoothed Analysis of Binary Search Trees and Quicksort under Additive Noise ⋮ Smoothed analysis of balancing networks ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On growing random binary trees
• Generating quasi-random sequences from semi-random sources
• Smoothed analysis of termination of linear programming algorithms
• Heuristics for semirandom graph problems
• Constant bounds on the moments of the height of binary search trees
• An analytic approach to the height of binary search trees
• Randomized search trees
• Topology matters: smoothed competitiveness of metrical task systems
• The height of a random binary search tree
• An analytic approach to the height of binary search trees II
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Smoothed analysis of algorithms
• Smoothed Analysis of Integer Programming
• A note on the height of binary search trees
• On the concentration of the height of binary search trees
• Coloring Random and Semi-Random k-Colorable Graphs
• On the Variance of the Height of Random Binary Search Trees
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Average-Case and Smoothed Competitive Analysis of the Multilevel Feedback Algorithm
• Mathematical Foundations of Computer Science 2003
• Algorithms – ESA 2004
• Typical Properties of Winners and Losers [0.2ex in Discrete Optimization]
• Fundamentals of Computation Theory
• Algorithms - ESA 2003
• Algorithms and Data Structures

This page was built for publication: Smoothed analysis of binary search trees