**Red Black Trees**

- A red black tree is a binary search tree.
- It is not completely balanced.
- We can balance the maximum; using RB Tree rotations.
- Every Node in Red Black Tree with an extra attribute: the color either Red or Black.

struct RBNode { int data ; enum { red, black} color ; struct RBNode *left, *right ; struct RBNode *parent ; }; |

**We need to follow some of the rules to construct RB tree.**

**Rule-1:**

**It is called BST rule.**- Red Black Tree must be a Binary Search Tree (least value goes left to parent and higher value goes right to parent).

**Rule-2:**

- Also called Rule property.
- The Root Node is always Black

**Rule-3:**

- It is also called Red node property.
- The Children of Red color node must be colored Black (Two consecutive Red color nodes not allowed).

**Rule-4:**

- It is called Depth property.
- In all the paths of the tree, there must be same number of Black nodes.
- Also called black height of the tree

**Rule-6:**

- It is new node property.
- Every new node must insert with RED color.
- We can repaint to black after insertion for balancing.

**Rule-6:**

- It is leaf node property.
- Every leaf node (NULL node) must consider as Black.

**Re-Painting:**

- We must insert a new node with red color.
- Two consecutive red nodes not allowed. Hence balancing is required.
- When uncle(also called neighbor) node is red color, no rotations required.
**Paint Parent and Uncle to Black color.****Paint Grandparent to Red color(make it black if it is root).**

- If the uncle node is colored black. We need to repaint and rotate to balance the tree.
- Rotation are like AVL Tree
- L-L Rotation

- R-R Rotation

- L-R Rotation

- R-L Rotation

- If there is no right child, we consider the NULL child node.
- NULL is always black in Red-Black Tree.
- When Uncle(NULL) is black color, we re-paint and rotate for balancing.

**Double rotation:**

- In the following example, The tree is not balance and the left child is right heavy.
- Hence double rotation with re-painting is required to balance the tree.
- Single left rotation

- After that, paint child to black and grandparent to red.

- Then single right rotation.