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.
Tag: Red-Black Tree
Notes of Introduction to Algorithm(Red-Black Tree)
Posted by –
March 7, 2006