blob: 9da3527859af35b2015018f23424e3a1ffa193e9 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
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.
|
