red_black_tree.c 16 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568
  1. /*!
  2. Temelia - Red Black Tree implementation source file.
  3. Copyright (C) 2008, 2009 Ceata (http://ceata.org/proiecte/temelia).
  4. @author Dascalu Laurentiu
  5. This program is free software; you can redistribute it and
  6. modify it under the terms of the GNU General Public License
  7. as published by the Free Software Foundation; either version 3
  8. of the License, or (at your option) any later version.
  9. This program is distributed in the hope that it will be useful,
  10. but WITHOUT ANY WARRANTY; without even the implied warranty of
  11. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  12. GNU General Public License for more details.
  13. You should have received a copy of the GNU General Public License
  14. along with this program; if not, write to the Free Software
  15. Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  16. */
  17. #include "include/red_black_tree.h"
  18. #include "include/stack.h"
  19. #include <stdlib.h>
  20. extern stack_t iterating_handlers;
  21. extern stack_t compare_stack;
  22. /*
  23. * Properties of red black trees :
  24. * 1. A node is either red or black.
  25. * 2. The root is black.
  26. * 3. All external nodes are black, even when the parent is black
  27. * (The external nodes are the null value children.)
  28. * 4. Both children of every red node are black.
  29. * 5. Every simple path from a node to a descendant leaf contains
  30. * the same number of black nodes, either counting or not counting
  31. * the null black nodes.
  32. */
  33. struct _red_black_tree_node_t
  34. {
  35. /*! user's key */
  36. void *key;
  37. unsigned int color;
  38. };
  39. #define GET_RED_BLACK_MEMBER(x, member) (((red_black_tree_node_t)(x))->member)
  40. /*!
  41. * Encapsulates user's key into a red black node.
  42. */
  43. static red_black_tree_node_t _red_black_tree_node_new(void *key,
  44. unsigned int color);
  45. static void _red_black_tree_node_delete(red_black_tree_node_t tree_node);
  46. static void _red_black_tree_internal_handling(void *x, void *context);
  47. static void _red_black_tree_internal_printing_level(void *x, int level,
  48. void *contextcontext);
  49. static int _red_black_tree_internal_compare(void *x, void *y, void *context);
  50. void _red_black_tree_set_color(red_black_tree_t red_black_tree,
  51. unsigned int color);
  52. red_black_tree_t red_black_tree_new(void *key)
  53. {
  54. return _binary_tree_new(_red_black_tree_node_new(key, RED));
  55. }
  56. void red_black_tree_delete_node(red_black_tree_t red_black_tree)
  57. {
  58. _ASSERT(red_black_tree, ==, NULL, NULL_POINTER,);
  59. _red_black_tree_node_delete(_binary_tree_get_key(red_black_tree));
  60. _delete(red_black_tree);
  61. }
  62. void red_black_tree_delete(red_black_tree_t red_black_tree)
  63. {
  64. _ASSERT(red_black_tree, ==, NULL, NULL_POINTER,);
  65. red_black_tree_delete(_binary_tree_get_left_child(red_black_tree));
  66. red_black_tree_delete(_binary_tree_get_right_child(red_black_tree));
  67. red_black_tree_delete_node(red_black_tree);
  68. }
  69. int red_black_tree_compare_trees(red_black_tree_t red_black_tree1,
  70. red_black_tree_t red_black_tree2, int compare(void *x, void *y,
  71. void *context), void *context)
  72. {
  73. return _binary_tree_compare_trees(red_black_tree1, red_black_tree2,
  74. compare, context);
  75. }
  76. int red_black_tree_is_empty(red_black_tree_t red_black_tree)
  77. {
  78. _ASSERT(red_black_tree, ==, NULL, NULL_POINTER, -1);
  79. return (_binary_tree_get_parent(red_black_tree) == NULL)
  80. && (_binary_tree_get_left_child(red_black_tree) == NULL)
  81. && (_binary_tree_get_right_child(red_black_tree) == NULL)
  82. && (GET_RED_BLACK_MEMBER(_binary_tree_get_key(red_black_tree), key)
  83. == NULL);
  84. }
  85. int red_black_tree_is_leaf(red_black_tree_t red_black_tree)
  86. {
  87. return _binary_tree_leaf(red_black_tree);
  88. }
  89. int red_black_tree_get_size(red_black_tree_t red_black_tree)
  90. {
  91. return _binary_tree_get_size(red_black_tree);
  92. }
  93. red_black_tree_t red_black_tree_get_root(red_black_tree_t red_black_tree)
  94. {
  95. return _binary_tree_get_root(red_black_tree);
  96. }
  97. void *red_black_tree_get_key(red_black_tree_t red_black_tree)
  98. {
  99. red_black_tree_node_t node;
  100. _ASSERT(red_black_tree, ==, NULL, NULL_POINTER, NULL);
  101. node = _binary_tree_get_key(red_black_tree);
  102. return node->key;
  103. }
  104. unsigned int red_black_tree_get_color(red_black_tree_t red_black_tree)
  105. {
  106. red_black_tree_node_t node;
  107. _ASSERT(red_black_tree, ==, NULL, NULL_POINTER, BLACK);
  108. node = _binary_tree_get_key(red_black_tree);
  109. return node->color;
  110. }
  111. red_black_tree_t red_black_tree_get_parent(red_black_tree_t red_black_tree)
  112. {
  113. return _binary_tree_get_parent(red_black_tree);
  114. }
  115. red_black_tree_t red_black_tree_get_left_child(red_black_tree_t red_black_tree)
  116. {
  117. return _binary_tree_get_left_child(red_black_tree);
  118. }
  119. red_black_tree_t red_black_tree_get_right_child(red_black_tree_t red_black_tree)
  120. {
  121. return _binary_tree_get_right_child(red_black_tree);
  122. }
  123. int red_black_tree_get_height(red_black_tree_t red_black_tree)
  124. {
  125. return _binary_tree_get_height(red_black_tree);
  126. }
  127. int red_black_tree_get_depth(red_black_tree_t red_black_tree)
  128. {
  129. return _binary_tree_get_depth(red_black_tree);
  130. }
  131. red_black_tree_t red_black_tree_search(red_black_tree_t _red_black_tree,
  132. void *key, int compare(void *x, void *y, void *context), void *context)
  133. {
  134. red_black_tree_node_t search_node = _red_black_tree_node_new(key, -1);
  135. red_black_tree_t aux;
  136. stack_push(compare_stack, compare);
  137. aux = _binary_search_tree_search(_red_black_tree, search_node,
  138. _red_black_tree_internal_compare, context);
  139. _red_black_tree_node_delete(search_node);
  140. stack_pop(compare_stack);
  141. return aux;
  142. }
  143. red_black_tree_t red_black_tree_insert(red_black_tree_t *red_black_tree,
  144. void *key, int compare(void *x, void *y, void *context), void *context,
  145. int adjust_root)
  146. {
  147. red_black_tree_t add = NULL, parent = NULL, aux = NULL, var = NULL, save =
  148. NULL;
  149. red_black_tree_node_t add_node = NULL;
  150. _ASSERT(red_black_tree, ==, NULL, NULL_POINTER, NULL);
  151. _ASSERT(compare, ==, NULL, INVALID_INPUT, NULL);
  152. stack_push(compare_stack, compare);
  153. add_node = _red_black_tree_node_new(key, RED);
  154. aux = add = _binary_search_tree_insert(*red_black_tree, add_node,
  155. _red_black_tree_internal_compare, context);
  156. // key already exists - no adding in performed
  157. if (aux == NULL)
  158. {
  159. _red_black_tree_node_delete(add_node);
  160. return NULL;
  161. }
  162. while (add != *red_black_tree && red_black_tree_get_color(add) == RED)
  163. {
  164. parent = _binary_tree_get_parent(add);
  165. if (parent == NULL || add == NULL)
  166. break;
  167. if (add == _binary_tree_get_left_child(parent))
  168. {
  169. var = _binary_tree_get_right_child(parent);
  170. if (red_black_tree_get_color(var) == RED)
  171. {
  172. _red_black_tree_set_color(add, BLACK);
  173. _red_black_tree_set_color(var, BLACK);
  174. _red_black_tree_set_color(parent, RED);
  175. save = parent;
  176. add = _binary_tree_get_parent(parent);
  177. }
  178. else
  179. {
  180. if (save == _binary_tree_get_right_child(add))
  181. {
  182. _self_balanced_binary_search_tree_rotate_left(add);
  183. add = save;
  184. }
  185. _red_black_tree_set_color(add, BLACK);
  186. _red_black_tree_set_color(parent, RED);
  187. _self_balanced_binary_search_tree_rotate_right(parent);
  188. }
  189. }
  190. else
  191. {
  192. var = _binary_tree_get_left_child(parent);
  193. if (red_black_tree_get_color(var) == RED)
  194. {
  195. _red_black_tree_set_color(add, BLACK);
  196. _red_black_tree_set_color(var, BLACK);
  197. _red_black_tree_set_color(parent, RED);
  198. save = parent;
  199. add = _binary_tree_get_parent(parent);
  200. }
  201. else
  202. {
  203. if (save == _binary_tree_get_left_child(add))
  204. {
  205. _self_balanced_binary_search_tree_rotate_right(add);
  206. add = save;
  207. }
  208. _red_black_tree_set_color(add, BLACK);
  209. _red_black_tree_set_color(parent, RED);
  210. _self_balanced_binary_search_tree_rotate_left(parent);
  211. }
  212. }
  213. }
  214. while (adjust_root && _binary_tree_get_parent(*red_black_tree))
  215. (*red_black_tree) = _binary_tree_get_parent(*red_black_tree);
  216. stack_pop(compare_stack);
  217. return aux;
  218. }
  219. int red_black_tree_remove(red_black_tree_t *red_black_tree_, void *key,
  220. int compare(void *x, void *y, void *context), void *context,
  221. int adjust_root)
  222. {
  223. red_black_tree_t replaced = NULL, my_deleted = NULL, brother = NULL;
  224. red_black_tree_node_t key_encapsulated = NULL;
  225. int _end = 0;
  226. if (compare(key, GET_RED_BLACK_MEMBER((*red_black_tree_)->key, key),
  227. context) == 0 && (*red_black_tree_)->parent == NULL
  228. && (*red_black_tree_)->left == NULL && (*red_black_tree_)->right
  229. == NULL)
  230. {
  231. red_black_tree_delete(*red_black_tree_);
  232. *red_black_tree_ = NULL;
  233. return 0;
  234. }
  235. stack_push(compare_stack, compare);
  236. // Remove the node as in a binary search tree and then start tree balancing.
  237. key_encapsulated = _red_black_tree_node_new(key, 0);
  238. replaced = _binary_search_tree_remove(red_black_tree_, key_encapsulated,
  239. _red_black_tree_internal_compare, context, &my_deleted);
  240. _red_black_tree_node_delete(key_encapsulated);
  241. _ASSERT(my_deleted, ==, NULL, ELEMENT_NOT_FOUND, 0);
  242. red_black_tree_delete_node(my_deleted);
  243. /*
  244. * If the replaced node is red, then the red-black property is preserved
  245. * so no root adjusting is required.
  246. */
  247. if (red_black_tree_get_color(replaced) == BLACK && !_end)
  248. {
  249. if (replaced == _binary_tree_get_left_child(_binary_tree_get_parent(
  250. replaced)))
  251. {
  252. brother = _binary_tree_get_right_child(_binary_tree_get_parent(
  253. replaced));
  254. if (brother && red_black_tree_get_color(brother) == RED)
  255. {
  256. _red_black_tree_set_color(brother, BLACK);
  257. _red_black_tree_set_color(_binary_tree_get_parent(replaced),
  258. RED);
  259. _self_balanced_binary_search_tree_rotate_left(
  260. _binary_tree_get_parent(replaced));
  261. }
  262. if (red_black_tree_get_color(_binary_tree_get_left_child(brother))
  263. == BLACK && red_black_tree_get_color(
  264. _binary_tree_get_right_child(brother)) == BLACK)
  265. {
  266. _red_black_tree_set_color(brother, RED);
  267. replaced = _binary_tree_get_parent(replaced);
  268. }
  269. else
  270. {
  271. if (red_black_tree_get_color(_binary_tree_get_right_child(
  272. brother)) == BLACK)
  273. {
  274. _red_black_tree_set_color(_binary_tree_get_left_child(
  275. brother), BLACK);
  276. _red_black_tree_set_color(brother, RED);
  277. _self_balanced_binary_search_tree_rotate_right(brother);
  278. brother = _binary_tree_get_right_child(
  279. _binary_tree_get_parent(replaced));
  280. }
  281. _red_black_tree_set_color(brother, red_black_tree_get_color(
  282. _binary_tree_get_parent(replaced)));
  283. _red_black_tree_set_color(
  284. _binary_tree_get_right_child(brother), BLACK);
  285. _red_black_tree_set_color(_binary_tree_get_parent(replaced),
  286. BLACK);
  287. _self_balanced_binary_search_tree_rotate_left(
  288. _binary_tree_get_parent(replaced));
  289. _end = 1;
  290. }
  291. }
  292. else
  293. {
  294. brother = _binary_tree_get_left_child(_binary_tree_get_parent(
  295. replaced));
  296. if (brother && red_black_tree_get_color(brother) == RED)
  297. {
  298. _red_black_tree_set_color(brother, BLACK);
  299. _red_black_tree_set_color(_binary_tree_get_parent(replaced),
  300. RED);
  301. _self_balanced_binary_search_tree_rotate_right(
  302. _binary_tree_get_parent(replaced));
  303. }
  304. if (red_black_tree_get_color(_binary_tree_get_right_child(brother))
  305. == BLACK && red_black_tree_get_color(
  306. _binary_tree_get_left_child(brother)) == BLACK)
  307. {
  308. _red_black_tree_set_color(brother, RED);
  309. replaced = _binary_tree_get_parent(replaced);
  310. }
  311. else
  312. {
  313. if (red_black_tree_get_color(_binary_tree_get_left_child(
  314. brother)) == BLACK)
  315. {
  316. _red_black_tree_set_color(_binary_tree_get_right_child(
  317. brother), BLACK);
  318. _red_black_tree_set_color(brother, RED);
  319. _self_balanced_binary_search_tree_rotate_left(brother);
  320. brother = _binary_tree_get_left_child(
  321. _binary_tree_get_parent(replaced));
  322. }
  323. _red_black_tree_set_color(brother, red_black_tree_get_color(
  324. _binary_tree_get_parent(replaced)));
  325. _red_black_tree_set_color(
  326. _binary_tree_get_right_child(brother), BLACK);
  327. _red_black_tree_set_color(_binary_tree_get_parent(replaced),
  328. BLACK);
  329. _self_balanced_binary_search_tree_rotate_right(
  330. _binary_tree_get_parent(replaced));
  331. _end = 1;
  332. }
  333. }
  334. }
  335. while (adjust_root && _binary_tree_get_parent(*red_black_tree_))
  336. (*red_black_tree_) = _binary_tree_get_parent(*red_black_tree_);
  337. stack_pop(compare_stack);
  338. return 1;
  339. }
  340. red_black_tree_t red_black_tree_get_min(red_black_tree_t red_black_tree)
  341. {
  342. return _binary_search_tree_get_min(red_black_tree);
  343. }
  344. red_black_tree_t red_black_tree_get_max(red_black_tree_t red_black_tree)
  345. {
  346. return _binary_search_tree_get_max(red_black_tree);
  347. }
  348. void red_black_tree_preorder(red_black_tree_t red_black_tree, void key_handler(
  349. void *x, void *context), void *context)
  350. {
  351. stack_push(iterating_handlers, key_handler);
  352. _binary_tree_preorder(red_black_tree, _red_black_tree_internal_handling,
  353. context);
  354. stack_pop(iterating_handlers);
  355. }
  356. void red_black_tree_inorder(red_black_tree_t red_black_tree, void key_handler(
  357. void *x, void *context), void *context)
  358. {
  359. stack_push(iterating_handlers, key_handler);
  360. _binary_tree_inorder(red_black_tree, _red_black_tree_internal_handling,
  361. context);
  362. stack_pop(iterating_handlers);
  363. }
  364. void red_black_tree_reverse_inorder(red_black_tree_t red_black_tree,
  365. void key_handler(void *x, void *context), void *context)
  366. {
  367. stack_push(iterating_handlers, key_handler);
  368. _binary_tree_reverse_inorder(red_black_tree,
  369. _red_black_tree_internal_handling, context);
  370. stack_pop(iterating_handlers);
  371. }
  372. void red_black_tree_postorder(red_black_tree_t red_black_tree,
  373. void key_handler(void *x, void *context), void *context)
  374. {
  375. stack_push(iterating_handlers, key_handler);
  376. _binary_tree_postorder(red_black_tree, _red_black_tree_internal_handling,
  377. context);
  378. stack_pop(iterating_handlers);
  379. }
  380. void red_black_tree_level_order(red_black_tree_t red_black_tree,
  381. void key_handler(void *x, void *context), void *context)
  382. {
  383. stack_push(iterating_handlers, key_handler);
  384. _binary_tree_level_order(red_black_tree, _red_black_tree_internal_handling,
  385. context);
  386. stack_pop(iterating_handlers);
  387. }
  388. void red_black_tree_show_indented(red_black_tree_t red_black_tree,
  389. void key_handler(void *x, int level, void *context), void *context)
  390. {
  391. stack_push(iterating_handlers, key_handler);
  392. _binary_tree_show_indented(red_black_tree,
  393. _red_black_tree_internal_printing_level, context, 0);
  394. stack_pop(iterating_handlers);
  395. }
  396. static red_black_tree_node_t _red_black_tree_node_new(void *key,
  397. unsigned int color)
  398. {
  399. red_black_tree_node_t red_black_tree;
  400. red_black_tree = (struct _red_black_tree_node_t *) _new(
  401. sizeof(struct _red_black_tree_node_t));
  402. red_black_tree->key = key;
  403. red_black_tree->color = color;
  404. return red_black_tree;
  405. }
  406. static void _red_black_tree_node_delete(
  407. red_black_tree_node_t red_black_tree_node)
  408. {
  409. _ASSERT(red_black_tree_node, ==, NULL, NULL_POINTER,);
  410. _delete(red_black_tree_node);
  411. }
  412. static void _red_black_tree_internal_handling(void *x, void *context)
  413. {
  414. void (*handler)(void *x, void *context);
  415. handler = stack_top(iterating_handlers);
  416. _ASSERT(handler, ==, NULL, NULL_POINTER,);
  417. handler(GET_RED_BLACK_MEMBER(x, key), context);
  418. }
  419. static void _red_black_tree_internal_printing_level(void *x, int level,
  420. void *context)
  421. {
  422. void (*user_printing_function_level)(void *, int, void *);
  423. user_printing_function_level = stack_top(iterating_handlers);
  424. _ASSERT(user_printing_function_level, ==, NULL, NULL_POINTER,);
  425. user_printing_function_level(GET_RED_BLACK_MEMBER(x, key), level, context);
  426. }
  427. static int _red_black_tree_internal_compare(void *x, void *y, void *context)
  428. {
  429. /*
  430. * This is the callback function and can compare red_black_tree_t tree nodes.
  431. *
  432. * For comparing key from nodes, I save the user comparison function in a global pointer.
  433. */
  434. int (*user_comparison_function)(void *, void *, void *);
  435. user_comparison_function = stack_top(compare_stack);
  436. _ASSERT(user_comparison_function, ==, NULL, NULL_POINTER, -1);
  437. return user_comparison_function(GET_RED_BLACK_MEMBER(x, key),
  438. GET_RED_BLACK_MEMBER(y, key), context);
  439. }
  440. void _red_black_tree_set_color(red_black_tree_t red_black_tree,
  441. unsigned int color)
  442. {
  443. red_black_tree_node_t node;
  444. _ASSERT(red_black_tree, ==, NULL, NULL_POINTER,);
  445. node = _binary_tree_get_key(red_black_tree);
  446. node->color = color;
  447. }