Red-Black Tree

Red-Black Tree

Red-Black tree is a self-balancing binary search tree in which each node contains an extra bit for denoting the color of the node, either red or black. It was created in 1972 by Rudolf Bayer who termed them "symmetric binary B-trees."

Properties of Red-Black Tree:

• Root element of Red-Black Tree is always black.
• Every NULL node or Leaf Nodes is black.
• If a red node has children then, the children or its parent are always black.
• Number of black Node on Any path from root to leaf is always same.
• Two consecutive red node should not be in Red-Black Tree.
• If you are inserting a new node is always a red node.

Maximum height of Red-Black Tree :

log n <= h <= 2log n

Examples of Red-Black Tree:-