Splay Tree in C - Sanfoundry

This is a C Program to implement Splay tree. Like AVL and Red-Black Trees, Splay tree is also self-balancing BST. The main idea of splay tree is to bring the recently accessed item to root of the tree, this makes the recently searched item to be accessible in O(1) time if accessed again. The idea is to use locality of reference.

Here is source code of the C Program to Implement Splay Tree. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

```
#include<stdio.h>
```
```
#include<stdlib.h>
```
```
 
```
```
// An AVL tree node
```
```
struct node {
```
```
    int key;
```
```
    struct node *left, *right;
```
```
};
```
```
 
```

/* Helper function that allocates a new node with the given key and

```
 NULL left and right pointers. */
```
```
struct node* newNode(int key) {
```

    struct node* node = (struct node*) malloc(sizeof(struct node));

```
    node->key = key;
```
```
    node->left = node->right = NULL;
```
```
    return (node);
```
```
}
```
```
 
```

// A utility function to right rotate subtree rooted with y

```
// See the diagram given above.
```

struct node *rightRotate(struct node *x) {

```
    struct node *y = x->left;
```
```
    x->left = y->right;
```
```
    y->right = x;
```
```
    return y;
```
```
}
```
```
 
```

// A utility function to left rotate subtree rooted with x

```
// See the diagram given above.
```

struct node *leftRotate(struct node *x) {

```
    struct node *y = x->right;
```
```
    x->right = y->left;
```
```
    y->left = x;
```
```
    return y;
```
```
}
```
```
 
```

// This function brings the key at root if key is present in tree.

// If key is not present, then it brings the last accessed item at

// root.  This function modifies the tree and returns the new root

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);

```
    }
```
```
}
```
```
 
```

// The search function for Splay tree.  Note that this function

// returns the new root of Splay Tree.  If key is present in tree

```
// then, it is moved to root.
```

struct node *search(struct node *root, int key) {

```
    return splay(root, key);
```
```
}
```
```
 
```

// A utility function to print preorder traversal of the tree.

// The function also prints height of every node

```
void preOrder(struct node *root) {
```
```
    if (root != NULL) {
```
```
        printf("%d ", root->key);
```
```
        preOrder(root->left);
```
```
        preOrder(root->right);
```
```
    }
```
```
}
```
```
 
```
```
int main() {
```
```
    struct node *root = newNode(100);
```
```
    root->left = newNode(50);
```
```
    root->right = newNode(200);
```
```
    root->left->left = newNode(40);
```

    root->left->left->left = newNode(30);

    root->left->left->left->left = newNode(20);

```
 
```

    printf("Preorder traversal of the Splay tree is \n");

```
    preOrder(root);
```
```
    root = search(root, 20);
```

    printf("\nPreorder traversal of after search Splay tree is \n");

```
    preOrder(root);
```
```
    return 0;
```
```
}
```

Output:

$ gcc SplayTree.c
$ ./a.out
 
Preorder traversal of the Splay tree is 
100 50 40 30 20 200 
Preorder traversal of after search Splay tree is 
20 50 30 40 100 200

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Here’s the list of Best Books in C Programming, Data Structures and Algorithms.

« Prev - C Program to Perform Left and Right Rotation on a Binary Search Tree

» Next - C Program to Perform Searching in a BST

Related Posts:

Check Computer Science Books
Apply for Computer Science Internship
Practice Computer Science MCQs
Practice Programming MCQs
Practice Design & Analysis of Algorithms MCQ

Recommended Articles: