diff options
| -rw-r--r-- | README.md | 68 | ||||
| -rw-r--r-- | rb_tree.c | 1 | ||||
| -rw-r--r-- | rb_tree.h | 4 | ||||
| -rw-r--r-- | rb_tree_main.c | 2 |
4 files changed, 72 insertions, 3 deletions
@@ -11,3 +11,71 @@ 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. @@ -334,7 +334,6 @@ 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); } @@ -22,8 +22,8 @@ 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); +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 index e90910d..66ba68d 100644 --- a/rb_tree_main.c +++ b/rb_tree_main.c @@ -73,6 +73,8 @@ int main() CLEAR_BUFFER break; case print: + /* clearing terminal history */ + printf("\033c"); if(new_tree) rb_tree_print(new_tree, new_tree->root); break; |