Lehrstuhl Mathematik & InformatikThe Effect of Delations in Binary Search Trees
Abstract. We are concerned with the behaviour of binary search trees formed by inserting and deleting keys using the standard insertion algorithm (attach a new key as a leaf, leaving the tree otherwise unchanged) and standard deletion algorithms (delete a key attached to a leaf by removing the leaf). We investigate the worstcase-effect of merging deletions into a given sequence of insertions. Call the result the extension of the sequence. It is shown that any sequence of n insertions (of pairwise different keys) has one extension with an average execution time of \Omega (n1/3), and has a second extension which produces a search tree with an average search time of \Omega (\sqrt{n}). The second result is tight. The first result leaves a gap which we can only close for 'almost all' sequences. All lower bounds are still valid if the deletion of keys attached to interior nodes is performed symmetrically between left and right.