Red–Black Tree Balancing — Invariants in Words

Red–black trees keep black height uniform along paths and limit consecutive reds; fixes use rotations plus recoloring.

Try this in Python

from __future__ import annotations
from dataclasses import dataclass


@dataclass
class TreeNode:
    val: int
    left: TreeNode | None = None
    right: TreeNode | None = None

from enum import Enum
from dataclasses import dataclass


class Color(Enum):
    RED = 1
    BLACK = 2


@dataclass
class RBNode:
    val: int
    color: Color = Color.RED
    left: RBNode | None = None
    right: RBNode | None = None


x = RBNode(10, Color.BLACK)
print(x.color)

Key takeaways

• Memorize the five invariants at a high level; implement only if the course requires—many interviews stop at comparing AVL vs RB tradeoffs.
• Recoloring can propagate to the root—watch parent and uncle cases.
• Standard libraries (e.g. sortedcontainers) hide this complexity.