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

The algorithm is written in C based on some pseudocode fragments from the book
"Introduction to algorithms" by Thomas H. Cormen.

## Description

This program performs demonstrates the capabilities of the rb algorithm.
To do this, type in the command line of the terminal:

```
git clone https://git.scratko.xyz/red-black-tree
cd red-black-tree
make
./red-black-tree
```
As seen in the second screenshot, the program displays an interactive menu.

However, the algorithm can be used in other projects too. The `rb_tree.h` file
provides a so-called API interface.  To take advantage of this, do the
following: compile `rb_tree.c`

```
gcc -Wall -c rb_tree.c
```

You will receive `rb_tree.o` (object module).

Thus, `rb_tree.h` is header file provides function declarations, and `rb_tree.o`
is required for the final build of the executable file.

Before using the functions, allocate dynamic memory in your program.

```
rb_tree \*new_tree = malloc(sizeof(rb_tree));
```
Do not forget to free the allocated memory at the end using:

```
free(new_tree);
```


## Interface for managing rb-tree

1. *`void rb_tree_init(rb_tree \*t);`*

To fill `new_tree` with initial values.

2. *`node \*rb_tree_create_node(rb_tree \*t, int num);`*

Returns a pointer of type `node\*` to the created node (note that the node has
not yet been inserted into the tree). Or NULL if the num value has already been
inserted into the tree.

3. *`void rb_tree_insert_node(rb_tree \*t, node \*cur_node);`*

4. *`void rb_tree_delete_node(rb_tree \*t, node \*cur_node);`*

5. *`void rb_tree_clear(rb_tree \*t, node \*root);`*

6. *`node\* rb_tree_search(rb_tree \*t, node \*root, int num);`*

Returns a node of type `node\*`. If the value was not found into the tree, then the
node will be equal to `t->nil`, otherwise it returns the node with the required value.

7. `void rb_tree_print(rb_tree \*t, node \*root);`

Displaying a binary tree in stdout.