Red-Black Tree Insert
A Red-Black tree keeps approximate balance with weaker, cheaper rules than AVL: every new node is red, and a red-red violation is fixed by recolouring (if the uncle is red) or rotating (if the uncle is black) — both O(1) amortised.
- Category
- Trees
- Time complexity
- O(log n)
- Space complexity
- O(1) per fixup
Pseudocode
new node is always red if parent is black: done if uncle is red: recolour parent/uncle/grandparent if uncle is black: rotate + recolour
Reference implementation
# insert red; fix red-red violations:
if uncle.color == RED:
parent.color = uncle.color = BLACK
grandparent.color = RED # recurse up
else:
rotate(grandparent) # + recolor