Extra colour for each node
Properties:
- Every node is either red or black.
- The root and leaves (nil) are black.
- Every red node has a black parent.
- All simple paths from a node x to a leaf descendant of x have the same number of black nodes.
height ≤ 2log(n+1)
leaves = n+1
Merge red nodes into black parent to balance the tree.
To merge red nodes into their black parent and balance the tree, a process called "color flipping" is used. This involves changing the colors of certain nodes in the tree to maintain the four properties listed above. By doing this, the tree remains balanced and efficient, even as new nodes are added or removed.
- Every internal node has 2-4 children.
- Every leaf has same depth, namely black-height (root)
Time complexity of the operations O(log(n))
Operation
Recoloring
Recolor whenever the sibling of a red node's red parent is red:
Restructuring
Restructure whenever the red child's red parent's sibling is black or null. There are four cases:
- Right
- Left
- Right-Left
- Left-Right
When you restructure, the root of the restructured subtree is colored black and its children are colored red.
