How to rotate a treap or AVL-tree?

Question

Sorry to bother you guys again, but I have a question and i haven't figured it out on my own for several days. It is about the rotation of a treap, for example, to right rotate a treap at pos. The question is how to link (or connect) pos->left to pos's original parent? I found this code online, which works, but i didn't see how it solves my question, is it because of the use of *&? If so, could you help me explain it a little bit? And what is the function of pos=b is this code?

void Treap::right_rotate(Node *&pos) {
    Node *b   = pos->left; 
    pos->left = b->right;
    b->right  = pos;
    pos       = b;
}

Thanks in advance!!

Answer 1

The tricky part is indeed the *& part. That declares it as a reference to a pointer (here's a link or two to some similar sample code, but I fear they may be more confusing than helpful).

By changing out the node to which the pointer points with pos = b, you can swap the contents to the different node without having to know the parent. The original reference is updated to be the new rotated node.

Here's a diagram just in case you needed a little overkill of what the rotation looks like (though it sounds like you understand that part).

Initial condition:

Node *&pos; 

         |
        [P]
      /     \
     L       R
    / \     / \ 
   w   x   y   z

You then store the left child since you are about to overwrite it as far as P is concerned.

Node *b = pos->left;
pos->left = b->right;

           |
    L     [P]
  /  \   /   \
 w     x      R
             / \ 
            y   z

Now we finish the rotation since since L is floating in space, breaking proper tree structure:

b->right = pos;

        L     
      /  \ |
     w    [P]
         /   \
        x     R
             / \ 
            y   z

We then finish the upkeep by updating the reference to the node pointer to be the new node that replaces the contents of that place in memory:

pos = b;

       |
      [L]     
     /   \
    w      P
         /   \
        x     R
             / \ 
            y   z

Whomever was previously pointing to pos (pos's original parent) now points to the same spot in memory, but that value has now been replaced with the child that has been rotated.