A red-black tree is a binary search tree with one extra bit of storage per node: its color, which can be either RED or BLACK.
A binary search tree is a red-black tree if it satisfies the following red-black properties:
1. Every node is either red or black.
2. The root is black.
3. Every leaf (NIL) is black.
4. If a node is red, then both its children are black.
5. For each node, all paths from the node to descendant leaves contain the same number of black nodes.
Continue reading “Notes of Introduction to Algorithm(Red-Black Tree)”