back to scratko.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--Makefile9
-rw-r--r--README.md13
-rw-r--r--rb_tree.c340
-rw-r--r--rb_tree.h29
-rw-r--r--rb_tree_main.c94
-rw-r--r--red-black-tree-1.pngbin0 -> 19476 bytes
-rw-r--r--red-black-tree-2.pngbin0 -> 15621 bytes
7 files changed, 485 insertions, 0 deletions
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
+
+<img src="red-black-tree-1.png" />
+
+<img src="red-black-tree-2.png" />
+
+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 <stdio.h>
+#include <stdlib.h>
+
+#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 <stdio.h>
+#include <stdlib.h>
+
+#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
--- /dev/null
+++ b/red-black-tree-1.png
Binary files differ
diff --git a/red-black-tree-2.png b/red-black-tree-2.png
new file mode 100644
index 0000000..64921a7
--- /dev/null
+++ b/red-black-tree-2.png
Binary files differ
generated by cgit v1.2.3 (git 2.25.1) at 2024-12-03 20:24:31 +0300