Help Privacy Policy Disclaimer
  Advanced SearchBrowse





Randomized Median-of-Three Trees


Dinu,  Lavinia
International Max Planck Research School, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available

Dinu, L. (2013). Randomized Median-of-Three Trees. Master Thesis, Universität des Saarlandes, Saarbrücken.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0026-CB5B-C
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.