Initial commit

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
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