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:
class BinarySearchTree(BinaryTree,BaseSet):class Node(BinaryTree.Node):def __init__(self, x):super(BinarySearchTree.Node, self).__init__()self.x = x
In addition to being a binary search tree, the nodes in a Treap also
obey the heap property:
- (Heap Property) At every node
u, except the root,u.parent.p < u.p.
In other words, each node has a priority smaller than that of its two children. An example is shown in the below illustration.
The heap and binary search tree conditions together ensure that, once
the key(x) and priority(p) for each node are defined, the shape of the
Treap is completely determined. The heap property tells us that the node with minimum priority has to be the root, r, of the Treap. The binary
search tree property tells us that all nodes with keys smaller than r.x are
stored in the subtree rooted at r.left and all nodes with keys larger than
r.x are stored in the subtree rooted at r.right.
The important point about the priority values in a Treap is that they
are unique and assigned at random. Because of this, there are two equivalent ways we can think about a Treap. As defined above, a Treap obeys
the heap and binary search tree properties. Alternatively, we can think
of a Treap as a BinarySearchTree whose nodes were added in increasing
order of priority. For example, the Treap in above figure can be obtained by
adding the sequence of (x, p) values
...
Create a free account to access the full course.
By signing up, you agree to Educative's Terms of Service and Privacy Policy