hide
Free keywords:
-
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.
