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