Red-Black Tree

A Red-Black Tree is a self-balancing BST that uses node coloring (red/black) to maintain balance. It is more flexible than an AVL Tree, so it is faster for insert and delete operations.

Red-Black Tree Properties

1. Every node is either red or black.
2. The root is always black.
3. All leaves (None) are considered black.
4. If a node is red, its children must be black (no two reds in a row).
5. Every path from the root to a leaf contains the same number of black nodes.

Rotations and Recoloring

Red-Black Trees use:
- Recoloring: Changing a node's color.
- Rotation: Left/right rotations, just like in AVL Trees.

RED = True
BLACK = False

class RBNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None
        self.color = RED

Insert

When inserting a new node (always red), there are several cases:

Case 1: Uncle is red

Recolor the parent, uncle, and grandparent.

Case 2: Uncle is black, zig-zag

Rotate to turn it into case 3.

Case 3: Uncle is black, zig-zig

Rotate the grandparent, then recolor.

class RedBlackTree:
    def __init__(self):
        self.NIL = RBNode(None)
        self.NIL.color = BLACK
        self.root = self.NIL

    def insert(self, val):
        node = RBNode(val)
        node.left = self.NIL
        node.right = self.NIL

        y = None
        x = self.root

        while x != self.NIL:
            y = x
            if node.val < x.val:
                x = x.left
            else:
                x = x.right

        node.parent = y
        if not y:
            self.root = node
        elif node.val < y.val:
            y.left = node
        else:
            y.right = node

        if not node.parent:
            self.root = node
            node.color = BLACK
            return

        if not node.parent.parent:
            return

        self._fix_insert(node)

    def _fix_insert(self, k):
        while k.parent and k.parent.color == RED:
            if k.parent == k.parent.parent.right:
                u = k.parent.parent.left
                if u.color == RED:
                    u.color = BLACK
                    k.parent.color = BLACK
                    k.parent.parent.color = RED
                    k = k.parent.parent
                else:
                    if k == k.parent.left:
                        k = k.parent
                        self._right_rotate(k)
                    k.parent.color = BLACK
                    k.parent.parent.color = RED
                    self._left_rotate(k.parent.parent)
            else:
                u = k.parent.parent.right
                if u.color == RED:
                    u.color = BLACK
                    k.parent.color = BLACK
                    k.parent.parent.color = RED
                    k = k.parent.parent
                else:
                    if k == k.parent.right:
                        k = k.parent
                        self._left_rotate(k)
                    k.parent.color = BLACK
                    k.parent.parent.color = RED
                    self._right_rotate(k.parent.parent)
            if k == self.root:
                break
        self.root.color = BLACK

AVL vs Red-Black Tree

Time Complexity

Red-Black Trees are used in many standard libraries. Now let's study Heaps for prioritized data.