Randomized binary search trees are an efficient dynamic data structure for storing items when the access sequence is not known a priori. We propose a space-efficient variation of randomized binary search trees that is approximately optimal in random key ordering, using Morris’ counters. The space required on average is O(n log log m) for an access sequence of n items and length m, compared to O(n log m) for Seidel and Aragon’s treaps. In the case where a probability distribution of the keys is given but the ordering of the keys is random, we prove that our algorithm has an expected access cost within a constant factor of the optimal solution. The proof is based on a novel Markov chain decomposition technique and a coupling argument. Moreover, our numerical experiments demonstrate that o...[ Read more ]

Randomized binary search trees are an efficient dynamic data structure for storing items when the access sequence is not known a priori. We propose a space-efficient variation of randomized binary search trees that is approximately optimal in random key ordering, using Morris’ counters. The space required on average is O(n log log m) for an access sequence of n items and length m, compared to O(n log m) for Seidel and Aragon’s treaps. In the case where a probability distribution of the keys is given but the ordering of the keys is random, we prove that our algorithm has an expected access cost within a constant factor of the optimal solution. The proof is based on a novel Markov chain decomposition technique and a coupling argument. Moreover, our numerical experiments demonstrate that our approach is empirically superior to the original treap for certain access patterns.