Splay Trees

Splay Tree | Set 1 (Search)
A splay tree is a binary search tree. It has one interesting difference, however: whenever an element is looked up in the tree, the splay tree reorganizes to move that element to the root of the tree, without breaking the binary search tree invariant. If the next lookup request is for the same element, it can be returned immediately. In general, if a small number of elements are being heavily used, they will tend to be found near the top of the tree and are thus found quickly.

The search operation in Splay tree does the standard BST search, in addition to search, it also splays (move a node to the root). If the search is successful, then the node that is found is splayed and becomes the new root. Else the last node accessed prior to reaching the NULL is splayed and becomes the new root.

2) Zig: Node is child of root (the node has no grandparent). Node is either a left child of root (we do a right rotation) or node is a right child of its parent (we do a left rotation).
T1, T2 and T3 are subtrees of the tree rooted with y (on left side) or x (on right side)

3) Node has both parent and grandparent. There can be following subcases.
........3.a) Zig-Zig and Zag-Zag Node is left child of parent and parent is also left child of grand parent (Two right rotations) OR node is right child of its parent and parent is also right child of grand parent (Two Left Rotations).
........3.b) Zig-Zag and Zag-Zig Node is left child of parent and parent is right child of grand parent (Left Rotation followed by right rotation) OR node is right child of its parent and parent is left child of grand parent (Right Rotation followed by left rotation).

struct node *splay(struct node *root, int key)

{

    // Base cases: root is NULL or key is present at root

    if (root == NULL || root->key == key)

        return root;

 

    // Key lies in left subtree

    if (root->key > key)

    {

        // Key is not in tree, we are done

        if (root->left == NULL) return root;

 

        // Zig-Zig (Left Left)

        if (root->left->key > key)

        {

            // First recursively bring the key as root of left-left

            root->left->left = splay(root->left->left, key);

 

            // Do first rotation for root, second rotation is done after else

            root = rightRotate(root);

        }

        else if (root->left->key < key) // Zig-Zag (Left Right)

        {

            // First recursively bring the key as root of left-right

            root->left->right = splay(root->left->right, key);

 

            // Do first rotation for root->left

            if (root->left->right != NULL)

                root->left = leftRotate(root->left);

        }

 

        // Do second rotation for root

        return (root->left == NULL)? root: rightRotate(root);

    }

    else // Key lies in right subtree

    {

        // Key is not in tree, we are done

        if (root->right == NULL) return root;

 

        // Zag-Zig (Right Left)

        if (root->right->key > key)

        {

            // Bring the key as root of right-left

            root->right->left = splay(root->right->left, key);

 

            // Do first rotation for root->right

            if (root->right->left != NULL)

                root->right = rightRotate(root->right);

        }

        else if (root->right->key < key)// Zag-Zag (Right Right)

        {

            // Bring the key as root of right-right and do first rotation

            root->right->right = splay(root->right->right, key);

            root = leftRotate(root);

        }

 

        // Do second rotation for root

        return (root->right == NULL)? root: leftRotate(root);

    }

}

1) Splay trees have excellent locality properties. Frequently accessed items are easy to find. Infrequent items are out of way.

3) Splay trees are simpler compared to AVL and Red-Black Trees as no extra field is required in every tree node.

Read full article from Splay Trees