fork download
copy 
  1.   #include <stdio.h>
  2.   #include <stdlib.h>
  3.  
  4.   enum nodeColor {
  5.         RED,
  6.         BLACK
  7.   };
  8.  
  9.   struct rbNode {
  10.         int data, color;
  11.         struct rbNode *link[3];
  12.   };
  13.  
  14.   struct rbNode *root = NULL;
  15.  
  16.   struct rbNode * createNode(int data) {
  17.         struct rbNode *newnode;
  18.         newnode = (struct rbNode *)malloc(sizeof(struct rbNode));
  19.         newnode->data = data;
  20.         newnode->color = RED;
  21.         newnode->link[0] = newnode->link[1]=newnode->link[2] = NULL;
  22.         return newnode;
  23.   }
  24.  
  25.   void insertion (int data) {
  26.         struct rbNode *stack[98],*zptr, *ptr, *newnode, *xPtr, *yPtr,*a;
  27.         int dir[98], ht = 0, index;
  28.         ptr = root;
  29.         if (!root) {
  30.                 root = createNode(data);
  31.                 return;
  32.         }
  33.         stack[ht] = root;
  34.         dir[ht++] = 0;
  35.         /* find the place to insert the new node */
  36.         while (ptr != NULL) {
  37.                 if (ptr->data == data) {
  38.                         printf("Duplicates Not Allowed!!\n");
  39.                         return;
  40.                 }
  41.                 index = (data - ptr->data) > 0 ? 1 : 0;
  42.                 a=ptr->data;
  43.                 stack[ht] = ptr;
  44.                 ptr = ptr->link[index];
  45.                 ptr->link[2]=a;
  46.                 dir[ht++] = index;
  47.  
  48.         }
  49.         /* insert the new node */
  50.         stack[ht - 1]->link[index] = newnode = createNode(data);
  51.         while ((ht >= 3) && (stack[ht - 1]->color == RED)) {
  52.                 if (dir[ht - 2] == 0) {
  53.                         yPtr = stack[ht - 2]->link[1];
  54.                         if (yPtr != NULL && yPtr->color == RED) {
  55.  
  56.                                 stack[ht - 2]->color = RED;
  57.                                 stack[ht - 1]->color = yPtr->color = BLACK;
  58.                                 ht = ht -2;
  59.                         } else {
  60.                                 if (dir[ht - 1] == 0) {
  61.                                         yPtr = stack[ht - 1];
  62.                                 } else {
  63.  
  64.                                         xPtr = stack[ht - 1];
  65.                                         yPtr = xPtr->link[1];
  66.                                         yPtr->link[0]->link[2]=xPtr;
  67.                                         xPtr->link[1] = yPtr->link[0];
  68.                                         yPtr->link[0] = xPtr;
  69.                                         stack[ht - 2]->link[0] = yPtr;
  70.                                         zptr=xPtr->link[2];
  71.                                         xPtr->link[2]=yPtr;
  72.                                         yPtr->link[2]=zptr;
  73.                                 }
  74.  
  75.                                 xPtr = stack[ht - 2];
  76.                                 xPtr->color = RED;
  77.                                 yPtr->color = BLACK;
  78.                                 yPtr->link[0]->link[2]=xPtr;
  79.                                 xPtr->link[0] = yPtr->link[1];
  80.                                 zptr=xPtr->link[2];
  81.                                 yPtr->link[1] = xPtr;
  82.                                 xPtr->link[2]=yPtr;
  83.                                 if (xPtr == root) {
  84.                                         root = yPtr;
  85.                                         yPtr->link[2]=NULL;
  86.                                 } else {
  87.                                         stack[ht - 3]->link[dir[ht - 3]] = yPtr;
  88.                                         yPtr->link[2]=zptr;
  89.                                 }
  90.                                 break;
  91.                         }
  92.                 } else {
  93.                         yPtr = stack[ht - 2]->link[0];
  94.                         if ((yPtr != NULL) && (yPtr->color == RED)) {
  95.                                 stack[ht - 2]->color = RED;
  96.                                 stack[ht - 1]->color = yPtr->color = BLACK;
  97.                                 ht = ht - 2;
  98.                         } else {
  99.                                 if (dir[ht - 1] == 1) {
  100.                                         yPtr = stack[ht - 1];
  101.                                 } else {
  102.  
  103.                                         xPtr = stack[ht - 1];
  104.                                         yPtr = xPtr->link[0];
  105.                                         yPtr->link[0]->link[2]=xPtr;
  106.                                         xPtr->link[0] = yPtr->link[1];
  107.                                         zptr=xPtr->link[2];
  108.                                         yPtr->link[1] = xPtr;
  109.                                         xPtr->link[2]=yPtr;
  110.                                         yPtr->link[2]=zptr;
  111.                                         stack[ht - 2]->link[1] = yPtr;
  112.                                 }
  113.  
  114.                                 xPtr = stack[ht - 2];
  115.                                 yPtr->color = BLACK;
  116.                                 xPtr->color = RED;
  117.                                 yPtr->link[0]->link[2]=xPtr;
  118.  
  119.                                 xPtr->link[1] = yPtr->link[0];
  120.                                 zptr=xPtr->link[2];
  121.  
  122.                                 yPtr->link[0] = xPtr;
  123.                                 xPtr->link[2]=yPtr;
  124.  
  125.                                 if (xPtr == root) {
  126.                                         root = yPtr;
  127.                                         yPtr->link[2]=NULL;
  128.                                 } else {
  129.                                         stack[ht - 3]->link[dir[ht - 3]] = yPtr;
  130.                                         yPtr->link[2]=zptr;
  131.                                 }
  132.                                 break;
  133.                         }
  134.                 }
  135.         }
  136.         root->color = BLACK;
  137.   }
  138.  
  139.   void print(struct rbNode * root)
  140.   {
  141.   		if (root != NULL)
  142.   		{
  143.   			print(root->link[0]);
  144.   			printf("%d %s ", root->data, root->color);
  145.   			if (root->link[2] == NULL)
  146.   			{
  147.   				printf("NIL\n");
  148.   			}
  149.   			else
  150.   			{
  151.   				printf("%d\n", (root->link[2])->data);
  152.   			}
  153.   			print(root->link[1]);
  154.   		}
  155.   		return;
  156.   }
  157.  
  158.   int main() {
  159. 	int n,i;
  160. 	scanf("%d",&n);
  161. 	int a=n;
  162. 	int ar[n];
  163. 	for (i=0;i<a;i++){
  164. 		scanf("%d",&ar[i]);
  165. 		insertion(ar[i]);
  166. 	}
  167.  
  168. 	print(root);
  169. 	return 0;
  170.  
  171. }
  172.  
Runtime error #stdin #stdout 0s 9432KB
comments (?)
stdin
copy 
4 3 6 7 2
stdout
copy 
Standard output is empty
https://ideone.com/V0IFO6
language:
C (gcc 8.3)
created:
6 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!