From ac55496d881e0a17b3eff85f1faae5aafbc53b50 Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Wed, 22 Jul 2020 17:30:45 +0200 Subject: erster Commit --- rb.c | 661 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 661 insertions(+) create mode 100644 rb.c (limited to 'rb.c') diff --git a/rb.c b/rb.c new file mode 100644 index 0000000..c95ab83 --- /dev/null +++ b/rb.c @@ -0,0 +1,661 @@ +#include +#include +#include +#include "util.h" + +typedef int T; + +#if 0 +struct rbtree { + T data; + enum { RED, BLACK } color; + struct rbtree *left, *right, *p; +}; + +struct rbtree * +rb_alloc(T data) +{ + struct rbtree *node = malloc(sizeof *node); + if ( node ) + { + node->data = data; + node->left = NULL; + node->right = NULL; + node->p = NULL; + } + return node; +} + +void +rb_left_rotate(struct rbtree **root, struct rbtree *x) +{ + struct rbtree *y = x->right; + x->right = y->left; + if ( y->left ) + y->left->p = x; + + y->p = x->p; + if ( x->p == NULL ) + *root = y; + else if ( x == x->p->left ) + x->p->left = y; + else + x->p->right = y; + + y->left = x; + x->p = y; +} + +void +rb_right_rotate(struct rbtree **root, struct rbtree *y) +{ + struct rbtree *x = y->left; + y->left = x->right; + if ( x->right ) + x->right->p = y; + + x->p = y->p; + if ( y->p == NULL ) + *root = x; + else if ( y == y->p->left ) + y->p->left = x; + else + y->p->right = x; + + x->right = y; + y->p = x; +} + +void +rb_insert_fixup(struct rbtree **root, struct rbtree **z) +{ + struct rbtree *y; + + while ( z->p->color == RED ) { + if ( z->p == z->p->p->left ) { + y = z->p->p->right; + if ( y->color == RED ) { + z->p->color = BLACK; + y->color = BLACK; + z->p->p->color = RED; + z = z->p->p; + } + else { + if ( z == z->p->right ) { + z = z->p; + rb_left_rotate(root, z); + } + z->p->color = BLACK; + z->p->p->color = RED; + rb_right_rotate(root, z->p->p); + } + } + else { + y = z->p->p->left; + if ( y->color == RED ) { + z->p->color = BLACK; + y->color = BLACK; + z->p->p->color = RED; + z = z->p->p; + } + else { + if ( z == z->p->left ) { + z = z->p; + rb_right_rotate(root, z); + } + z->p->color = BLACK; + z->p->p->color = RED; + rb_left_rotate(root, z->p->p); + } + } + } + + (*root)->color = BLACK; +} + +void +rb_insert_node(struct rbtree **root, T data) +{ + struct rbtree *z = rb_alloc(data); + + if ( *root == NULL ) { + z->color = BLACK; + *root = z; + } + else { + struct rbtree *y = NULL; + struct rbtree *x = *root; + + while ( x ) { + y = x; + if ( z->data < x->data ) + x = x->left; + else + x = x->right; + } + z->p = y; + + if ( y == NULL ) // kann entfallen! + *root = z; + else if ( z->data < y->data ) + y->left = z; + else + y->right = z; + + z->left = NULL; // kann entfallen! + z->right = NULL; // kann entfallen! + z->color = RED; + + rb_insert_fixup(root, &z); + } +} + +#endif + + + +/* 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) { +#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(struct rbtree_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(struct rbtree_node_t)); + 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; icolor == 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(); + print_tree(t); + + for(i=0; i<5000; i++) { + long x = rand() % 10000; + long y = rand() % 10000; +#ifdef TRACE + print_tree(t); + printf("Inserting %d -> %d\n\n", x, y); +#endif + rbtree_insert(t, (void*)x, (void*)y, compare_int); + assert(rbtree_lookup(t, (void*)x, compare_int) == (void*)y); + } + for(i=0; i<60000; i++) { + long x = rand() % 10000; +#ifdef TRACE + print_tree(t); + printf("Deleting key %d\n\n", x); +#endif + rbtree_delete(t, (void*)x, compare_int); + } + return 0; +} + +#if 0 +int main__(void) +{ + struct rbtree *tree = NULL; + + srand(time(NULL)); + for ( int i = 0; i != 10; ++i ) + rb_insert_node(&tree, rand()); + +} +#endif -- cgit v1.3