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

In red-black trees, the leaf nodes are not relevant and do not contain data.

Red-black trees, like all binary search trees, allow efficient in-order traversal of elements.

Each node has a color attribute, the value of which is either red or black.

Characteristics:

The root and leaves are black

Both children of every red node are black.

Every simple path from a node to a descendant leaf contains the same number of black nodes, either counting or not counting the null black nodes