Red-Black Trees

Functionality

A red-black tree is used to ensure that a binary search tree remains balanced when adding elements.

Rules

• Every node is either a red node or a black node.
• The root node must be a black node.
• A red node cannot be the child of a red node.
• There must be the same number of black nodes in every path to a null node.