Splay Tree in C++ - Sanfoundry

This C++ Program demonstrates the implementation of Splay Tree.

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

```
/*
```

 *  C++ Program to Implement Splay Tree

```
 */
```
```
 
```
```
#include <iostream>
```
```
#include <cstdio>
```
```
#include <cstdlib>
```
```
using namespace std;
```
```
 
```
```
struct splay
```
```
{
```
```
    int key;
```
```
    splay* lchild;
```
```
    splay* rchild;
```
```
};
```
```
 
```
```
class SplayTree
```
```
{
```
```
    public:
```
```
        SplayTree()
```
```
        {
```
```
        }
```
```
 
```
```
        // RR(Y rotates to the right)
```
```
        splay* RR_Rotate(splay* k2)
```
```
        {
```
```
            splay* k1 = k2->lchild;
```
```
            k2->lchild = k1->rchild;
```
```
            k1->rchild = k2;
```
```
            return k1;
```
```
        }
```
```
 
```
```
        // LL(Y rotates to the left)
```
```
        splay* LL_Rotate(splay* k2)
```
```
        {
```
```
            splay* k1 = k2->rchild;
```
```
            k2->rchild = k1->lchild;
```
```
            k1->lchild = k2;
```
```
            return k1;
```
```
        }
```
```
 
```

        // An implementation of top-down splay tree

        splay* Splay(int key, splay* root)

```
        {
```
```
            if (!root)
```
```
                return NULL;
```
```
            splay header;
```

            /* header.rchild points to L tree;

            header.lchild points to R Tree */

            header.lchild = header.rchild = NULL;

            splay* LeftTreeMax = &header;

            splay* RightTreeMin = &header;

```
            while (1)
```
```
            {
```
```
                if (key < root->key)
```
```
                {
```
```
                    if (!root->lchild)
```
```
                        break;
```

                    if (key < root->lchild->key)

```
                    {
```

                        root = RR_Rotate(root);

                        // only zig-zig mode need to rotate once,

                        if (!root->lchild)

```
                            break;
```
```
                    }
```

                    /* Link to R Tree */

                    RightTreeMin->lchild = root;

                    RightTreeMin = RightTreeMin->lchild;

                    root = root->lchild;

                    RightTreeMin->lchild = NULL;

```
                }
```

                else if (key > root->key)

```
                {
```
```
                    if (!root->rchild)
```
```
                        break;
```

                    if (key > root->rchild->key)

```
                    {
```

                        root = LL_Rotate(root);

                        // only zag-zag mode need to rotate once,

                        if (!root->rchild)

```
                            break;
```
```
                    }
```

                    /* Link to L Tree */

                    LeftTreeMax->rchild = root;

                    LeftTreeMax = LeftTreeMax->rchild;

                    root = root->rchild;

                    LeftTreeMax->rchild = NULL;

```
                }
```
```
                else
```
```
                    break;
```
```
            }
```

            /* assemble L Tree, Middle Tree and R tree */

            LeftTreeMax->rchild = root->lchild;

            RightTreeMin->lchild = root->rchild;

            root->lchild = header.rchild;

            root->rchild = header.lchild;

```
            return root;
```
```
        }
```
```
 
```
```
        splay* New_Node(int key)
```
```
        {
```
```
            splay* p_node = new splay;
```
```
            if (!p_node)
```
```
            {
```

                fprintf(stderr, "Out of memory!\n");

```
                exit(1);
```
```
            }
```
```
            p_node->key = key;
```

            p_node->lchild = p_node->rchild = NULL;

```
            return p_node;
```
```
        }
```
```
 
```

        splay* Insert(int key, splay* root)

```
        {
```

            static splay* p_node = NULL;

```
            if (!p_node)
```
```
                p_node = New_Node(key);
```
```
            else
```
```
                p_node->key = key;
```
```
            if (!root)
```
```
            {
```
```
                root = p_node;
```
```
                p_node = NULL;
```
```
                return root;
```
```
            }
```
```
            root = Splay(key, root);
```

            /* This is BST that, all keys <= root->key is in root->lchild, all keys >

            root->key is in root->rchild. */

