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