back to scratko.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorscratko <m@scratko.xyz>2024-03-30 19:26:21 +0300
committerscratko <m@scratko.xyz>2024-03-30 19:26:21 +0300
commit2eebf06ade7a316f057334dd6d76b6af22c8ff01 (patch)
treeae591df0dea6c03c93c0406e5bdcd81ad55b7a5a
parentff69b8a8f2997c794ed4790dd84d2b3657f2f86e (diff)
downloadred-black-tree-2eebf06ade7a316f057334dd6d76b6af22c8ff01.tar.gz
red-black-tree-2eebf06ade7a316f057334dd6d76b6af22c8ff01.tar.bz2
red-black-tree-2eebf06ade7a316f057334dd6d76b6af22c8ff01.zip
Minor changes
Extended desctiption. Cleaning a terminal history before dispaing of the tree is added to the main file. Fixed some function declaration.
-rw-r--r--README.md68
-rw-r--r--rb_tree.c1
-rw-r--r--rb_tree.h4
-rw-r--r--rb_tree_main.c2
4 files changed, 72 insertions, 3 deletions
diff --git a/README.md b/README.md
index 9da3527..8de893d 100644
--- a/README.md
+++ b/README.md
@@ -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.
diff --git a/rb_tree.c b/rb_tree.c
index 2386295..7edc294 100644
--- a/rb_tree.c
+++ b/rb_tree.c
@@ -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);
}
diff --git a/rb_tree.h b/rb_tree.h
index 491e5b8..7e7e4d7 100644
--- a/rb_tree.h
+++ b/rb_tree.h
@@ -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;