```
            if (key < root->key)
```
```
            {
```

                p_node->lchild = root->lchild;

```
                p_node->rchild = root;
```
```
                root->lchild = NULL;
```
```
                root = p_node;
```
```
            }
```
```
            else if (key > root->key)
```
```
            {
```

                p_node->rchild = root->rchild;

```
                p_node->lchild = root;
```
```
                root->rchild = NULL;
```
```
                root = p_node;
```
```
            }
```
```
            else
```
```
                return root;
```
```
            p_node = NULL;
```
```
            return root;
```
```
        }
```
```
 
```

        splay* Delete(int key, splay* root)

```
        {
```
```
            splay* temp;
```
```
            if (!root)
```
```
                return NULL;
```
```
            root = Splay(key, root);
```
```
            if (key != root->key)
```
```
                return root;
```
```
            else
```
```
            {
```
```
                if (!root->lchild)
```
```
                {
```
```
                    temp = root;
```

                    root = root->rchild;

```
                }
```
```
                else
```
```
                {
```
```
                    temp = root;
```

                    /*Note: Since key == root->key,

                    so after Splay(key, root->lchild),

                    the tree we get will have no right child tree.*/

                    root = Splay(key, root->lchild);

                    root->rchild = temp->rchild;

```
                }
```
```
                free(temp);
```
```
                return root;
```
```
            }
```
```
        }
```
```
 
```

        splay* Search(int key, splay* root)

```
        {
```
```
            return Splay(key, root);
```
```
        }
```
```
 
```
```
        void InOrder(splay* root)
```
```
        {
```
```
            if (root)
```
```
            {
```
```
                InOrder(root->lchild);
```

                cout<< "key: " <<root->key;

```
                if(root->lchild)
```

                    cout<< " | left child: "<< root->lchild->key;

```
                if(root->rchild)
```

                    cout << " | right child: " << root->rchild->key;

```
                cout<< "\n";
```
```
                InOrder(root->rchild);
```
```
            }
```
```
        }
```
```
};
```
```
 
```
```
int main()
```
```
{
```
```
    SplayTree st;
```

    int vector[10] = {9,8,7,6,5,4,3,2,1,0};

```
    splay *root;
```
```
    root = NULL;
```
```
    const int length = 10;
```
```
    int i;
```
```
    for(i = 0; i < length; i++)
```

        root = st.Insert(vector[i], root);

```
    cout<<"\nInOrder: \n";
```
```
    st.InOrder(root);
```
```
    int input, choice;
```
```
    while(1)
```
```
    {
```

        cout<<"\nSplay Tree Operations\n";

```
        cout<<"1. Insert "<<endl;
```
```
        cout<<"2. Delete"<<endl;
```
```
        cout<<"3. Search"<<endl;
```
```
        cout<<"4. Exit"<<endl;
```
```
        cout<<"Enter your choice: ";
```
```
        cin>>choice;
```
```
        switch(choice)
```
```
        {
```
```
        case 1:
```

            cout<<"Enter value to be inserted: ";

```
            cin>>input;
```

            root = st.Insert(input, root);

            cout<<"\nAfter Insert: "<<input<<endl;

```
            st.InOrder(root);
```
```
            break;
```
```
        case 2:
```

            cout<<"Enter value to be deleted: ";

```
            cin>>input;
```

            root = st.Delete(input, root);

            cout<<"\nAfter Delete: "<<input<<endl;

```
            st.InOrder(root);
```
```
            break;
```
```
        case 3:
```

            cout<<"Enter value to be searched: ";

```
            cin>>input;
```

            root = st.Search(input, root);

            cout<<"\nAfter Search "<<input<<endl;

```
            st.InOrder(root);
```
```
            break;
```
```
 
```
```
        case 4:
```
```
            exit(1);
```
```
        default:
```
```
            cout<<"\nInvalid type! \n";
```
```
        }
```
```
    }
```
```
    cout<<"\n";
```
```
    return 0;
```
```
}
```

