Computational Complexity - Research Seminar
Stefan Schuh: Smoothed Bounds for the Height of Binary Search Trees Using Perturbed Indices
July 1, 2008, 10:15 a.m.
E 1 3, Room 415
Binary search trees are closely related to the running-time of the quicksort algorithm. Manthey and Tantau investigated the smoothed height of binary search trees with additive noise on the data to be inserted in the search tree. What happens if not the data itself, but the indices are perturbed? We are going to present a lower bound, which we suppose is tight, and an upper bound, which is to be refined later.