Movatterモバイル変換

Next:7.3 Discussion and Exercises Up:7. Random Binary Search Previous:7.1 Random Binary Search  Contents

• 7.2.1 Summary

7.2Treap: A Randomized Binary Search Tree

The problem with random binary search trees is, of course, that they arenot dynamic. They don't support the or operationsneeded to implement theSSet interface. In this section we describea data structure called aTreap that uses Lemma 7.1 to implementtheSSet interface.^7.2

A node in aTreap is like a node in aBinarySearchTree in that it hasa data value,, but it also contains a unique numericalpriority,, that is assigned at random:

    class Node<T> extends BinarySearchTree.BSTNode<Node<T>,T> {        int p;    }

• (Heap Property) At every node, except the root,.

Figure 7.5:An example of aTreap containing the integers. Each node,, is illustrated as a box containing.

The heap and binary search tree conditions together ensure that, oncethe key () and priority () for each node are defined, theshape of theTreap is completely determined. The heap property tells us thatthe node with minimum priority has to be the root,, of theTreap.The binary search tree property tells us that all nodes with keys smallerthan are stored in the subtree rooted at and all nodeswith keys larger than are stored in the subtree rooted at.

The important point about the priority values in aTreap is that theyare unique and assigned at random. Because of this, there aretwo equivalent ways we can think about aTreap. As defined above, aTreap obeys the heap and binary search tree properties. Alternatively,we can think of aTreap as aBinarySearchTree whose nodeswere added in increasing order of priority. For example, theTreapin Figure 7.5 can be obtained by adding the sequence ofvalues

Since the priorities are chosen randomly, this is equivalent to taking arandom permutation of the keys -- in this case the permutation is

Lemma7..2  In aTreap that stores a set of keys, the following statements hold:

1. For any, the expected length of the search path for is.
2. For any, the expected length of the search path for is.

Here, denotes the rank of in the set.

Lemma 7.2 tells us thatTreaps can implement theoperation efficiently. However, the real benefit of aTreap is thatit can support the and operations. Todo this, it needs to perform rotations in order to maintain the heap property. Refer to Figure 7.6.Arotation in a binarysearch tree is a local modification that takes a parent of a nodeand makes the parent of, while preserving the binary search treeproperty. Rotations come in two flavours:left orrightdepending on whether is a right or left child of, respectively.

Figure 7.6:Left and right rotations in a binary search tree.

The code that implements this has to handle these two possibilitiesand be careful of a boundarycase (when is the root) so the actual code is a little longer thanFigure 7.6 would lead a reader to believe:

    void rotateLeft(Node u) {        Node w = u.right;        w.parent = u.parent;        if (w.parent != nil) {            if (w.parent.left == u) {                w.parent.left = w;            } else {                w.parent.right = w;            }        }        u.right = w.left;        if (u.right != nil) {            u.right.parent = u;        }        u.parent = w;        w.left = u;        if (u == r) { r = w; r.parent = nil; }    }        void rotateRight(Node u) {        Node w = u.left;        w.parent = u.parent;        if (w.parent != nil) {            if (w.parent.left == u) {                w.parent.left = w;            } else {                w.parent.right = w;            }        }        u.left = w.right;        if (u.left != nil) {            u.left.parent = u;        }        u.parent = w;        w.right = u;        if (u == r) { r = w; r.parent = nil; }    }

Using rotations, we can implement the operation as follows:We create a new node,, and assign and pick a random valuefor. Next we add using the usual algorithmfor aBinarySearchTree, so that is now a leaf of theTreap.At this point, ourTreap satisfies the binary search tree property,but not necessarily the heap property. In particular, it may be thecase that. If this is the case, then we perform arotation at node= so that becomes the parent of.If continues to violate the heap property, we will have to repeat this, decreasing's depth by one every time, until either becomes the root or.

    boolean add(T x) {        Node<T> u = newNode();        u.x = x;        u.p = rand.nextInt();        if (super.add(u)) {            bubbleUp(u);            return true;        }        return false;    }    void bubbleUp(Node<T> u) {        while (u.parent != nil && u.parent.p > u.p) {            if (u.parent.right == u) {                rotateLeft(u.parent);            } else {                rotateRight(u.parent);            }        }        if (u.parent == nil) {            r = u;        }    }

Figure 7.7:Adding the value 1.5 into theTreap from Figure 7.5.

The running time of the operation is given by the time ittakes to follow the search path for plus the number of rotationsperformed to move the newly-added node,, up to its correct locationin theTreap. By Lemma 7.2, the expected length of thesearch path is at most. Furthermore, each rotationdecreases the depth of. This stops if becomes the root, sothe expected number of rotations cannot exceed the expected length ofthe search path. Therefore, the expected running time of theoperation in aTreap is. (Exercise 7.5asks you to show that the expected number of rotations performed duringan addition is actually only.)

The operation in aTreap is the opposite of theoperation. We search for the node,, containing and then performrotations to move downwards until it becomes a leaf and then wesplice from theTreap. Notice that, to move downwards, we canperform either a left or right rotation at, which will replacewith or, respectively.The choice is made by the first of the following that apply:

1. If and are both, then is a leaf and no rotation is performed.
2. If (or) is, then perform a right (or left, respectively) rotation at.
3. If (or, then perform a right rotation (or left rotation, respectively) at.

    boolean remove(T x) {        Node<T> u = findLast(x);        if (u != nil && compare(u.x, x) == 0) {            trickleDown(u);            splice(u);            return true;        }        return false;    }    void trickleDown(Node<T> u) {        while (u.left != nil || u.right != nil) {            if (u.left == nil) {                rotateLeft(u);            } else if (u.right == nil) {                rotateRight(u);            } else if (u.left.p < u.right.p) {                rotateRight(u);            } else {                rotateLeft(u);            }            if (r == u) {                r = u.parent;            }        }    }

Figure 7.8:Removing the value 9 from theTreap in Figure 7.5.

The trick to analyze the running time of the operation isto notice that this operation is the reverse of the operation.In particular, if we were to reinsert, using the same priority,then the operation would do exactly the same number of rotationsand would restore theTreap to exactly the same state it was in beforethe operation took place. (Reading from bottom-to-top,Figure 7.8 illustrates the addition of the value 9 into aTreap.) This means that the expected running time of theon aTreap of size is proportional to the expected running timeof the operation on aTreap of size. We concludethat the expected running time of is.

7.2.1 Summary

The following theorem summarizes the performance of theTreap datastructure:

Theorem7..2  ATreap implements theSSet interface. ATreap supportsthe operations,, and inexpected time per operation.

It is worth comparing theTreap data structure to theSkiplistSSetdata structure. Both implement theSSet operations inexpected time per operation. In both data structures, andinvolve a search and then a constant number of pointer changes(see Exercise 7.5 below). Thus, for both thesestructures, the expected length of the search path is the critical valuein assessing their performance. In aSkiplistSSet, the expected lengthof a search path is

Footnotes

... interface.^7.2

The namesTreap comes from the factthat this data structure is simultaneously a binary searchtree(Section 6.2) and a heap (Chapter 10).

... rank,^7.3

Therank of an element in a set of elements is the number ofelements in that are less than.

---

Next:7.3 Discussion and Exercises Up:7. Random Binary Search Previous:7.1 Random Binary Search  Contents