Can not figure out how splaying works

Question

I can not understand how splaying works.
The part that I can not follow is how we know if a: i) zig ii) zig-zag or iii) zig-zig must be done.
If I understand correctly this has to do with the current node in the path.
If it is the root's child then it is a zig otherwise either (ii) or (iii) depending on if the parent of current node and current node are both left (or right) children. Ok so far.
Now the part I don't get:
As we move down isn't the process to "remove" the intermediate nodes into left and right subtrees so that we have a middle tree that will be eventually the root of the item under search?
Then if we start from a tree we would be doing continually zig and nothing else since we are removing elements and are always at the root.
Example:

If for example I am looking for 20 I would start at the root and go left. So the current node has root as parent and I do a zig. Now what happens?? I am at 26 and go left but isn't 26 also root? So should I be doing a zig?
But from what I see in this example a zig-zag is being done and I can not understand why.
Any help here?

Answer 1

By root they mean root of the entire tree, not root of the subtree you are splaying. So, in your example 12 is the root of the entire tree.

...

If you'd like an example to work from, I coded up a SplayTree in Java recently. You can find the code here.

The big thing with splay tree's is they move the most recently inserted/queried node up (at most) two levels in the tree. You have to perform a zig, zig-zig, or zig-zag based on it's grand parent and parent node locations.

When a node x is accessed, a splay operation is performed on x to move it to the root. To perform a splay operation we carry out a sequence of splay steps, each of which moves x closer to the root.

The three types of splay steps are: (g = grand parent, p = parent, and x = node to splay)

• Zig Step: This step is done when p is the root. The tree is rotated on the edge between x and p.
• Zig-zig Step: This step is done when p is not the root and x and p are either both right children or are both left children. The tree is rotated on the edge joining p with its parent g, then rotated on the edge joining x with p.
• Zig-zag Step: This step is done when p is not the root and x is a right child and p is a left child or vice versa. The tree is rotated on the edge between x and p, then rotated on the edge between x and its new parent g.

http://en.wikipedia.org/wiki/Splay_tree

Below is splaying of node 3 in the tree.

Tree before splaying:

└── 0
    └── (right) 9
        └── (left) 7
            ├── (left) 5
            │   ├── (left) 1
            │   │   └── (right) 2
            │   │       └── (right) 4
            │   │           └── (left) 3
            │   └── (right) 6
            └── (right) 8

After a (right->left) Zig-Zag to node 3.

└── 0
    └── (right) 9
        └── (left) 7
            ├── (left) 5
            │   ├── (left) 1
            │   │   └── (right) 3
            │   │       ├── (left) 2
            │   │       └── (right) 4
            │   └── (right) 6
            └── (right) 8

After another (left->right) Zig-Zag to node 3.

└── 0
    └── (right) 9
        └── (left) 7
            ├── (left) 3
            │   ├── (left) 1
            │   │   └── (right) 2
            │   └── (right) 5
            │       ├── (left) 4
            │       └── (right) 6
            └── (right) 8

After a (left->left) Zig-Zig to node 3.

└── 0
    └── (right) 3
        ├── (left) 1
        │   └── (right) 2
        └── (right) 7
            ├── (left) 5
            │   ├── (left) 4
            │   └── (right) 6
            └── (right) 9
                └── (left) 8

After a (right) Zig to node 3. Now time to stop since 3 is in the root position.

└── 3
    ├── (left) 0
    │   └── (right) 1
    │       └── (right) 2
    └── (right) 7
        ├── (left) 5
        │   ├── (left) 4
        │   └── (right) 6
        └── (right) 9
            └── (left) 8t) 6
                └── (right) 9
                    └── (left) 8

If you try and access node 3 again in the Tree, it would not have to be splayed since it's already in the root position.