Red-Black Tree

Introduction

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.

Key Properties:

1. Each node is either red or black
2. The root is black.
3. No red nodes can have red children
4. Every path from root to a null child has the same number of black nodes(black height of the tree)
5. Null children are black

An example of valid Red-Black tree:

There is one link to more information about Red-Black tree: