Red Black Tree

What is a Red Black Tree?

A Red Black Tree is a self-balancing binary search tree where each node has an extra bit for storing the color of the node, which can be either red or black.

Properties of Red Black Tree

• Each node is either red or black.
• The root is always black.
• No red can have red children.

More information here: Red Black Tree - Wikipedia