From 154874afda4a8df885e51c01f7681f04fb0b8e61 Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Sat, 9 Apr 2022 09:43:53 +0200 Subject: neue Verzeichnisstruktur --- src/rb.c | 614 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 614 insertions(+) create mode 100644 src/rb.c (limited to 'src/rb.c') diff --git a/src/rb.c b/src/rb.c new file mode 100644 index 0000000..7c2d2c1 --- /dev/null +++ b/src/rb.c @@ -0,0 +1,614 @@ +/* + Implementierung übernommen von: https://web.archive.org/web/20140328232325/http://en.literateprograms.org/Red-black_tree_(C) + */ + +#include +#include +#include + +#include "util.h" + +/* The authors of this work have released all rights to it and placed it +in the public domain under the Creative Commons CC0 1.0 waiver +(http://creativecommons.org/publicdomain/zero/1.0/). + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF +MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. +IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY +CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, +TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE +SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + +Retrieved from: http://en.literateprograms.org/Red-black_tree_(C)?oldid=19567 +*/ + +enum rbtree_node_color { RED, + BLACK }; + +typedef struct rbtree_node_t { + void * key; + void * value; + struct rbtree_node_t * left; + struct rbtree_node_t * right; + struct rbtree_node_t * parent; + enum rbtree_node_color color; +} * rbtree_node; + +typedef struct rbtree_t { + rbtree_node root; +} * rbtree; + +typedef int (*compare_func)(void *left, void *right); + +rbtree rbtree_create(); +void * rbtree_lookup(rbtree t, void *key, compare_func compare); +void rbtree_insert(rbtree t, void *key, void *value, compare_func compare); +void rbtree_delete(rbtree t, void *key, compare_func compare); + +#include +#include + +typedef rbtree_node node; +typedef enum rbtree_node_color color; + +static node grandparent(node n); +static node sibling(node n); +static node uncle(node n); +static void verify_properties(rbtree t); +static void verify_property_1(node root); +static void verify_property_2(node root); +static color node_color(node n); +static void verify_property_4(node root); +static void verify_property_5(node root); +static void verify_property_5_helper(node n, int black_count, int *black_count_path); + +static node new_node(void *key, void *value, color node_color, node left, node right); +static node lookup_node(rbtree t, void *key, compare_func compare); +static void rotate_left(rbtree t, node n); +static void rotate_right(rbtree t, node n); + +static void replace_node(rbtree t, node oldn, node newn); +static void insert_case1(rbtree t, node n); +static void insert_case2(rbtree t, node n); +static void insert_case3(rbtree t, node n); +static void insert_case4(rbtree t, node n); +static void insert_case5(rbtree t, node n); +static node maximum_node(node root); +static void delete_case1(rbtree t, node n); +static void delete_case2(rbtree t, node n); +static void delete_case3(rbtree t, node n); +static void delete_case4(rbtree t, node n); +static void delete_case5(rbtree t, node n); +static void delete_case6(rbtree t, node n); + +node +grandparent(node n) +{ + assert(n != NULL); + assert(n->parent != NULL); /* Not the root node */ + assert(n->parent->parent != NULL); /* Not child of root */ + return n->parent->parent; +} + +node +sibling(node n) +{ + assert(n != NULL); + assert(n->parent != NULL); /* Root node has no sibling */ + if ( n == n->parent->left ) + return n->parent->right; + else + return n->parent->left; +} + +node +uncle(node n) +{ + assert(n != NULL); + assert(n->parent != NULL); /* Root node has no uncle */ + assert(n->parent->parent != NULL); /* Children of root have no uncle */ + return sibling(n->parent); +} + +void +verify_properties(rbtree t) +{ + (void) t; +#ifdef VERIFY_RBTREE + verify_property_1(t->root); + verify_property_2(t->root); + /* Property 3 is implicit */ + verify_property_4(t->root); + verify_property_5(t->root); +#endif +} + +void +verify_property_1(node n) +{ + assert(node_color(n) == RED || node_color(n) == BLACK); + if ( n == NULL ) + return; + verify_property_1(n->left); + verify_property_1(n->right); +} + +void +verify_property_2(node root) +{ + assert(node_color(root) == BLACK); +} + +color +node_color(node n) +{ + return n == NULL ? BLACK : n->color; +} + +void +verify_property_4(node n) +{ + if ( node_color(n) == RED ) { + assert(node_color(n->left) == BLACK); + assert(node_color(n->right) == BLACK); + assert(node_color(n->parent) == BLACK); + } + if ( n == NULL ) + return; + verify_property_4(n->left); + verify_property_4(n->right); +} + +void +verify_property_5(node root) +{ + int black_count_path = -1; + verify_property_5_helper(root, 0, &black_count_path); +} + +void +verify_property_5_helper(node n, int black_count, int *path_black_count) +{ + if ( node_color(n) == BLACK ) { + black_count++; + } + if ( n == NULL ) { + if ( *path_black_count == -1 ) { + *path_black_count = black_count; + } + else { + assert(black_count == *path_black_count); + } + return; + } + verify_property_5_helper(n->left, black_count, path_black_count); + verify_property_5_helper(n->right, black_count, path_black_count); +} + +rbtree +rbtree_create() +{ + rbtree t = malloc(sizeof *t); + t->root = NULL; + verify_properties(t); + return t; +} + +node +new_node(void *key, void *value, color node_color, node left, node right) +{ + node result = malloc(sizeof *result); + result->key = key; + result->value = value; + result->color = node_color; + result->left = left; + result->right = right; + if ( left != NULL ) + left->parent = result; + if ( right != NULL ) + right->parent = result; + result->parent = NULL; + return result; +} + +node +lookup_node(rbtree t, void *key, compare_func compare) +{ + node n = t->root; + while ( n != NULL ) { + int comp_result = compare(key, n->key); + if ( comp_result == 0 ) { + return n; + } + else if ( comp_result < 0 ) { + n = n->left; + } + else { + assert(comp_result > 0); + n = n->right; + } + } + return n; +} + +void * +rbtree_lookup(rbtree t, void *key, compare_func compare) +{ + node n = lookup_node(t, key, compare); + return n == NULL ? NULL : n->value; +} + +void +rotate_left(rbtree t, node n) +{ + node r = n->right; + replace_node(t, n, r); + n->right = r->left; + if ( r->left != NULL ) { + r->left->parent = n; + } + r->left = n; + n->parent = r; +} + +void +rotate_right(rbtree t, node n) +{ + node L = n->left; + replace_node(t, n, L); + n->left = L->right; + if ( L->right != NULL ) { + L->right->parent = n; + } + L->right = n; + n->parent = L; +} + +void +replace_node(rbtree t, node oldn, node newn) +{ + if ( oldn->parent == NULL ) { + t->root = newn; + } + else { + if ( oldn == oldn->parent->left ) + oldn->parent->left = newn; + else + oldn->parent->right = newn; + } + if ( newn != NULL ) { + newn->parent = oldn->parent; + } +} + +void +rbtree_insert(rbtree t, void *key, void *value, compare_func compare) +{ + node inserted_node = new_node(key, value, RED, NULL, NULL); + if ( t->root == NULL ) { + t->root = inserted_node; + } + else { + node n = t->root; + while ( 1 ) { + int comp_result = compare(key, n->key); + if ( comp_result == 0 ) { + n->value = value; + return; + } + else if ( comp_result < 0 ) { + if ( n->left == NULL ) { + n->left = inserted_node; + break; + } + else { + n = n->left; + } + } + else { + assert(comp_result > 0); + if ( n->right == NULL ) { + n->right = inserted_node; + break; + } + else { + n = n->right; + } + } + } + inserted_node->parent = n; + } + insert_case1(t, inserted_node); + verify_properties(t); +} + +void +insert_case1(rbtree t, node n) +{ + if ( n->parent == NULL ) + n->color = BLACK; + else + insert_case2(t, n); +} + +void +insert_case2(rbtree t, node n) +{ + if ( node_color(n->parent) == BLACK ) + return; /* Tree is still valid */ + else + insert_case3(t, n); +} + +void +insert_case3(rbtree t, node n) +{ + if ( node_color(uncle(n)) == RED ) { + n->parent->color = BLACK; + uncle(n)->color = BLACK; + grandparent(n)->color = RED; + insert_case1(t, grandparent(n)); + } + else { + insert_case4(t, n); + } +} + +void +insert_case4(rbtree t, node n) +{ + if ( n == n->parent->right && n->parent == grandparent(n)->left ) { + rotate_left(t, n->parent); + n = n->left; + } + else if ( n == n->parent->left && n->parent == grandparent(n)->right ) { + rotate_right(t, n->parent); + n = n->right; + } + insert_case5(t, n); +} + +void +insert_case5(rbtree t, node n) +{ + n->parent->color = BLACK; + grandparent(n)->color = RED; + if ( n == n->parent->left && n->parent == grandparent(n)->left ) { + rotate_right(t, grandparent(n)); + } + else { + assert(n == n->parent->right && n->parent == grandparent(n)->right); + rotate_left(t, grandparent(n)); + } +} + +void +rbtree_delete(rbtree t, void *key, compare_func compare) +{ + node child; + node n = lookup_node(t, key, compare); + if ( n == NULL ) + return; /* Key not found, do nothing */ + if ( n->left != NULL && n->right != NULL ) { + /* Copy key/value from predecessor and then delete it instead */ + node pred = maximum_node(n->left); + n->key = pred->key; + n->value = pred->value; + n = pred; + } + + assert(n->left == NULL || n->right == NULL); + child = n->right == NULL ? n->left : n->right; + if ( node_color(n) == BLACK ) { + n->color = node_color(child); + delete_case1(t, n); + } + replace_node(t, n, child); + if ( n->parent == NULL && child != NULL ) // root should be black + child->color = BLACK; + free(n); + + verify_properties(t); +} + +static node +maximum_node(node n) +{ + assert(n != NULL); + while ( n->right != NULL ) { + n = n->right; + } + return n; +} + +void +delete_case1(rbtree t, node n) +{ + if ( n->parent == NULL ) + return; + else + delete_case2(t, n); +} + +void +delete_case2(rbtree t, node n) +{ + if ( node_color(sibling(n)) == RED ) { + n->parent->color = RED; + sibling(n)->color = BLACK; + if ( n == n->parent->left ) + rotate_left(t, n->parent); + else + rotate_right(t, n->parent); + } + delete_case3(t, n); +} + +void +delete_case3(rbtree t, node n) +{ + if ( node_color(n->parent) == BLACK && + node_color(sibling(n)) == BLACK && + node_color(sibling(n)->left) == BLACK && + node_color(sibling(n)->right) == BLACK ) { + sibling(n)->color = RED; + delete_case1(t, n->parent); + } + else + delete_case4(t, n); +} + +void +delete_case4(rbtree t, node n) +{ + if ( node_color(n->parent) == RED && + node_color(sibling(n)) == BLACK && + node_color(sibling(n)->left) == BLACK && + node_color(sibling(n)->right) == BLACK ) { + sibling(n)->color = RED; + n->parent->color = BLACK; + } + else + delete_case5(t, n); +} + +void +delete_case5(rbtree t, node n) +{ + if ( n == n->parent->left && + node_color(sibling(n)) == BLACK && + node_color(sibling(n)->left) == RED && + node_color(sibling(n)->right) == BLACK ) { + sibling(n)->color = RED; + sibling(n)->left->color = BLACK; + rotate_right(t, sibling(n)); + } + else if ( n == n->parent->right && + node_color(sibling(n)) == BLACK && + node_color(sibling(n)->right) == RED && + node_color(sibling(n)->left) == BLACK ) { + sibling(n)->color = RED; + sibling(n)->right->color = BLACK; + rotate_left(t, sibling(n)); + } + delete_case6(t, n); +} + +void +delete_case6(rbtree t, node n) +{ + sibling(n)->color = node_color(n->parent); + n->parent->color = BLACK; + if ( n == n->parent->left ) { + assert(node_color(sibling(n)->right) == RED); + sibling(n)->right->color = BLACK; + rotate_left(t, n->parent); + } + else { + assert(node_color(sibling(n)->left) == RED); + sibling(n)->left->color = BLACK; + rotate_right(t, n->parent); + } +} + +/* The authors of this work have released all rights to it and placed it +in the public domain under the Creative Commons CC0 1.0 waiver +(http://creativecommons.org/publicdomain/zero/1.0/). + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF +MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. +IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY +CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, +TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE +SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + +Retrieved from: http://en.literateprograms.org/Red-black_tree_(C)?oldid=19567 +*/ + +#include +#include +#include /* rand() */ + +static int compare_int(void *left, void *right); +static void print_tree(rbtree t); +static void print_tree_helper(rbtree_node n, int indent); + +int +compare_int(void *leftp, void *rightp) +{ + int left = (int) leftp; + int right = (int) rightp; + if ( left < right ) + return -1; + else if ( left > right ) + return 1; + else { + assert(left == right); + return 0; + } +} + +#define INDENT_STEP 4 + +void print_tree_helper(rbtree_node n, int indent); + +void +print_tree(rbtree t) +{ + print_tree_helper(t->root, 0); + puts(""); +} + +void +print_tree_helper(rbtree_node n, int indent) +{ + int i; + if ( n == NULL ) { + fputs("", stdout); + return; + } + if ( n->right != NULL ) { + print_tree_helper(n->right, indent + INDENT_STEP); + } + for ( i = 0; i < indent; i++ ) + fputs(" ", stdout); + if ( n->color == BLACK ) + printf("%d\n", (int) n->key); + else + printf("<%d>\n", (int) n->key); + if ( n->left != NULL ) { + print_tree_helper(n->left, indent + INDENT_STEP); + } +} + +int +main() +{ + int i; + rbtree t = rbtree_create(); + + for ( i = 0; i < 50; i++ ) { + long x = rand() % 10000; + long y = rand() % 10000; +#ifdef TRACE + print_tree(t); + printf("Inserting %ld -> %ld\n\n", x, y); +#endif + rbtree_insert(t, (void *) x, (void *) y, compare_int); + assert(rbtree_lookup(t, (void *) x, compare_int) == (void *) y); + } + + print_tree(t); + + for ( i = 0; i < 60000; i++ ) { + long x = rand() % 10000; +#ifdef TRACE + print_tree(t); + printf("Deleting key %ld\n\n", x); +#endif + rbtree_delete(t, (void *) x, compare_int); + } + return 0; +} -- cgit v1.3