Lecture Overview

I continued talking about treaps.

For comparison, here is a recursive implenentation of add to contrast to the book's iterative version. It works identically, the element goes in the same location and the same bubbling up occurs, but in the recursive version the bubbling up happens during the recursive calls. Also, the recursive version does not need to store the parent of any node which simplifies the code somewhat. Especially rotate right and left are shorter since they don't have to deal with the parent.

First, the data structures:

struct Node {
    T x;
    int p;
    shared_ptr<Node> left;
    shared_ptr<Node> right;
}

struct Treap {
    shared_ptr<Node> root;
}

Now pseudocode for the add method:

rotate_right(u):
    # Transforms           u               w
    #                     / \             / \
    #                    w   C     to    A   u
    #                   / \                 / \
    #                  A   B               B   C
    #
    # and returns w
    w = u.left
    u.left = w.right # copy B
    w.right = u
    return w


rotate_left(w):
    # Transforms        w            u  
    #                  / \          / \ 
    #                 A   u   to   w   C
    #                    / \      / \   
    #                   B   C    A   B  
    # and returns u
    u = w.right
    w.right = u.left # copy B
    u.left = u
    return u

add_helper(newNode, v):
    # Adds newNode into the tree rooted at v
    # returns the new root of the tree, which could be different than v

    if v == nil:
        return newNode

    if newNode.x == v.x:
        v.x = newNode.x # recall x could be a pair of a key and value

    elif newNode.x < v.x:
        # Insert newNode to the left.  The root of the left subtree could change,
        # so the return value of the recusive call will replace v.left
        v.left = add_helper(newNode, v.left)

        # If the heap property is violated, rotate right
        if v.left.p < v.p:
            v = rotate_right(v)

    else:
        # Insert newNode to the right.  The root of the right subtree could change,
        # so the return value of the recusive call will replace v.right
        v.right = add_helper(newNode, v.right)

        # If the heap property is violated, rotate left
        if v.right.p < v.p:
            v = rotate_left(v)

    return v


add(x):
   newNode = allocate new node
   newNode.x = x
   newNode.p = random number
   root = add_helper(newNode, root)

Exercises

Exercises 7..1 and 7..2 from this page.