What is a Red-Black Tree?
A Red-Black tree is a self-balancing binary search tree data structure. When the tree is modified, the new tree is rearranged and “repainted” to restore the coloring properties that constrain how unbalanced the tree can become in the worst case.
source
Properties
A Red-Black tree has all binary search tree properties, with some additional properties:
- Every node is either
red
orblack
. - All
nil
nodes are consideredblack
. - A
red
node does not have ared
child. - If a node is
red
, then both its children areblack
. - Every path from a given node to any of its descendant
nil
nodes goes through the same number ofblack
nodes.
Time Complexity
The (re-)balancing is not perfect, but guarantees searching in O(log n) time, where n is the number of entries in the tree. The insert and delete operations, along with tree rearrangement and recoloring, also execute in O(log n) time.