From ff69b8a8f2997c794ed4790dd84d2b3657f2f86e Mon Sep 17 00:00:00 2001 From: scratko Date: Sat, 30 Mar 2024 17:12:57 +0300 Subject: Initial commit --- README.md | 13 +++++++++++++ 1 file changed, 13 insertions(+) create mode 100644 README.md (limited to 'README.md') 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 + + + + + +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. -- cgit v1.2.3