A red black tree is a binary tree where

1. every node has color.

2. root node is always black

3. the child of a black node is either black or red

4. both the child nodes of every red node must be black

5. all the leaves must be black