From ff69b8a8f2997c794ed4790dd84d2b3657f2f86e Mon Sep 17 00:00:00 2001 From: scratko Date: Sat, 30 Mar 2024 17:12:57 +0300 Subject: Initial commit --- Makefile | 9 ++ README.md | 13 ++ rb_tree.c | 340 +++++++++++++++++++++++++++++++++++++++++++++++++++ rb_tree.h | 29 +++++ rb_tree_main.c | 94 ++++++++++++++ red-black-tree-1.png | Bin 0 -> 19476 bytes red-black-tree-2.png | Bin 0 -> 15621 bytes 7 files changed, 485 insertions(+) create mode 100644 Makefile create mode 100644 README.md create mode 100644 rb_tree.c create mode 100644 rb_tree.h create mode 100644 rb_tree_main.c create mode 100644 red-black-tree-1.png create mode 100644 red-black-tree-2.png diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..e18ea6e --- /dev/null +++ b/Makefile @@ -0,0 +1,9 @@ +OBJMODULES = rb_tree.o +CC = gcc +CFLAGS = -g -Wall + +%.o: %.c %.h + $(CC) $(CFLAGS) -c $< -o $@ + +rb_tree: rb_tree_main.c $(OBJMODULES) + $(CC) $(CFLAGS) $^ -o $@ diff --git a/README.md b/README.md new file mode 100644 index 0000000..9da3527 --- /dev/null +++ b/README.md @@ -0,0 +1,13 @@ +# Red-black tree algorithm + + + + + +Red-black tree is an algorithm for balancing a binary search tree. It uses an +additional attribute of a tree node -- color (i.e. each node must be either red +or black). The binary search tree is not a bad algorithm, but if we get a lined +up chain of nodes, we get a similarity to a linked list (O(n), n is the number +of nodes). Thus, the advantage of binary tree is lost. To correct this +situation, tree balancing was created. Advantages over a regular binary tree: +insertion, deletion and search procedure for O(log n) even in the worst case. 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); +} diff --git a/rb_tree.h b/rb_tree.h new file mode 100644 index 0000000..491e5b8 --- /dev/null +++ b/rb_tree.h @@ -0,0 +1,29 @@ +#ifndef RB_TREE_H_SENTRY +#define RB_TREE_H_SENTRY + +enum color_type { red, black }; + +struct node_type { + int key; + enum color_type color; + struct node_type *p; + struct node_type *left; + struct node_type *right; +}; +typedef struct node_type node; + +struct rb_tree_type { + node *root; + node *nil; +}; +typedef struct rb_tree_type rb_tree; + +void rb_tree_init(rb_tree *t); +void rb_tree_insert_node(rb_tree *t, node *cur_node); +void rb_tree_delete_node(rb_tree *t, node *cur_node); +void rb_tree_clear(rb_tree *t, node *root); +node* rb_tree_create_node(rb_tree *t, int num); +node* rb_tree_search(rb_tree *t, node *root, int num); +void rb_tree_print(rb_tree *t, node *root); + +#endif diff --git a/rb_tree_main.c b/rb_tree_main.c new file mode 100644 index 0000000..e90910d --- /dev/null +++ b/rb_tree_main.c @@ -0,0 +1,94 @@ +#include "rb_tree.h" +#include +#include + +#define PRINT_MENU \ + printf("\n1 - add numbers to tree\n"); \ + printf("2 - remove node if it exists\n"); \ + printf("3 - print tree\n"); \ + printf("4 - clear tree\n"); \ + printf("5 - quit\n"); + +#define CLEAR_BUFFER \ + while ( (res = getchar()) != '\n' && res != EOF ) { } + +int main() +{ + enum { true = 1 }; + enum state { add = 1, remove, print, clear, quit }; + enum state answer; + rb_tree *new_tree = NULL; + int res, num; + char ch; + while(true) { + PRINT_MENU + if((res = getchar())== EOF) + break; + ch = (char)res; + res = strtol(&ch, NULL, 10); + if(!res) { + CLEAR_BUFFER + printf("\e[1;1H\e[2J"); /* clear screen */ + continue; + } + answer = (enum state) res; + CLEAR_BUFFER + printf("\e[1;1H\e[2J"); + switch(answer) { + case add: + if(!new_tree) { + new_tree = malloc(sizeof(rb_tree)); + rb_tree_init(new_tree); + } + printf("enter some numbers (ctrl-d - quit)\n"); + while((res = scanf("%d", &num)) != EOF) { + if(!res) { + fprintf(stderr, "invalid input\n"); + return 1; + } + node *new_node = rb_tree_create_node(new_tree, num); + if (new_node) + rb_tree_insert_node(new_tree, new_node); + } + clearerr(stdin); + break; + case remove: + if(!new_tree) { + printf("tree wasn't created\n"); + break; + } + printf("enter a number to delete\n"); + res = scanf("%d", &num); + if(!res) { + fprintf(stderr, "invalid input\n"); + return 1; + } + node *del_node = rb_tree_search(new_tree, new_tree->root, num); + if(del_node != new_tree->nil) { + rb_tree_delete_node(new_tree, del_node); + printf("node with this number has been removed!\n"); + } + else + printf("the number wasn't finded\n"); + CLEAR_BUFFER + break; + case print: + if(new_tree) + rb_tree_print(new_tree, new_tree->root); + break; + case clear: + if(new_tree) { + rb_tree_clear(new_tree, new_tree->root); + free(new_tree); + new_tree = NULL; + printf("tree has been cleared\n"); + } + break; + case quit: + if(new_tree) + free(new_tree); + return 0; + } + } + return 0; +} diff --git a/red-black-tree-1.png b/red-black-tree-1.png new file mode 100644 index 0000000..9dfae10 Binary files /dev/null and b/red-black-tree-1.png differ diff --git a/red-black-tree-2.png b/red-black-tree-2.png new file mode 100644 index 0000000..64921a7 Binary files /dev/null and b/red-black-tree-2.png differ -- cgit v1.2.3