Heap learning: Red-black tree | wiki article | 10 minutes reading

 

Red–black tree

From Wikipedia, the free encyclopedia

Jump to navigationJump to search

Red–black tree
Type	tree
Invented	1972
Invented by	Rudolf Bayer
Time complexity in big O notation
Algorithm Average Worst case Space ${\displaystyle {\mathcal {O}}(n)}$ ${\displaystyle {\mathcal {O}}(n)}$ Search ${\displaystyle {\mathcal {O}}(\log n)}$[1] ${\displaystyle {\mathcal {O}}(\log n)}$[1] Insert ${\displaystyle {\mathcal {O}}(\log n)}$[1] ${\displaystyle {\mathcal {O}}(\log n)}$[1] Delete ${\displaystyle {\mathcal {O}}(\log n)}$[1] ${\displaystyle {\mathcal {O}}(\log n)}$[1]

In computer science, a red–black tree is a kind of self-balancing binary search tree. Each node stores an extra bit representing "color" ("red" or "black"), used to ensure that the tree remains balanced during insertions and deletions.^[2]

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. The properties are designed such that this rearranging and recoloring can be performed efficiently.

The re-balancing is not perfect, but guarantees searching in ${\displaystyle {\mathcal {O}}(\log n)}$ time, where ${\displaystyle n}$ is the number of nodes of the tree. The insertion and deletion operations, along with the tree rearrangement and recoloring, are also performed in ${\displaystyle {\mathcal {O}}(\log n)}$ time.^[3]

Tracking the color of each node requires only 1 bit of information per node because there are only two colors. The tree does not contain any other data specific to its being a red–black tree so its memory footprint is almost identical to a classic (uncolored) binary search tree. In many cases, the additional bit of information can be stored at no additional memory cost.