Red-Black Tree

A Self-Balancing Binary Search Tree. Uses Nil Node

Nodes

• Every nodes is either red or black
• Root node is black
• Every Nil Node is black
• If a node is red, then its children are black
• Starting from any node, paths leading down to leaf nodes hold same number of black nodes

Operations

• Red Black Tree Insertion
• Red Black Tree Deletion
• Red Black Tree Rotation
• Red Black Double Rotation