$ g++ splay_tree.cpp
$ a.out
 
 
Splay Tree Operations
1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 1
Enter value to be inserted: 1
 
After Insert: 1
key: 1
 
Splay Tree Operations
1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 1
Enter value to be inserted: 9
 
After Insert: 9
key: 1
key: 9 | left child: 1
 
Splay Tree Operations
1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 1
Enter value to be inserted: 5
 
After Insert: 5
key: 1
key: 5 | left child: 1 | right child: 9
key: 9
 
Splay Tree Operations
1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 1
Enter value to be inserted: 3
 
After Insert: 3
key: 1
key: 3 | left child: 1 | right child: 5
key: 5 | right child: 9
key: 9
 
Splay Tree Operations
1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 1
Enter value to be inserted: 8
 
After Insert: 8
key: 1
key: 3 | left child: 1
key: 5 | left child: 3
key: 8 | left child: 5 | right child: 9
key: 9
 
Splay Tree Operations
1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 1
Enter value to be inserted: 7
 
After Insert: 7
key: 1
key: 3 | left child: 1
key: 5 | left child: 3
key: 7 | left child: 5 | right child: 8
key: 8 | right child: 9
key: 9
 
Splay Tree Operations
1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 1
Enter value to be inserted: 2
 
After Insert: 2
key: 1
key: 2 | left child: 1 | right child: 5
key: 3
key: 5 | left child: 3 | right child: 7
key: 7 | right child: 8
key: 8 | right child: 9
key: 9
 
Splay Tree Operations
1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 1
Enter value to be inserted: 4
 
After Insert: 4
key: 1
key: 2 | left child: 1
key: 3 | left child: 2
key: 4 | left child: 3 | right child: 5
key: 5 | right child: 7
key: 7 | right child: 8
key: 8 | right child: 9
key: 9
 
Splay Tree Operations
1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 1
Enter value to be inserted: 10
 
After Insert: 10
key: 1
key: 2 | left child: 1
key: 3 | left child: 2
key: 4 | left child: 3
key: 5 | left child: 4 | right child: 8
key: 7
key: 8 | left child: 7
key: 9 | left child: 5
key: 10 | left child: 9
 
Splay Tree Operations
1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 1
Enter value to be inserted: 6
 
After Insert: 6
key: 1
key: 2 | left child: 1
key: 3 | left child: 2
key: 4 | left child: 3
key: 5 | left child: 4
key: 6 | left child: 5 | right child: 7
key: 7 | right child: 9
key: 8
key: 9 | left child: 8 | right child: 10
key: 10
 
Splay Tree Operations
1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 2
Enter value to be deleted: 5
 
After Delete: 5
key: 1
key: 2 | left child: 1
key: 3 | left child: 2
key: 4 | left child: 3 | right child: 6
key: 6 | right child: 7
key: 7 | right child: 9
key: 8
key: 9 | left child: 8 | right child: 10
key: 10
 
Splay Tree Operations
1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 2
Enter value to be deleted: 10
 
After Delete: 10
key: 1
key: 2 | left child: 1
key: 3 | left child: 2
key: 4 | left child: 3
key: 6 | left child: 4 | right child: 7
key: 7 | right child: 8
key: 8
key: 9 | left child: 6
 
Splay Tree Operations
1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 3
Enter value to be searched: 9
 
After Search 9
key: 1
key: 2 | left child: 1
key: 3 | left child: 2
key: 4 | left child: 3
key: 6 | left child: 4 | right child: 7
key: 7 | right child: 8
key: 8
key: 9 | left child: 6
 
Splay Tree Operations
1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 4
 
------------------
(program exited with code: 1)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

If you wish to look at all C++ Programming examples, go to C++ Programs.

« Prev - C++ Program to Implement Segment Tree

» Next - C++ Program to Implement Suffix Tree

Related Posts:

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

Recommended Articles: