// The code is adopted from http://goo.gl/SDH9hH
// https://www.geeksforgeeks.org/splay-tree-set-2-insert-delete/
//

#include<stdio.h>
#include<stdlib.h>
 
typedef struct node
{
  int key;
  struct node *left, *right;
} tnode;
 
/* Helper function that allocates a new node with the given key and
  NULL left and right pointers. */
tnode *new_node(int key)
{
  tnode* node = (tnode*)malloc(sizeof(tnode));
  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.
tnode *rotate_right(tnode *x)
{
  tnode *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.
tnode *rotate_left(tnode *x)
{
  tnode *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
tnode *splay(tnode *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 = rotate_right(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 = rotate_left(root->left);
    }
 
    // Do second rotation for root
    return (root->left == NULL)? root: rotate_right(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 = rotate_right(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 = rotate_left(root);
    }
 
    // Do second rotation for root
    return (root->right == NULL)? root: rotate_left(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.
tnode *search(tnode *root, int key)
{
  return splay(root, key);
}

// Function to insert a new key k in splay tree with given root
tnode *insert(tnode *root, int k)
{
  // Simple Case: If tree is empty
  if (root == NULL) return new_node(k);
 
  // Bring the closest leaf node to root
  root = splay(root, k);
 
  // If key is already present, then return
  if (root->key == k) return root;
 
  // Otherwise allocate memory for new node
  tnode *newnode  = new_node(k);
 
  // If root's key is greater, make root as right child
  // of newnode and copy the left child of root to newnode
  if (root->key > k)
  {
    newnode->right = root;
    newnode->left = root->left;
    root->left = NULL;
  }
 
  // If root's key is smaller, make root as left child
  // of newnode and copy the right child of root to newnode
  else
  {
    newnode->left = root;
    newnode->right = root->right;
    root->right = NULL;
  }
 
  return newnode; // newnode becomes new root
}
 
// The delete function for Splay tree. Note that this function
// returns the new root of Splay Tree after removing the key 
tnode* delete_key(tnode *root, int key)
{
  tnode *temp;
  if (!root)
    return NULL;
   
  // Splay the given key  
  root = splay(root, key);
   
  // If key is not present, then
  // return root
  if (key != root->key)
    return root;
     
  // If key is present
  // If left child of root does not exist
  // make root->right as root   
  if (!root->left)
  {
    temp = root;
    root = root->right;
  }
   
  // Else if left child exits
  else
  {
    temp = root;
 
    /*Note: Since key == root->key,
    so after Splay(key, root->lchild),
    the tree we get will have no right child tree
    and maximum node in left subtree will get splayed*/
    // New root
    root = splay(root->left, key);
     
    // Make right child of previous root  as
    // new root's right child
    root->right = temp->right;
  }
   
  // free the previous root node, that is,
  // the node containing the key
  free(temp);
   
  // return root of the new Splay Tree
  return root;
   
} 

void display_tree(tnode *root, int prelen) {
  if (root) {
    int i;
    for (i = 0; i < prelen; i++) printf("%c", ' ');
    printf("%s", "|___");
    printf("%d\n", root->key);
    display_tree(root->left, prelen + 4);
    display_tree(root->right, prelen + 4);
  }
} 
 
// A utility function to print preorder traversal of the tree.
// The function also prints height of every node
void print_preorder(tnode *root)
{
  if (root != NULL)
  {
    printf("%d ", root->key);
    print_preorder(root->left);
    print_preorder(root->right);
  }
}
 
/* Drier program to test above function*/
int main()
{  
  tnode *root = NULL; 
  int i=0;
  for (i = 1; i<10; i++) {
    root = insert(root, i);
  }
  printf("Splay tree after insertion:\n");
  //print_preorder(root);
  display_tree(root, 0);
  
  printf("\n");
  for (i = 1; i<10; i++) {
    if (i%2 == 0)
     root = delete_key(root, i);
  }
  printf("Splay tree after deletion:\n");
  //print_preorder(root);
  display_tree(root, 0);
  
  printf("\nSplay tree search:\n");
  for (i = 1; i<10; i++) {
    root = search(root, i);
    if (root->key == i)
    printf("found %d\n", i);
    else 
      printf("not found %d\n", i);
  }

  return 0;
}

/*
Splay tree after insertion:
|___9
  |___8
    |___7
      |___6
        |___5
          |___4
            |___3
              |___2
                |___1

Splay tree after deletion:
|___7
  |___5
    |___3
      |___1
  |___9

Splay tree search:
found 1
not found 2
found 3
not found 4
found 5
not found 6
found 7
not found 8
found 9
*/