RED BLACK TREE

A red–black tree is a binary search tree where each node has a color attribute, the value of which is either red or black. In addition to the ordinary requirements imposed on binary search trees, the following requirements apply to red–black trees:

1. A node is either red or black.
2. The root is black. All leaves are the same color as the root.
3. Both children of every red node are black.
4. Every simple path from a given node to any of its descendant leaves contains the same number of black nodes.

• Red-black trees are binary search trees with each node colored red or black and satisfying the following properties:
• Root property: The root is black.
• External property: All external nodes are black.
• Internal property: The children of red nodes are black.
• Depth property: All external nodes have the same black depth. The black depth is the number of black ancestors minus one, or the number of black links from the root to the node.
• From a combinatorial point of view, a red-black tree is an extended binary tree (every node has two children or is a leaf) which satisfies the following properties.
• Every node is colored either red or black.
• Every leaf node is colored black.
• If a node is red, then both of its children are black.
• Every path from the root to a leaf contains the same number of black nodes. This number is called the black-height of the tree.

---------------------------------------------------------------------------------------