1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
|
# 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.
|
