Item

Abstract

This thesis introduces a new type of randomized search trees based on the median-of-three improvement for quicksort (M3 quicksort). We consider the set of trees obtained by running M3 quicksort. This thesis show how to obtain them by a slightly changed insertion procedure for binary search trees. Furthermore, if the input is random, it generates the same probability distribution as M3 quicksort and consequently accesses in the tree are faster than for randomized search trees. In order to maintain randomness for any type of input sequence, we introduce the concept of support nodes, which define a path covering of the tree. With their help, and by storing the subtree size at each node, random updates take O(log n). If instead of subtree sizes, each node stores a random priority, updates take O(log2 n). Experiments show that while accesses are indeed faster, update times take however too long for the method to be competitive.