aboutsummaryrefslogtreecommitdiff
path: root/src/rb.c
diff options
context:
space:
mode:
authorThomas Schmucker <ts@its1.de>2022-04-10 09:01:30 +0200
committerThomas Schmucker <ts@its1.de>2022-04-10 09:01:30 +0200
commit07e72af6f78d7316eaed828ac0af6f95ac8e4820 (patch)
tree8516dc7673e88a9e3886911fcc6778c62d21acf6 /src/rb.c
parent38f5e364f73967c01f9ed442fe6646e70cb1dde0 (diff)
parent7221289477ba80bfbb9c2c37e43a9d6b1d0e6d17 (diff)
downloaddata-structures-07e72af6f78d7316eaed828ac0af6f95ac8e4820.tar.gz
data-structures-07e72af6f78d7316eaed828ac0af6f95ac8e4820.tar.bz2
data-structures-07e72af6f78d7316eaed828ac0af6f95ac8e4820.zip
Merge branch 'correct-file-names'
Diffstat (limited to 'src/rb.c')
-rw-r--r--src/rb.c614
1 files changed, 0 insertions, 614 deletions
diff --git a/src/rb.c b/src/rb.c
deleted file mode 100644
index 7c2d2c1..0000000
--- a/src/rb.c
+++ /dev/null
@@ -1,614 +0,0 @@
1/*
2 Implementierung übernommen von: https://web.archive.org/web/20140328232325/http://en.literateprograms.org/Red-black_tree_(C)
3 */
4
5#include <stdio.h>
6#include <stdlib.h>
7#include <time.h>
8
9#include "util.h"
10
11/* The authors of this work have released all rights to it and placed it
12in the public domain under the Creative Commons CC0 1.0 waiver
13(http://creativecommons.org/publicdomain/zero/1.0/).
14
15THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
16EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
17MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
18IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
19CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
20TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
21SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
22
23Retrieved from: http://en.literateprograms.org/Red-black_tree_(C)?oldid=19567
24*/
25
26enum rbtree_node_color { RED,
27 BLACK };
28
29typedef struct rbtree_node_t {
30 void * key;
31 void * value;
32 struct rbtree_node_t * left;
33 struct rbtree_node_t * right;
34 struct rbtree_node_t * parent;
35 enum rbtree_node_color color;
36} * rbtree_node;
37
38typedef struct rbtree_t {
39 rbtree_node root;
40} * rbtree;
41
42typedef int (*compare_func)(void *left, void *right);
43
44rbtree rbtree_create();
45void * rbtree_lookup(rbtree t, void *key, compare_func compare);
46void rbtree_insert(rbtree t, void *key, void *value, compare_func compare);
47void rbtree_delete(rbtree t, void *key, compare_func compare);
48
49#include <assert.h>
50#include <stdlib.h>
51
52typedef rbtree_node node;
53typedef enum rbtree_node_color color;
54
55static node grandparent(node n);
56static node sibling(node n);
57static node uncle(node n);
58static void verify_properties(rbtree t);
59static void verify_property_1(node root);
60static void verify_property_2(node root);
61static color node_color(node n);
62static void verify_property_4(node root);
63static void verify_property_5(node root);
64static void verify_property_5_helper(node n, int black_count, int *black_count_path);
65
66static node new_node(void *key, void *value, color node_color, node left, node right);
67static node lookup_node(rbtree t, void *key, compare_func compare);
68static void rotate_left(rbtree t, node n);
69static void rotate_right(rbtree t, node n);
70
71static void replace_node(rbtree t, node oldn, node newn);
72static void insert_case1(rbtree t, node n);
73static void insert_case2(rbtree t, node n);
74static void insert_case3(rbtree t, node n);
75static void insert_case4(rbtree t, node n);
76static void insert_case5(rbtree t, node n);
77static node maximum_node(node root);
78static void delete_case1(rbtree t, node n);
79static void delete_case2(rbtree t, node n);
80static void delete_case3(rbtree t, node n);
81static void delete_case4(rbtree t, node n);
82static void delete_case5(rbtree t, node n);
83static void delete_case6(rbtree t, node n);
84
85node
86grandparent(node n)
87{
88 assert(n != NULL);
89 assert(n->parent != NULL); /* Not the root node */
90 assert(n->parent->parent != NULL); /* Not child of root */
91 return n->parent->parent;
92}
93
94node
95sibling(node n)
96{
97 assert(n != NULL);
98 assert(n->parent != NULL); /* Root node has no sibling */
99 if ( n == n->parent->left )
100 return n->parent->right;
101 else
102 return n->parent->left;
103}
104
105node
106uncle(node n)
107{
108 assert(n != NULL);
109 assert(n->parent != NULL); /* Root node has no uncle */
110 assert(n->parent->parent != NULL); /* Children of root have no uncle */
111 return sibling(n->parent);
112}
113
114void
115verify_properties(rbtree t)
116{
117 (void) t;
118#ifdef VERIFY_RBTREE
119 verify_property_1(t->root);
120 verify_property_2(t->root);
121 /* Property 3 is implicit */
122 verify_property_4(t->root);
123 verify_property_5(t->root);
124#endif
125}
126
127void
128verify_property_1(node n)
129{
130 assert(node_color(n) == RED || node_color(n) == BLACK);
131 if ( n == NULL )
132 return;
133 verify_property_1(n->left);
134 verify_property_1(n->right);
135}
136
137void
138verify_property_2(node root)
139{
140 assert(node_color(root) == BLACK);
141}
142
143color
144node_color(node n)
145{
146 return n == NULL ? BLACK : n->color;
147}
148
149void
150verify_property_4(node n)
151{
152 if ( node_color(n) == RED ) {
153 assert(node_color(n->left) == BLACK);
154 assert(node_color(n->right) == BLACK);
155 assert(node_color(n->parent) == BLACK);
156 }
157 if ( n == NULL )
158 return;
159 verify_property_4(n->left);
160 verify_property_4(n->right);
161}
162
163void
164verify_property_5(node root)
165{
166 int black_count_path = -1;
167 verify_property_5_helper(root, 0, &black_count_path);
168}
169
170void
171verify_property_5_helper(node n, int black_count, int *path_black_count)
172{
173 if ( node_color(n) == BLACK ) {
174 black_count++;
175 }
176 if ( n == NULL ) {
177 if ( *path_black_count == -1 ) {
178 *path_black_count = black_count;
179 }
180 else {
181 assert(black_count == *path_black_count);
182 }
183 return;
184 }
185 verify_property_5_helper(n->left, black_count, path_black_count);
186 verify_property_5_helper(n->right, black_count, path_black_count);
187}
188
189rbtree
190rbtree_create()
191{
192 rbtree t = malloc(sizeof *t);
193 t->root = NULL;
194 verify_properties(t);
195 return t;
196}
197
198node
199new_node(void *key, void *value, color node_color, node left, node right)
200{
201 node result = malloc(sizeof *result);
202 result->key = key;
203 result->value = value;
204 result->color = node_color;
205 result->left = left;
206 result->right = right;
207 if ( left != NULL )
208 left->parent = result;
209 if ( right != NULL )
210 right->parent = result;
211 result->parent = NULL;
212 return result;
213}
214
215node
216lookup_node(rbtree t, void *key, compare_func compare)
217{
218 node n = t->root;
219 while ( n != NULL ) {
220 int comp_result = compare(key, n->key);
221 if ( comp_result == 0 ) {
222 return n;
223 }
224 else if ( comp_result < 0 ) {
225 n = n->left;
226 }
227 else {
228 assert(comp_result > 0);
229 n = n->right;
230 }
231 }
232 return n;
233}
234
235void *
236rbtree_lookup(rbtree t, void *key, compare_func compare)
237{
238 node n = lookup_node(t, key, compare);
239 return n == NULL ? NULL : n->value;
240}
241
242void
243rotate_left(rbtree t, node n)
244{
245 node r = n->right;
246 replace_node(t, n, r);
247 n->right = r->left;
248 if ( r->left != NULL ) {
249 r->left->parent = n;
250 }
251 r->left = n;
252 n->parent = r;
253}
254
255void
256rotate_right(rbtree t, node n)
257{
258 node L = n->left;
259 replace_node(t, n, L);
260 n->left = L->right;
261 if ( L->right != NULL ) {
262 L->right->parent = n;
263 }
264 L->right = n;
265 n->parent = L;
266}
267
268void
269replace_node(rbtree t, node oldn, node newn)
270{
271 if ( oldn->parent == NULL ) {
272 t->root = newn;
273 }
274 else {
275 if ( oldn == oldn->parent->left )
276 oldn->parent->left = newn;
277 else
278 oldn->parent->right = newn;
279 }
280 if ( newn != NULL ) {
281 newn->parent = oldn->parent;
282 }
283}
284
285void
286rbtree_insert(rbtree t, void *key, void *value, compare_func compare)
287{
288 node inserted_node = new_node(key, value, RED, NULL, NULL);
289 if ( t->root == NULL ) {
290 t->root = inserted_node;
291 }
292 else {
293 node n = t->root;
294 while ( 1 ) {
295 int comp_result = compare(key, n->key);
296 if ( comp_result == 0 ) {
297 n->value = value;
298 return;
299 }
300 else if ( comp_result < 0 ) {
301 if ( n->left == NULL ) {
302 n->left = inserted_node;
303 break;
304 }
305 else {
306 n = n->left;
307 }
308 }
309 else {
310 assert(comp_result > 0);
311 if ( n->right == NULL ) {
312 n->right = inserted_node;
313 break;
314 }
315 else {
316 n = n->right;
317 }
318 }
319 }
320 inserted_node->parent = n;
321 }
322 insert_case1(t, inserted_node);
323 verify_properties(t);
324}
325
326void
327insert_case1(rbtree t, node n)
328{
329 if ( n->parent == NULL )
330 n->color = BLACK;
331 else
332 insert_case2(t, n);
333}
334
335void
336insert_case2(rbtree t, node n)
337{
338 if ( node_color(n->parent) == BLACK )
339 return; /* Tree is still valid */
340 else
341 insert_case3(t, n);
342}
343
344void
345insert_case3(rbtree t, node n)
346{
347 if ( node_color(uncle(n)) == RED ) {
348 n->parent->color = BLACK;
349 uncle(n)->color = BLACK;
350 grandparent(n)->color = RED;
351 insert_case1(t, grandparent(n));
352 }
353 else {
354 insert_case4(t, n);
355 }
356}
357
358void
359insert_case4(rbtree t, node n)
360{
361 if ( n == n->parent->right && n->parent == grandparent(n)->left ) {
362 rotate_left(t, n->parent);
363 n = n->left;
364 }
365 else if ( n == n->parent->left && n->parent == grandparent(n)->right ) {
366 rotate_right(t, n->parent);
367 n = n->right;
368 }
369 insert_case5(t, n);
370}
371
372void
373insert_case5(rbtree t, node n)
374{
375 n->parent->color = BLACK;
376 grandparent(n)->color = RED;
377 if ( n == n->parent->left && n->parent == grandparent(n)->left ) {
378 rotate_right(t, grandparent(n));
379 }
380 else {
381 assert(n == n->parent->right && n->parent == grandparent(n)->right);
382 rotate_left(t, grandparent(n));
383 }
384}
385
386void
387rbtree_delete(rbtree t, void *key, compare_func compare)
388{
389 node child;
390 node n = lookup_node(t, key, compare);
391 if ( n == NULL )
392 return; /* Key not found, do nothing */
393 if ( n->left != NULL && n->right != NULL ) {
394 /* Copy key/value from predecessor and then delete it instead */
395 node pred = maximum_node(n->left);
396 n->key = pred->key;
397 n->value = pred->value;
398 n = pred;
399 }
400
401 assert(n->left == NULL || n->right == NULL);
402 child = n->right == NULL ? n->left : n->right;
403 if ( node_color(n) == BLACK ) {
404 n->color = node_color(child);
405 delete_case1(t, n);
406 }
407 replace_node(t, n, child);
408 if ( n->parent == NULL && child != NULL ) // root should be black
409 child->color = BLACK;
410 free(n);
411
412 verify_properties(t);
413}
414
415static node
416maximum_node(node n)
417{
418 assert(n != NULL);
419 while ( n->right != NULL ) {
420 n = n->right;
421 }
422 return n;
423}
424
425void
426delete_case1(rbtree t, node n)
427{
428 if ( n->parent == NULL )
429 return;
430 else
431 delete_case2(t, n);
432}
433
434void
435delete_case2(rbtree t, node n)
436{
437 if ( node_color(sibling(n)) == RED ) {
438 n->parent->color = RED;
439 sibling(n)->color = BLACK;
440 if ( n == n->parent->left )
441 rotate_left(t, n->parent);
442 else
443 rotate_right(t, n->parent);
444 }
445 delete_case3(t, n);
446}
447
448void
449delete_case3(rbtree t, node n)
450{
451 if ( node_color(n->parent) == BLACK &&
452 node_color(sibling(n)) == BLACK &&
453 node_color(sibling(n)->left) == BLACK &&
454 node_color(sibling(n)->right) == BLACK ) {
455 sibling(n)->color = RED;
456 delete_case1(t, n->parent);
457 }
458 else
459 delete_case4(t, n);
460}
461
462void
463delete_case4(rbtree t, node n)
464{
465 if ( node_color(n->parent) == RED &&
466 node_color(sibling(n)) == BLACK &&
467 node_color(sibling(n)->left) == BLACK &&
468 node_color(sibling(n)->right) == BLACK ) {
469 sibling(n)->color = RED;
470 n->parent->color = BLACK;
471 }
472 else
473 delete_case5(t, n);
474}
475
476void
477delete_case5(rbtree t, node n)
478{
479 if ( n == n->parent->left &&
480 node_color(sibling(n)) == BLACK &&
481 node_color(sibling(n)->left) == RED &&
482 node_color(sibling(n)->right) == BLACK ) {
483 sibling(n)->color = RED;
484 sibling(n)->left->color = BLACK;
485 rotate_right(t, sibling(n));
486 }
487 else if ( n == n->parent->right &&
488 node_color(sibling(n)) == BLACK &&
489 node_color(sibling(n)->right) == RED &&
490 node_color(sibling(n)->left) == BLACK ) {
491 sibling(n)->color = RED;
492 sibling(n)->right->color = BLACK;
493 rotate_left(t, sibling(n));
494 }
495 delete_case6(t, n);
496}
497
498void
499delete_case6(rbtree t, node n)
500{
501 sibling(n)->color = node_color(n->parent);
502 n->parent->color = BLACK;
503 if ( n == n->parent->left ) {
504 assert(node_color(sibling(n)->right) == RED);
505 sibling(n)->right->color = BLACK;
506 rotate_left(t, n->parent);
507 }
508 else {
509 assert(node_color(sibling(n)->left) == RED);
510 sibling(n)->left->color = BLACK;
511 rotate_right(t, n->parent);
512 }
513}
514
515/* The authors of this work have released all rights to it and placed it
516in the public domain under the Creative Commons CC0 1.0 waiver
517(http://creativecommons.org/publicdomain/zero/1.0/).
518
519THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
520EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
521MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
522IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
523CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
524TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
525SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
526
527Retrieved from: http://en.literateprograms.org/Red-black_tree_(C)?oldid=19567
528*/
529
530#include <assert.h>
531#include <stdio.h>
532#include <stdlib.h> /* rand() */
533
534static int compare_int(void *left, void *right);
535static void print_tree(rbtree t);
536static void print_tree_helper(rbtree_node n, int indent);
537
538int
539compare_int(void *leftp, void *rightp)
540{
541 int left = (int) leftp;
542 int right = (int) rightp;
543 if ( left < right )
544 return -1;
545 else if ( left > right )
546 return 1;
547 else {
548 assert(left == right);
549 return 0;
550 }
551}
552
553#define INDENT_STEP 4
554
555void print_tree_helper(rbtree_node n, int indent);
556
557void
558print_tree(rbtree t)
559{
560 print_tree_helper(t->root, 0);
561 puts("");
562}
563
564void
565print_tree_helper(rbtree_node n, int indent)
566{
567 int i;
568 if ( n == NULL ) {
569 fputs("<empty tree>", stdout);
570 return;
571 }
572 if ( n->right != NULL ) {
573 print_tree_helper(n->right, indent + INDENT_STEP);
574 }
575 for ( i = 0; i < indent; i++ )
576 fputs(" ", stdout);
577 if ( n->color == BLACK )
578 printf("%d\n", (int) n->key);
579 else
580 printf("<%d>\n", (int) n->key);
581 if ( n->left != NULL ) {
582 print_tree_helper(n->left, indent + INDENT_STEP);
583 }
584}
585
586int
587main()
588{
589 int i;
590 rbtree t = rbtree_create();
591
592 for ( i = 0; i < 50; i++ ) {
593 long x = rand() % 10000;
594 long y = rand() % 10000;
595#ifdef TRACE
596 print_tree(t);
597 printf("Inserting %ld -> %ld\n\n", x, y);
598#endif
599 rbtree_insert(t, (void *) x, (void *) y, compare_int);
600 assert(rbtree_lookup(t, (void *) x, compare_int) == (void *) y);
601 }
602
603 print_tree(t);
604
605 for ( i = 0; i < 60000; i++ ) {
606 long x = rand() % 10000;
607#ifdef TRACE
608 print_tree(t);
609 printf("Deleting key %ld\n\n", x);
610#endif
611 rbtree_delete(t, (void *) x, compare_int);
612 }
613 return 0;
614}