diff options
Diffstat (limited to 'README.md')
| -rw-r--r-- | README.md | 13 |
1 files changed, 13 insertions, 0 deletions
diff --git a/README.md b/README.md new file mode 100644 index 0000000..9da3527 --- /dev/null +++ b/README.md @@ -0,0 +1,13 @@ +# 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. |