fork download
  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
stdin
Standard input is empty
stdout
Preorder traversal of the modified Splay tree is 
20 50 30 40 100 200