fork download
copy 
  1. #include<stdio.h> 
  2. #include<stdlib.h> 
  3.  
  4. // An AVL tree node 
  5. struct node 
  6. { 
  7.     int key; 
  8.     struct node *left, *right; 
  9. }; 
  10. struct node* newNode(int key) 
  11. { 
  12.     struct node* node = (struct node*)malloc(sizeof(struct node)); 
  13.     node->key   = key; 
  14.     node->left  = node->right  = NULL; 
  15.     return (node); 
  16. } 
  17.  
  18. struct node *rightRotate(struct node *x) 
  19. { 
  20.     struct node *y = x->left; 
  21.     x->left = y->right; 
  22.     y->right = x; 
  23.     return y; 
  24. } 
  25.  
  26. struct node *leftRotate(struct node *x) 
  27. { 
  28.     struct node *y = x->right; 
  29.     x->right = y->left; 
  30.     y->left = x; 
  31.     return y; 
  32. } 
  33.  
  34. // This function brings the key at root if key is present in tree. 
  35. // If key is not present, then it brings the last accessed item at 
  36. // root.  This function modifies the tree and returns the new root 
  37. struct node *splay(struct node *root, int key) 
  38. { 
  39.     // Base cases: root is NULL or key is present at root 
  40.     if (root == NULL || root->key == key) 
  41.         return root; 
  42.  
  43.     // Key lies in left subtree 
  44.     if (root->key > key) 
  45.     { 
  46.         // Key is not in tree, we are done 
  47.         if (root->left == NULL) return root; 
  48.  
  49.         // Zig-Zig (Left Left) 
  50.         if (root->left->key > key) 
  51.         { 
  52.             // First recursively bring the key as root of left-left 
  53.             root->left->left = splay(root->left->left, key); 
  54.  
  55.             // Do first rotation for root, second rotation is done after else 
  56.             root = rightRotate(root); 
  57.         } 
  58.         else if (root->left->key < key) // Zig-Zag (Left Right) 
  59.         { 
  60.             // First recursively bring the key as root of left-right 
  61.             root->left->right = splay(root->left->right, key); 
  62.  
  63.             // Do first rotation for root->left 
  64.             if (root->left->right != NULL) 
  65.                 root->left = leftRotate(root->left); 
  66.         } 
  67.  
  68.         // Do second rotation for root 
  69.         return (root->left == NULL)? root: rightRotate(root); 
  70.     } 
  71.     else // Key lies in right subtree 
  72.     { 
  73.         // Key is not in tree, we are done 
  74.         if (root->right == NULL) return root; 
  75.  
  76.         // Zag-Zig (Right Left) 
  77.         if (root->right->key > key) 
  78.         { 
  79.             // Bring the key as root of right-left 
  80.             root->right->left = splay(root->right->left, key); 
  81.  
  82.             // Do first rotation for root->right 
  83.             if (root->right->left != NULL) 
  84.                 root->right = rightRotate(root->right); 
  85.         } 
  86.         else if (root->right->key < key)// Zag-Zag (Right Right) 
  87.         { 
  88.             // Bring the key as root of right-right and do first rotation 
  89.             root->right->right = splay(root->right->right, key); 
  90.             root = leftRotate(root); 
  91.         } 
  92.  
  93.         // Do second rotation for root 
  94.         return (root->right == NULL)? root: leftRotate(root); 
  95.     } 
  96. } 
  97.  
  98. // The search function for Splay tree.  Note that this function 
  99. // returns the new root of Splay Tree.  If key is present in tree 
  100. // then, it is moved to root. 
  101. struct node *search(struct node *root, int key) 
  102. { 
  103.     return splay(root, key); 
  104. } 
  105.  
  106. // A utility function to print preorder traversal of the tree. 
  107. // The function also prints height of every node 
  108. void preOrder(struct node *root) 
  109. { 
  110.     if (root != NULL) 
  111.     { 
  112.         printf("%d ", root->key); 
  113.         preOrder(root->left); 
  114.         preOrder(root->right); 
  115.     } 
  116. } 
  117.  
  118. /* Drier program to test above function*/
  119. int main() 
  120. { 
  121.     struct node *root = newNode(100); 
  122.     root->left = newNode(50); 
  123.     root->right = newNode(200); 
  124.     root->left->left = newNode(40); 
  125.     root->left->left->left = newNode(30); 
  126.     root->left->left->left->left = newNode(20); 
  127.  
  128.     root = search(root, 20); 
  129.     printf("Preorder traversal of the modified Splay tree is \n"); 
  130.     preOrder(root); 
  131.     return 0; 
  132. }
Success #stdin #stdout 0s 9424KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Preorder traversal of the modified Splay tree is 
20 50 30 40 100 200
https://ideone.com/utp503
language:
C (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!