What Is a Red-Black Tree?
A red-black tree is a binary search tree in which each node is assigned either a red or black color. Its coloring rules help prevent the tree from becoming excessively unbalanced.
Important Properties
- Every node is either red or black.
- The root of the tree is black.
- A red node cannot have a red child.
- Every path from a node to a null leaf has the same number of black nodes.
- New nodes are normally inserted as red nodes.
Why Are Red-Black Trees Useful?
Efficient Operations
Search, insertion, and removal operations have a worst-case time complexity of O(log n).
Learn more about red-black trees on Wikipedia