SplayInsertSearch.cpp

//splay tree implementation
//Insert operation
//Search operation

//delete not splay nodes

#include<iostream>
using namespace std;

struct Node
{
   int data;
   Node* left;
   Node* right;

   public:
   Node(int d,Node* lp = NULL, Node* rp = NULL)
   {
      data = d;
      left = lp;
      right = rp;
   }
};

//     y
//      \
//       x
//      /\
//    T1  T2

Node* leftrotate(Node* y)
{
  Node* x = y->right;
  Node *t = x->left;
  x->left = y;
  y->right = t;
  return x;
}
//       y
//      /
//      X
//     / \
//    T1  T2
Node* rightrotate(Node* y)
{
  Node* x = y->left;
  Node *t = x->right;
  x->right = y;
  y->left = t;
  return x;
}

Node* splay(Node* root, int k)
{

   if(root == NULL || root->data == k)
   {
      return root;
   }
   if(root->data > k)
   {
      if(root->left == NULL)
      {
         return root;
      }
      if(root->left->data == k)
      {
         return root->left;
      }


      if(root->left->data > k)
      {
          root->left->left = splay(root->left->left,k);

          root = rightrotate(root);
      }
      else
      {
         root->left->right = splay(root->left->right,k);

         if(root->left->right != NULL)
         {
            root->left = leftrotate(root->left);
         }
      }

      return root->left == NULL ? root : rightrotate(root);
   }
   else
   {
      if(root->right == NULL)
      {
         return root;
      }
      if(root->right->data == k)
      {
         return root->right;
      }


      if(root->right->data > k)
      {

         root->right->left = splay(root->right->left,k);
         if(root->right->left != NULL)
         {
            root->right = rightrotate(root->right);
         }
      }
      else
      {
          root->right->right = splay(root->right->right,k);
          root = leftrotate(root);

      }

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

Node* Insert(Node* root, int data)
{
    if(root == NULL)
    {
         return new Node(data,NULL,NULL);
    }

  root = splay(root,data);

  if(root->data == data) return root;


   Node* temp = new Node(data,NULL,NULL);

   if(root->data > data)
   {
       temp->right = root;
       temp->left = root->left;
       root->left = NULL;
   }
   else
   {
      temp->left = root;
      temp->right = root->right;
      root->right = NULL;

   }
   return temp;
}

Node* search1(Node* root, int k)
{
   if(root == NULL || root->data == k)
   {
      return root;
   }

   return splay(root,k);
}
int main()
{
   Node* root = NULL;

   root = Insert(root,10);
   cout<<"  10  "<<root->data<<"  "<<endl;
   root = Insert(root,5);
   cout<<"  5  "<<root->data<<"  "<<endl;
   root = Insert(root,15);
   cout<<"  15  "<<root->data<<"  "<<endl;
   root = Insert(root,3);
   cout<<"  3  "<<root->data<<"  "<<endl;
   root = Insert(root,1);
   cout<<"  1  "<<root->data<<"  "<<endl;
   root = Insert(root,2);
   cout<<"  2  "<<root->data<<"  "<<endl;
   root = Insert(root,13);
   cout<<"  13  "<<root->data<<"  "<<endl;
   root = Insert(root,11);
   cout<<"  11  "<<root->data<<"  "<<endl;

   root = search1(root,15);
   root = search1(root,35);
   cout<<root->data<<endl;

   return 0;
}