From ff69b8a8f2997c794ed4790dd84d2b3657f2f86e Mon Sep 17 00:00:00 2001 From: scratko Date: Sat, 30 Mar 2024 17:12:57 +0300 Subject: Initial commit --- rb_tree.c | 340 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 340 insertions(+) create mode 100644 rb_tree.c (limited to 'rb_tree.c') diff --git a/rb_tree.c b/rb_tree.c new file mode 100644 index 0000000..2386295 --- /dev/null +++ b/rb_tree.c @@ -0,0 +1,340 @@ +#include "rb_tree.h" +#include +#include + +#define MIN_SIZE_BUF 10 + +enum { start_depth = -1 }; +enum vert_border { empty, line }; +struct scopes { + unsigned int size; + enum vert_border *mas; +}; + +void rb_tree_init(rb_tree *t) { + t->nil = malloc(sizeof(node)); + node *nil = t->nil; + nil->key = 0; + nil->color = black; + nil->p = NULL; + nil->left = NULL; + nil->right = NULL; + t->root = nil; +} + +static void left_rotate(rb_tree *t, node *cur_node) +{ + node *x = cur_node; + node *y = x->right; + x->right = y->left; /* turn y's left subtee into x's right subtree */ + if(y->left != t->nil) + y->left->p = x; + y->p = x->p; /* link x's parent to y */ + if(x->p == t->nil) /* if x was root */ + t->root = y; + else if(x == x->p->left) + x->p->left = y; + else + x->p->right = y; + y->left = x; /* put x on y's left */ + x->p = y; /* y is parent of x */ +} + +static void right_rotate(rb_tree *t, node *cur_node) +{ + node *y = cur_node; + node *x = y->left; + y->left = x->right; + if(x->right != t->nil) + x->right->p = y; + x->p = y->p; + if(y->p == t->nil) + t->root = x; + else if(y == y->p->left) + y->p->left = x; + else + y->p->right = x; + x->right = y; + y->p = x; +} + +static void rb_insert_fixup(rb_tree *t, node *cur_node) +{ + node *z = cur_node; + node *y; + while(z->p->color == red) { + if(z->p == z->p->p->left) {/* parent of z is left child of its parent */ + y = z->p->p->right; /* uncle of z */ + 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 - right chid, y - black */ + z = z->p; + left_rotate(t, z); + } + /* z - left child, y - black */ + z->p->color = black; + z->p->p->color = red; + right_rotate(t, z->p->p); + } + } else { /* parent of z is right child of its parent */ + 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; + right_rotate(t, z); + } + z->p->color = black; + z->p->p->color = red; + left_rotate(t, z->p->p); + } + } + } + t->root->color = black; +} + +/* replacing one subtree with another subtree */ +static void rb_transplant(rb_tree *t, node *source, node *dest) +{ + if(source->p == t->nil) + t->root = dest; + else if(source == source->p->left) + source->p->left = dest; + else + source->p->right = dest; + dest->p = source->p; +} + +static node* tree_minimum(rb_tree *t, node *cur_node) +{ + while(cur_node->left != t->nil) + cur_node = cur_node->left; + return cur_node; +} + +static void rb_delete_fixup(rb_tree *t, node *x) +{ + node *w; + while(x != t->root && x->color == black) { + if(x == x->p->left) { /* x is left child */ + w = x->p->right; + if(w->color == red) { /* case 1 - x's sibling w is red */ + w->color = black; + x->p->color = red; + left_rotate(t, x->p); + w = x->p->right; + } + /* case 2 - x's subling w is black, and both of w's children are black */ + if(w->left->color == black && w->right->color == black) { + w->color = red; + x = x->p; + } else { + /*case 3 - w's black, w's left child's red and w's right child's black*/ + if(w->right->color == black) { + w->left->color = black; + w->color = red; + right_rotate(t, w); + w = x->p->right; /* new w */ + } + /* case 4 - x's sibling w's black, and w's right child's red */ + w->color = x->p->color; + x->p->color = black; + w->right->color = black; + left_rotate(t, x->p); + x = t->root; /* after that the loop's terminated */ + } + } else { /* x's right child */ + w = x->p->left; + if(w->color == red) { + w->color = black; + x->p->color = red; + right_rotate(t, x->p); + w = x->p->left; + } + if(w->right->color == black && w->left->color == black) { + w->color = red; + x = x->p; + } else { + if(w->left->color == black) { + w->right->color = black; + w->color = red; + left_rotate(t, w); + w = x->p->left; + } + w->color = x->p->color; + x->p->color = black; + w->left->color = black; + right_rotate(t, x->p); + x = t->root; + } + } + } + x->color = black; +} + +void rb_tree_delete_node(rb_tree *t, node *cur_node) +{ + node *z = cur_node; + node *y = z; + node *x; + enum color_type y_original_color = y->color; /* y's color might change */ + if(z->left == t->nil) {/* if exists only right child (it's can be nil too)*/ + x = z->right; + rb_transplant(t, z, z->right); + } else if(z->right == t->nil) { /* or exists only left child */ + x = z->left; + rb_transplant(t, z, z->left); + } else { + y = tree_minimum(t, z->right); /* both children exist */ + y_original_color = y->color; + x = y->right; + if(y->p == z) /* node y is right child of z */ + x->p = y; + else { + rb_transplant(t, y, y->right); /* x subtree takes place of y */ + y->right = z->right; /* y takes place of z */ + y->right->p = y; + } + rb_transplant(t, z, y); + y->left = z->left; + y->left->p = y; + y->color = z->color; + } + free(cur_node); + if(y_original_color == black) /*if y with black color was moved or removed*/ + rb_delete_fixup(t, x); +} + +void rb_tree_insert_node(rb_tree *t, node *cur_node) +{ + node *z = cur_node; + node *y = t->nil; + node *x = t->root; + while(x != t->nil) { + y = x; /* save parent of z */ + x = z->key < x->key ? x->left : x->right; + } + z->p = y; + if(y == t->nil) + t->root = z; + else if(z->key < y->key) + y->left = z; + else + y->right = z; + z->left = t->nil; + z->right = t->nil; + z->color = red; + rb_insert_fixup(t, cur_node); +} + +node* rb_tree_search(rb_tree *t, node *root, int num) +{ + if(root == t->nil || root->key == num) + return root; + if(num < root->key) + return rb_tree_search(t, root->left, num); + else + return rb_tree_search(t, root->right, num); +} + +node* rb_tree_create_node(rb_tree *t, int num) +{ + if(rb_tree_search(t, t->root, num) != t->nil) + return NULL; + node *new_node = malloc(sizeof(node)); + new_node->key = num; + new_node->color = red; + new_node->p = t->nil; + new_node->left = t->nil; + new_node->right = t->nil; + return new_node; +} + +void rb_tree_clear(rb_tree *t, node *root) +{ + if(root == t->nil) + return; + rb_tree_clear(t, root->left); + rb_tree_clear(t, root->right); + if(root->p == t->nil) { + free(t->nil); + t->nil = NULL; + } + free(root); +} + +static void buf_copy(enum vert_border *source, enum vert_border *dest, + unsigned buf_size) +{ + int idx; + for(idx = 0; idx < buf_size; ++idx) + dest[idx] = source[idx]; +} + +static void allocate(struct scopes *cur_scopes) +{ + unsigned size = cur_scopes->size; + cur_scopes->size *= 2; + enum vert_border *new_mas = + malloc(cur_scopes->size * sizeof(enum vert_border)); + buf_copy(cur_scopes->mas, new_mas, size); + free(cur_scopes->mas); + cur_scopes->mas = new_mas; +} + +static void print(rb_tree *t, node *root, int depth, struct scopes *cur_scopes) +{ +#if 0 + if(root == t->nil) + return; +#endif + int i; + printf("\t"); +#if 0 + if(depth >= cur_scopes->size) + allocate(cur_scopes); +#endif + for(i = 0; i <= depth;i++) + if(i == depth) + /* left |- or right |_ and --- */ + printf("%s\u2014\u2014\u2014", cur_scopes->mas[depth] ? "\u0371" : + "\u221F"); + else + /* left | or right ' ' */ + printf("%s ", cur_scopes->mas[i]? "\u23B8" : " "); +#if 1 + if(root == t->nil) { + printf("\033[0;34;49m%s\n\033[0m", "nil"); + return; + } +#endif + if(root->color == red) + printf("\033[0;31;49m%d\n\033[0m", root->key); + else + printf("\033[0;34;49m%d\n\033[0m", root->key); + if(depth+1 >= cur_scopes->size) + allocate(cur_scopes); + /* vertical line if left branch */ + cur_scopes->mas[depth+1] = line; + print(t, root->left, depth+1, cur_scopes); + cur_scopes->mas[depth+1] = empty; + print(t, root->right, depth+1, cur_scopes); +} + +void rb_tree_print(rb_tree *t, node *root) +{ + struct scopes cur_scopes; + cur_scopes.mas = malloc(MIN_SIZE_BUF * sizeof(enum vert_border)); + cur_scopes.size = MIN_SIZE_BUF; + /* clearing terminal */ + print(t, root, start_depth, &cur_scopes); + free(cur_scopes.mas); +} -- cgit v1.2.3