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.

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

• void rb_tree_init(rb_tree *t);

  To fill new_tree with initial values.

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

• 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_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.

• void rb_tree_print(rb_tree *t, node *root);

  Displaying a binary tree in stdout.