next up previous contents index
Next: 7.1 Random Binary Search Up: Open Data Structures (in Previous: 6.3 Discussion and Exercises Contents Index

7. Random Binary Search Trees

In this chapter, we present a binary search tree structure that uses randomization to achieve $ O(\log \ensuremath{\ensuremath{\ensuremath{\mathit{n}}}})$ expected time for all operations.

Subsections

7.1 Random Binary Search Trees
7.2 Treap: A Randomized Binary Search Tree
7.3 Discussion and Exercises

opendatastructures.org