C Program to Perform Left and Right Rotation on a Binary Search Tree

«
»
This is a C Program to Perform Left and Right Rotation on a Binary Search Tree. These trees are binary search trees in which the height of two siblings are not allowed to differ by more than one.

Here is source code of the C Program to Perform Left Rotation on a Binary Search Tree. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. #include<conio.h>
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4.  
  5. typedef struct node {
  6.     int data;
  7.     struct node *left, *right;
  8.     int ht;
  9. } node;
  10.  
  11. node *insert(node *, int);
  12. node *Delete(node *, int);
  13. void preorder(node *);
  14. void inorder(node *);
  15. int height(node *);
  16. node *rotateright(node *);
  17. node *rotateleft(node *);
  18. node *RR(node *);
  19. node *LL(node *);
  20. node *LR(node *);
  21. node *RL(node *);
  22. int BF(node *);
  23.  
  24. int main() {
  25.     node *root = NULL;
  26.     int x, n, i, op;
  27.     do {
  28.         printf("\n1)Create:");
  29.         printf("\n2)Insert:");
  30.         printf("\n3)Delete:");
  31.         printf("\n4)Print:");
  32.         printf("\n5)Quit:");
  33.         printf("\n\nEnter Your Choice:");
  34.         scanf("%d", &op);
  35.         switch (op) {
  36.         case 1:
  37.             printf("\nEnter no. of elements:");
  38.             scanf("%d", &n);
  39.             printf("\nEnter tree data:");
  40.             root = NULL;
  41.             for (i = 0; i < n; i++) {
  42.                 scanf("%d", &x);
  43.                 root = insert(root, x);
  44.             }
  45.             break;
  46.         case 2:
  47.             printf("\nEnter a data:");
  48.             scanf("%d", &x);
  49.             root = insert(root, x);
  50.             break;
  51.         case 3:
  52.             printf("\nEnter a data:");
  53.             scanf("%d", &x);
  54.             root = Delete(root, x);
  55.             break;
  56.         case 4:
  57.             printf("\nPreorder sequence:\n");
  58.             preorder(root);
  59.             printf("\n\nInorder sequence:\n");
  60.             inorder(root);
  61.             printf("\n");
  62.             break;
  63.         }
  64.  
  65.     } while (op != 5);
  66.  
  67.     return 0;
  68. }
  69. node * insert(node *T, int x) {
  70.     if (T == NULL) {
  71.         T = (node*) malloc(sizeof(node));
  72.         T->data = x;
  73.         T->left = NULL;
  74.         T->right = NULL;
  75.     } else if (x > T->data) // insert in right subtree
  76.     {
  77.         T->right = insert(T->right, x);
  78.         if (BF(T) == -2) {
  79.             if (x > T->right->data)
  80.                 T = RR(T);
  81.             else
  82.                 T = RL(T);
  83.         }
  84.     } else if (x < T->data) {
  85.         T->left = insert(T->left, x);
  86.         if (BF(T) == 2) {
  87.             if (x < T->left->data)
  88.                 T = LL(T);
  89.             else
  90.                 T = LR(T);
  91.         }
  92.     }
  93.     T->ht = height(T);
  94.     return (T);
  95. }
  96.  
  97. node * Delete(node *T, int x) {
  98.     node * p;
  99.  
  100.     if (T == NULL) {
  101.         return NULL;
  102.     } else
  103.  
  104.     if (x > T->data) // insert in right subtree
  105.     {
  106.         T->right = Delete(T->right, x);
  107.         if (BF(T) == 2) {
  108.             if (BF(T->left) >= 0)
  109.                 T = LL(T);
  110.             else
  111.                 T = LR(T);
  112.         }
  113.     } else if (x < T->data) {
  114.         T->left = Delete(T->left, x);
  115.         if (BF(T) == -2)//Rebalance during windup
  116.         {
  117.             if (BF(T->right) <= 0)
  118.                 T = RR(T);
  119.             else
  120.                 T = RL(T);
  121.         }
  122.     } else {
  123.         //data to be deleted is found
  124.         if (T->right != NULL) { //delete its inordersuccesor
  125.             p = T->right;
  126.             while (p->left != NULL)
  127.                 p = p->left;
  128.  
  129.             T->data = p->data;
  130.             T->right = Delete(T->right, p->data);
  131.             if (BF(T) == 2)//Rebalance during windup
  132.             {
  133.                 if (BF(T->left) >= 0)
  134.                     T = LL(T);
  135.                 else
  136.                     T = LR(T);
  137.             }
  138.         } else
  139.             return (T->left);
  140.  
  141.     }
  142.     T->ht = height(T);
  143.     return (T);
  144. }
  145.  
  146. int height(node *T) {
  147.     int lh, rh;
  148.     if (T == NULL)
  149.         return (0);
  150.     if (T->left == NULL)
  151.         lh = 0;
  152.     else
  153.         lh = 1 + T->left->ht;
  154.     if (T->right == NULL)
  155.         rh = 0;
  156.     else
  157.         rh = 1 + T->right->ht;
  158.     if (lh > rh)
  159.         return (lh);
  160.     return (rh);
  161. }
  162. node * rotateright(node *x) {
  163.     node * y;
  164.     y = x->left;
  165.     x->left = y->right;
  166.     y->right = x;
  167.     x->ht = height(x);
  168.     y->ht = height(y);
  169.     printf("rotate right\n");
  170.     return (y);
  171. }
  172. node * rotateleft(node *x) {
  173.     node * y;
  174.     y = x->right;
  175.     x->right = y->left;
  176.     y->left = x;
  177.     x->ht = height(x);
  178.     y->ht = height(y);
  179.     printf("rotate left\n");
  180.     return (y);
  181. }
  182. node * RR(node *T) {
  183.     T = rotateleft(T);
  184.     printf("rotate right right\n");
  185.     return (T);
  186. }
  187. node * LL(node *T) {
  188.     T = rotateright(T);
  189.     printf("rotate left left\n");
  190.     return (T);
  191. }
  192. node * LR(node *T) {
  193.     T->left = rotateleft(T->left);
  194.     T = rotateright(T);
  195.     printf("rotate left right\n");
  196.     return (T);
  197. }
  198. node * RL(node *T) {
  199.     T->right = rotateright(T->right);
  200.     T = rotateleft(T);
  201.     printf("rotate right left\n");
  202.     return (T);
  203. }
  204. int BF(node *T) {
  205.     int lh, rh;
  206.     if (T == NULL)
  207.         return (0);
  208.     if (T->left == NULL)
  209.         lh = 0;
  210.     else
  211.         lh = 1 + T->left->ht;
  212.     if (T->right == NULL)
  213.         rh = 0;
  214.     else
  215.         rh = 1 + T->right->ht;
  216.     return (lh - rh);
  217. }
  218. void preorder(node *T) {
  219.     if (T != NULL) {
  220.         printf("%d(Bf=%d) ", T->data, BF(T));
  221.         preorder(T->left);
  222.         preorder(T->right);
  223.     }
  224. }
  225. void inorder(node *T) {
  226.     if (T != NULL) {
  227.         inorder(T->left);
  228.         printf("%d(Bf=%d) ", T->data, BF(T));
  229.         inorder(T->right);
  230.     }
  231.  
  232. }

Output:

$ gcc AVLLeftRotation.c
$ ./a.out
 
1)Create:
2)Insert:
3)Delete:
4)Print:
5)Quit:
 
Enter Your Choice: 1
Enter no. of elements: 5
Enter tree data: 23 76 26 256 78
rotate right
rotate left
rotate right left
rotate right
rotate left
rotate right left
 
1)Create:
2)Insert:
3)Delete:
4)Print:
5)Quit:
 
Enter Your Choice: 2
Enter a data: 94
rotate left
rotate right right
 
1)Create:
2)Insert:
3)Delete:
4)Print:
5)Quit:
 
Enter Your Choice: 5

Sanfoundry Global Education & Learning Series – 1000 C Programs.

advertisement
advertisement

Here’s the list of Best Books in C Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.