C++ Program to Implement Splay Tree

«
»
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.

  1. /*
  2.  *  C++ Program to Implement Splay Tree
  3.  */
  4.  
  5. #include <iostream>
  6. #include <cstdio>
  7. #include <cstdlib>
  8. using namespace std;
  9.  
  10. struct splay
  11. {
  12.     int key;
  13.     splay* lchild;
  14.     splay* rchild;
  15. };
  16.  
  17. class SplayTree
  18. {
  19.     public:
  20.         SplayTree()
  21.         {
  22.         }
  23.  
  24.         // RR(Y rotates to the right)
  25.         splay* RR_Rotate(splay* k2)
  26.         {
  27.             splay* k1 = k2->lchild;
  28.             k2->lchild = k1->rchild;
  29.             k1->rchild = k2;
  30.             return k1;
  31.         }
  32.  
  33.         // LL(Y rotates to the left)
  34.         splay* LL_Rotate(splay* k2)
  35.         {
  36.             splay* k1 = k2->rchild;
  37.             k2->rchild = k1->lchild;
  38.             k1->lchild = k2;
  39.             return k1;
  40.         }
  41.  
  42.         // An implementation of top-down splay tree
  43.         splay* Splay(int key, splay* root)
  44.         {
  45.             if (!root)
  46.                 return NULL;
  47.             splay header;
  48.             /* header.rchild points to L tree;
  49.             header.lchild points to R Tree */
  50.             header.lchild = header.rchild = NULL;
  51.             splay* LeftTreeMax = &header;
  52.             splay* RightTreeMin = &header;
  53.             while (1)
  54.             {
  55.                 if (key < root->key)
  56.                 {
  57.                     if (!root->lchild)
  58.                         break;
  59.                     if (key < root->lchild->key)
  60.                     {
  61.                         root = RR_Rotate(root);
  62.                         // only zig-zig mode need to rotate once,
  63.                         if (!root->lchild)
  64.                             break;
  65.                     }
  66.                     /* Link to R Tree */
  67.                     RightTreeMin->lchild = root;
  68.                     RightTreeMin = RightTreeMin->lchild;
  69.                     root = root->lchild;
  70.                     RightTreeMin->lchild = NULL;
  71.                 }
  72.                 else if (key > root->key)
  73.                 {
  74.                     if (!root->rchild)
  75.                         break;
  76.                     if (key > root->rchild->key)
  77.                     {
  78.                         root = LL_Rotate(root);
  79.                         // only zag-zag mode need to rotate once,
  80.                         if (!root->rchild)
  81.                             break;
  82.                     }
  83.                     /* Link to L Tree */
  84.                     LeftTreeMax->rchild = root;
  85.                     LeftTreeMax = LeftTreeMax->rchild;
  86.                     root = root->rchild;
  87.                     LeftTreeMax->rchild = NULL;
  88.                 }
  89.                 else
  90.                     break;
  91.             }
  92.             /* assemble L Tree, Middle Tree and R tree */
  93.             LeftTreeMax->rchild = root->lchild;
  94.             RightTreeMin->lchild = root->rchild;
  95.             root->lchild = header.rchild;
  96.             root->rchild = header.lchild;
  97.             return root;
  98.         }
  99.  
  100.         splay* New_Node(int key)
  101.         {
  102.             splay* p_node = new splay;
  103.             if (!p_node)
  104.             {
  105.                 fprintf(stderr, "Out of memory!\n");
  106.                 exit(1);
  107.             }
  108.             p_node->key = key;
  109.             p_node->lchild = p_node->rchild = NULL;
  110.             return p_node;
  111.         }
  112.  
  113.         splay* Insert(int key, splay* root)
  114.         {
  115.             static splay* p_node = NULL;
  116.             if (!p_node)
  117.                 p_node = New_Node(key);
  118.             else
  119.                 p_node->key = key;
  120.             if (!root)
  121.             {
  122.                 root = p_node;
  123.                 p_node = NULL;
  124.                 return root;
  125.             }
  126.             root = Splay(key, root);
  127.             /* This is BST that, all keys <= root->key is in root->lchild, all keys >
  128.             root->key is in root->rchild. */
  129.             if (key < root->key)
  130.             {
  131.                 p_node->lchild = root->lchild;
  132.                 p_node->rchild = root;
  133.                 root->lchild = NULL;
  134.                 root = p_node;
  135.             }
  136.             else if (key > root->key)
  137.             {
  138.                 p_node->rchild = root->rchild;
  139.                 p_node->lchild = root;
  140.                 root->rchild = NULL;
  141.                 root = p_node;
  142.             }
  143.             else
  144.                 return root;
  145.             p_node = NULL;
  146.             return root;
  147.         }
  148.  
  149.         splay* Delete(int key, splay* root)
  150.         {
  151.             splay* temp;
  152.             if (!root)
  153.                 return NULL;
  154.             root = Splay(key, root);
  155.             if (key != root->key)
  156.                 return root;
  157.             else
  158.             {
  159.                 if (!root->lchild)
  160.                 {
  161.                     temp = root;
  162.                     root = root->rchild;
  163.                 }
  164.                 else
  165.                 {
  166.                     temp = root;
  167.                     /*Note: Since key == root->key,
  168.                     so after Splay(key, root->lchild),
  169.                     the tree we get will have no right child tree.*/
  170.                     root = Splay(key, root->lchild);
  171.                     root->rchild = temp->rchild;
  172.                 }
  173.                 free(temp);
  174.                 return root;
  175.             }
  176.         }
  177.  
  178.         splay* Search(int key, splay* root)
  179.         {
  180.             return Splay(key, root);
  181.         }
  182.  
  183.         void InOrder(splay* root)
  184.         {
  185.             if (root)
  186.             {
  187.                 InOrder(root->lchild);
  188.                 cout<< "key: " <<root->key;
  189.                 if(root->lchild)
  190.                     cout<< " | left child: "<< root->lchild->key;
  191.                 if(root->rchild)
  192.                     cout << " | right child: " << root->rchild->key;
  193.                 cout<< "\n";
  194.                 InOrder(root->rchild);
  195.             }
  196.         }
  197. };
  198.  
  199. int main()
  200. {
  201.     SplayTree st;
  202.     int vector[10] = {9,8,7,6,5,4,3,2,1,0};
  203.     splay *root;
  204.     root = NULL;
  205.     const int length = 10;
  206.     int i;
  207.     for(i = 0; i < length; i++)
  208.         root = st.Insert(vector[i], root);
  209.     cout<<"\nInOrder: \n";
  210.     st.InOrder(root);
  211.     int input, choice;
  212.     while(1)
  213.     {
  214.         cout<<"\nSplay Tree Operations\n";
  215.         cout<<"1. Insert "<<endl;
  216.         cout<<"2. Delete"<<endl;
  217.         cout<<"3. Search"<<endl;
  218.         cout<<"4. Exit"<<endl;
  219.         cout<<"Enter your choice: ";
  220.         cin>>choice;
  221.         switch(choice)
  222.         {
  223.         case 1:
  224.             cout<<"Enter value to be inserted: ";
  225.             cin>>input;
  226.             root = st.Insert(input, root);
  227.             cout<<"\nAfter Insert: "<<input<<endl;
  228.             st.InOrder(root);
  229.             break;
  230.         case 2:
  231.             cout<<"Enter value to be deleted: ";
  232.             cin>>input;
  233.             root = st.Delete(input, root);
  234.             cout<<"\nAfter Delete: "<<input<<endl;
  235.             st.InOrder(root);
  236.             break;
  237.         case 3:
  238.             cout<<"Enter value to be searched: ";
  239.             cin>>input;
  240.             root = st.Search(input, root);
  241.             cout<<"\nAfter Search "<<input<<endl;
  242.             st.InOrder(root);
  243.             break;
  244.  
  245.         case 4:
  246.             exit(1);
  247.         default:
  248.             cout<<"\nInvalid type! \n";
  249.         }
  250.     }
  251.     cout<<"\n";
  252.     return 0;
  253. }

advertisement
$ 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.

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

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn