Red-Black Tree

Properties

• Each node is red or black
• Root is black
• No two red nodes are adjacent

A red-black tree is a self-balancing binary search tree.