An Iterative Algorithm for Treap Insertion Farooq Mela <f mela@yahoo.com>

Algorithm I (Treap Insertion). Given a set of nodes which form a treap T, and a key to insert K, this algorithm will insert the node into the treap while maintaining it’s heap properties. Each node is assumed to contain KEY, PRIO, LLINK, RLINK, and PARENT fields. For any given node N, KEY(N) gives the key field of N, PRIO(N) gives the priority field of N, LLINK(N) and RLINK(N) are pointers to N’s left and right subtrees, respectively, and PARENT(N) is a pointer to the node of which N is a subtree. Any or all of these three link fields may be Λ, which for LLINK(N) and RLINK(N) indicates that N has no left or right subtree, respectively, and for PARENT(N) indicates that N is the root of the treap. The treap has a field ROOT which is a pointer to the root node of the treap.

You can find an implementation of this algorithm, as well as many others, in libdict, which is available on

the web at http://home.earthlink.net/~smela1/libdict.html.

I1. [Initialize.] Set N ← ROOT(T), P ← Λ.

I2. [Find insertion point.] If N = Λ, go to step I3. If K = KEY(N), the key is already in the treap and the algorithm terminates with an error. Set P ← N; if K < KEY(N), then set N ← LLINK(N), otherwise set N ← RLINK(N). Repeat this step.

I3. [Insert.] Set N ← AVAIL. If N = Λ, the algorithm terminates with an out of memory error. Set KEY(N) ← K, LLINK(N) ← RLINK(N) ← Λ, and PARENT(N) ← P. Set PRIO(N) equal to a random integer. If P = Λ, set ROOT(T) ← N, and go to step I5. If K < KEY(P), set LLINK(P) ← N; otherwise,

       set RLINK(P) ← N.

I4. [Sift up.] If P = Λ or PRIO(P) ≤ PRIO(N), go to step I5. If LLINK(P) = N, rotate P right; otherwise,

rotate P left. Then set P ← PARENT(N), and repeat this step. I5. [All done.] The algorithm terminates successfully.

Rotations Algorithm R (Right Rotation). Given a treap T and a node in the treap N, this routine will rotate N right.

R1. [Do the rotation.] Set L ← LLINK(N) and LLINK(N) ← RLINK(L). If RLINK(L) ≠ Λ, then set

       PARENT(RLINK(L)) ← N. Set P ← PARENT(N), PARENT(L) ← P. If P = Λ, then set ROOT(T) ← L; if

P ≠ Λ and LLINK(P) = N, set LLINK(P) ← L, otherwise set RLINK(P) ← L. Finally, set RLINK(L) ← N,

       and PARENT(N) ← L.

The code for a left rotation is symmetric. At the risk of being repetitive, it appears below.

Algorithm L (Left Rotation). Given a treap T and a node in the treap N, this routine will rotate N left.

L1. [Do the rotation.] Set R ← RLINK(N) and RLINK(N) ← LLINK(R). If LLINK(R) ≠ Λ, then set

       PARENT(LLINK(R)) ← N. Set P ← PARENT(N), PARENT(R) ← P. If P = Λ, then set ROOT(T) ← R; if

P ≠ Λ and LLINK(P) = N, set LLINK(P) ← R, otherwise set RLINK(P) ← R. Finally, set LLINK(R) ← N,

       and PARENT(N) ← R.