# 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.