Treaps: Randomized search trees

yourbasic.org
symbolic search tree

A treap stores items in sorted order and offers effi­cient lookup, addi­tion and remo­val of items.

If you could use only one data structure, which one would you choose? A hash table? While it supports the basic lookup, addition and removal operations, it doesn’t keep the elements sorted. Therefore it can’t efficiently perform some common tasks, such as finding the minimum element or producing an ordered list of all elements.

What would you require of this ideal, sole structure? It should be easy to use (and preferably easy to implement) and it should be efficient in terms of both speed and memory.

The randomized search tree by Seidel and Aragon, described in “Randomized Search Trees” (Algorithmica, 16(4/5):464–497, 1996), fulfills all of these requirements, and it offers the functionality of a general-purpose sorting routine, priority queue, hash table, stack, or standard queue.

Data Structure

The data structure consists of a balanced binary tree. Therefore, an element is never more than about log n steps away, where n is the number of elements in the treap and log n is the binary logarithm.

Being able to access the elements in the treap in log n time is a big improvement over some of the most common basic data structures.

Insert Find Min
Unsorted array 1 n n
Sorted array n log n 1
Unsorted linked list 1 n n
Sorted linked list n n 1
Hash table 1 1 n
Treap log n log n log n

The treap is reasonably space efficient as well. Each element is stored in a node in a tree, and each node contains an integer and two references, one to the left subtree and one to the right subtree. Hence, to store n elements in a treap, we need n integers and 2n references.

A typical hash-table implementation uses n integers for the hash values and n references for the linked lists. Furthermore, it uses an array with a size that is typically close to n. For example, with a load factor of 1.0, the hash table will use the same amount of extra space as a treap if the table is full, and more space if it’s only partly filled.

Implementation

A search tree consists of a number of nodes. Each node contains a key and has two references, one to the left subtree and one to the right.

         E
        / \
       B   H
      /   / \
     A   F   K

Note that the tree is ordered. All keys in the left subtree are smaller than the key in the node, and all keys in the right subtree are larger. This property holds for every node in the tree. Therefore, it’s possible to search the tree in a simple manner.

For example, to check if the key F is present in the tree,

You can use the same technique to insert a new node. If the key of the new node isn’t already present in the tree, the search will take you to a position at the bottom of the tree where the new node can be inserted.

But you still have a potential problem. The algorithm above is efficient only if the tree is well balanced. For example, if each node in the tree has only one child, the structure will behave just like a linked list: You have to visit every node in the tree to find the one at the bottom.

There are plenty of algorithms available that try to keep a search tree balanced. Most of them are rather complicated. The treap offers a simple solution.

You will use rotations (the simplest possible rebalancing operation) to help keep the tree balanced. The idea is to change the form of the tree without disturbing the order of the keys. The left tree in this figure is transformed into the right one by a right rotation.

        B               A
       / \             / \
      A        <->        B
     / \                 / \

This operation is easy to implement – only two references need to be updated, and the order of the keys is preserved. The corresponding balancing operation that transforms the right tree into the left one is called a left rotation.

Now comes the stroke of genius. You want the tree to look as if it was constructed from a random sequence of updates. (Random trees are nicely balanced. The expected length of an average search path is roughly 1.4 log2 n - 2, and the expected length of the longest search path is about 4.3 log2 n.)

To achieve this,

If you do this, the tree will have the same form as if the nodes had been added in priority order, that is random order.

Insert

The insertion algorithm is best explained by an example.

(a)       E3                (b)       E3
         / \                         / \
       B5   H7                     B5   H7
       /   / \                     /   / \
     A6   F9  K8                 A6   G2  K8
           \                         /
           G2                       F9


(c)       E3                (d)       G2
         / \                         / \
       B5   G2                     E3   H7
       /   / \                     / \   \
     A6   F9  H7                 B5   F9  K8
               \                 /
                K8              A6

In Fig. A the node G (with priority 2) has just been added to the treap. It has been placed in the correct position with respect to the ordering of the keys, but it violates the priority requirement: It has higher priority than its parent.

Now the tree fulfills both the key order and the priority order requirements.

At first this algorithm may seem hard to implement. It looks as if you would have to walk up the tree, which is hard since the references point in the other direction. However, this problem is easily overcome if you formulate the insertion algorithm recursively.

// Insert a new node in the tree and return the updated tree.
Algorithm insert(node, tree)
    if tree is empty
        return node
    if node.key < tree.key
        tree.left ← insert(node, tree.left)
        if tree.prio > tree.left.prio
            rotate tree to the right
    else
        tree.right ← insert(node, tree.right)
        if tree.prio > tree.right.prio
            rotate tree to the left
    return tree

Delete

Compared to those of other balanced search tree schemes, the delete operation is also quite simple.

In Dr. Dobb’s Journal, pp. 40-44, Vol. 267, July 1997.

Share this page: