fork(20) download
copy 
  1. /* Author: Prakhar Jain */
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4.  
  5. #define RED		1
  6. #define BLACK	2
  7.  
  8. struct node {
  9. 	int key;
  10. 	struct node *left, *right, *p;
  11. 	int color;
  12. };
  13.  
  14. typedef struct node *NODEPTR;
  15. struct node NIL;
  16. NODEPTR NILPTR = &NIL;
  17.  
  18. void inorder(NODEPTR x) {
  19. 	if (x != NILPTR) {
  20. 		inorder(x->left);
  21. 		printf("%d ", x->key);
  22. 		inorder(x->right);
  23. 	}
  24. }
  25.  
  26. NODEPTR search(NODEPTR root, int k) {
  27. 	if (root == NILPTR || root->key == k)
  28. 		return root;
  29. 	if (k < root->key)
  30. 		return search(root->left, k);
  31. 	else
  32. 		return search(root->right, k);
  33. }
  34.  
  35. NODEPTR minimum(NODEPTR root) {
  36. 	while (root->left != NILPTR)
  37. 		root = root->left;
  38. 	return root;
  39. }
  40.  
  41. NODEPTR maximum(NODEPTR root) {
  42. 	while (root->right != NILPTR)
  43. 		root = root->right;
  44. 	return root;
  45. }
  46.  
  47. NODEPTR successor(NODEPTR root, int x) {
  48. 	NODEPTR temp = search(root, x);
  49. 	if (temp == NILPTR) {
  50. 		printf("%d not in tree\n", x);
  51. 		return temp;
  52. 	}
  53. 	if (temp->right != NILPTR)
  54. 		return minimum(temp->right);
  55. 	NODEPTR y = temp->p;
  56. 	while (y != NILPTR && temp == y->right) {
  57. 		temp = y;
  58. 		y = y->p;
  59. 	}
  60. 	return y;
  61. }
  62.  
  63. NODEPTR predecessor(NODEPTR root, int x) {
  64. 	NODEPTR temp = search(root, x);
  65. 	if (temp == NILPTR) {
  66. 		printf("%d not in tree\n", x);
  67. 		return temp;
  68. 	}
  69. 	if (temp->left != NILPTR)
  70. 		return maximum(temp->left);
  71. 	NODEPTR y = temp->p;
  72. 	while (y != NILPTR && temp == y->left) {
  73. 		temp = y;
  74. 		y = y->p;
  75. 	}
  76. 	return y;
  77. }
  78. void leftrotate(NODEPTR *treeroot, NODEPTR x) {
  79. 	NODEPTR y = x->right;
  80. 	x->right = y->left;
  81. 	if (y->left != NILPTR)
  82. 		y->left->p = x;
  83. 	y->p = x->p;
  84. 	if (x->p == NILPTR)
  85. 		*treeroot = y;
  86. 	else if (x->p->left == x)
  87. 		x->p->left = y;
  88. 	else
  89. 		x->p->right = y;
  90. 	y->left = x;
  91. 	x->p = y;
  92. }
  93.  
  94. void rightrotate(NODEPTR *treeroot, NODEPTR y) {
  95. 	NODEPTR x = y->left;
  96. 	y->left = x->right;
  97. 	if (x->right != NILPTR)
  98. 		x->right->p = y;
  99. 	x->p = y->p;
  100. 	if (y->p == NILPTR)
  101. 		*treeroot = x;
  102. 	else if (y->p->left == y)
  103. 		y->p->left = x;
  104. 	else
  105. 		y->p->right = x;
  106. 	x->right = y;
  107. 	y->p = x;
  108. }
  109.  
  110. void rbinsertfixup(NODEPTR *treeroot, NODEPTR z) {
  111. 	while (z->p->color == RED) {
  112. 		if (z->p == z->p->p->left) {
  113. 			NODEPTR y = z->p->p->right;
  114. 			if (y->color == RED) {
  115. 				z->p->color = BLACK;
  116. 				y->color = BLACK;
  117. 				z->p->p->color = RED;
  118. 				z = z->p->p;
  119. 			}
  120. 			else {
  121. 				if (z == z->p->right) {
  122. 					z = z->p;
  123. 					leftrotate(treeroot,z);
  124. 				}
  125. 				z->p->color = BLACK;
  126. 				z->p->p->color = RED;
  127. 				rightrotate(treeroot,z->p->p);
  128. 			}
  129. 		}
  130. 		else {
  131. 			NODEPTR y = z->p->p->left;
  132. 			if (y->color == RED) {
  133. 				z->p->color = BLACK;
  134. 				y->color = BLACK;
  135. 				z->p->p->color = RED;
  136. 				z = z->p->p;
  137. 			}
  138. 			else {
  139. 				if (z == z->p->left) {
  140. 					z = z->p;
  141. 					rightrotate(treeroot,z);
  142. 				}
  143. 				z->p->color = BLACK;
  144. 				z->p->p->color = RED;
  145. 				leftrotate(treeroot,z->p->p);
  146. 			}
  147. 		}
  148. 	}
  149. 	(*treeroot)->color = BLACK;
  150. }
  151.  
  152. void rbinsert(NODEPTR *treeroot, int z) {
  153. 	NODEPTR Z = (NODEPTR) malloc(sizeof(struct node));
  154. 	Z->key = z;
  155. 	NODEPTR y = NILPTR;
  156. 	NODEPTR x = *treeroot;
  157. 	while (x != NILPTR) {
  158. 		y = x;
  159. 		if (Z->key < x->key)
  160. 			x = x->left;
  161. 		else
  162. 			x = x->right;
  163. 	}
  164. 	Z->p = y;
  165. 	if (y == NILPTR)
  166. 		*treeroot = Z;
  167. 	else if (Z->key < y->key)
  168. 		y->left = Z;
  169. 	else
  170. 		y->right = Z;
  171. 	Z->left = NILPTR;
  172. 	Z->right = NILPTR;
  173. 	Z->color = RED;
  174. 	rbinsertfixup(treeroot,Z);
  175. }
  176.  
  177. void rbtransplant(NODEPTR *treeroot, NODEPTR u, NODEPTR v) {
  178. 	if (u->p == NILPTR)
  179. 		*treeroot = v;
  180. 	else if (u == u->p->left)
  181. 		u->p->left = v;
  182. 	else
  183. 		u->p->right = v;
  184. 	v->p = u->p;
  185. }
  186.  
  187. void rbdeletefixup(NODEPTR *treeroot, NODEPTR x) {
  188. 	while (x != *treeroot && x->color == BLACK) {
  189. 		if (x == x->p->left) {
  190. 			NODEPTR w = x->p->right;
  191. 			if (w->color == RED) {
  192. 				w->color = BLACK;
  193. 				x->p->color = RED;
  194. 				leftrotate(treeroot,x->p);
  195. 				w = x->p->right;
  196. 			}
  197. 			if (w->left->color == BLACK && w->right->color == BLACK) {
  198. 				w->color = RED;
  199. 				x = x->p;
  200. 			}
  201. 			else {
  202. 			 	if (w->right->color == BLACK) {
  203. 					w->left->color = BLACK;
  204. 					w->color = RED;
  205. 					rightrotate(treeroot,w);
  206. 					w = x->p->right;
  207. 				}
  208. 				w->color = x->p->color;
  209. 				x->p->color = BLACK;
  210. 				w->right->color = BLACK;
  211. 				leftrotate(treeroot,x->p);
  212. 				x = *treeroot;
  213. 			}
  214. 		}
  215. 		else {
  216. 			NODEPTR w = x->p->left;
  217. 			if (w->color == RED) {
  218. 				w->color = BLACK;
  219. 				x->p->color = RED;
  220. 				rightrotate(treeroot,x->p);
  221. 				w = x->p->left;
  222. 			}
  223. 			if (w->left->color == BLACK && w->right->color == BLACK) {
  224. 				w->color = RED;
  225. 				x = x->p;
  226. 			}
  227. 			else {
  228. 				if (w->left->color == BLACK) {
  229. 					w->right->color = BLACK;
  230. 					w->color = RED;
  231. 					leftrotate(treeroot,w);
  232. 					w = x->p->left;
  233. 				}
  234. 				w->color = x->p->color;
  235. 				x->p->color = BLACK;
  236. 				w->left->color = BLACK;
  237. 				rightrotate(treeroot,x->p);
  238. 				x = *treeroot;
  239. 			}
  240. 		}
  241. 	}
  242. 	x->color = BLACK;
  243. }
  244.  
  245. void rbdelete(NODEPTR *treeroot, int z) {
  246. 	NODEPTR Z = search(*treeroot, z);
  247. 	if (Z == NILPTR) {
  248. 		printf("Node to be deleted not found\n");
  249. 		return;
  250. 	}
  251. 	NODEPTR y = Z;
  252. 	int yoc = y->color;
  253. 	NODEPTR x;
  254. 	if (Z->left == NILPTR) {
  255. 		x = Z->right;
  256. 		rbtransplant(treeroot,Z,Z->right);
  257. 	}
  258. 	else if (Z->right == NILPTR) {
  259. 		x = Z->left;
  260. 		rbtransplant(treeroot,Z,Z->left);
  261. 	}
  262. 	else {
  263. 		y = minimum(Z->right);
  264. 		yoc = y->color;
  265. 		x = y->right;
  266. 		if (y->p == Z)
  267. 			x->p = y;
  268. 		else {
  269. 			rbtransplant(treeroot,y,y->right);
  270. 			y->right = Z->right;
  271. 			y->right->p = y;
  272. 		}
  273. 		rbtransplant(treeroot,Z,y);
  274. 		y->left = Z->left;
  275. 		y->left->p = y;
  276. 		y->color = Z->color;
  277. 	}
  278. 	if (yoc == BLACK)
  279. 		rbdeletefixup(treeroot,x);
  280. }
  281.  
  282. main()
  283. {
  284. 	NIL.left = NIL.right = NIL.p = NILPTR;
  285. 	NIL.color = BLACK;
  286. 	NODEPTR tree = NILPTR;
  287. 	int n;
  288. 	while (1) {
  289. 		printf("1.Insert\n2.Search\n3.Inorder Walk\n4.Minimum\n5.Maximum\n6.Successor\n7.Predecessor\n8.Delete\n9.Exit\n");
  290. 		scanf("%d", &n);
  291. 		if (n == 1) {
  292. 			printf("Enter any number:\n");
  293. 			int num;
  294. 			scanf("%d", &num);
  295. 			rbinsert(&tree, num);
  296. 		}
  297. 		else if (n == 2) {
  298. 			printf("Enter the number to be search\n");
  299. 			int num;
  300. 			scanf("%d", &num);
  301. 			if (search(tree, num) == NILPTR)
  302. 				printf("%d not found\n", num);
  303. 			else
  304. 				printf("%d found\n", num);
  305. 		}
  306. 		else if (n == 3) {
  307. 			inorder(tree);
  308. 			printf("\n");
  309. 		}
  310. 		else if (n == 4)
  311. 			printf("%d\n", minimum(tree)->key);
  312. 		else if (n == 5)
  313. 			printf("%d\n", maximum(tree)->key);
  314. 		else if (n == 6) {
  315. 			printf("Enter the number whose successor needs to be found\n");
  316. 			int num;
  317. 			scanf("%d", &num);
  318. 			NODEPTR t = successor(tree, num);
  319. 			if (t != NULL)
  320. 				printf("%d\n", t->key);
  321. 		}
  322. 		else if (n == 7) {
  323. 			printf("Enter the number whose predecessor needs to be found\n");
  324. 			int num;
  325. 			scanf("%d", &num);
  326. 			NODEPTR t = predecessor(tree, num);
  327. 			if (t != NULL)
  328. 				printf("%d\n", t->key);
  329. 		}
  330. 		else if (n == 8) {
  331. 			printf("Enter the number to be deleted\n");
  332. 			int num;
  333. 			scanf("%d", &num);
  334. 			rbdelete(&tree, num);
  335. 		}
  336. 		else 
  337. 			break;
  338. 	}
  339. 	return 0;
  340. }
  341.  
Success #stdin #stdout 0s 2256KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1.Insert
2.Search
3.Inorder Walk
4.Minimum
5.Maximum
6.Successor
7.Predecessor
8.Delete
9.Exit
https://ideone.com/mr7juv
language:
C (gcc 8.3)
created:
10 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!