# Treap: A Randomized Binary Search Tree

Learn the implementation of a randomized binary search tree.

The problem with random binary search trees is, of course, that they
are not dynamic. They don’t support the `add(x)`

or `remove(x)`

operations
needed to implement the `SSet`

interface. In this section we describe a
data structure called a `Treap`

that uses Lemma 1 (from the previous lesson) to implement the `SSet`

interface.

Note:The name Treap comes from the fact that this data structure is simultaneously a binary search tree and a heap.

## Treap overview

A node in a `Treap`

is like a node in a `BinarySearchTree`

in that it has
a data value, `x`

, but it also contains a unique numerical priority, `p`

, that is
assigned at random:

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy