Exercise 13.3.2

Show the red-black trees that result after successfully inserting the keys $41, 38, 31, 12, 19, 8$ into an initially empty red-black tree.

This was a curious exercise. It was worth doing this on a piece of paper and then writing the code to verify that it works.

After inserting 41

After inserting 38

After inserting 31

After inserting 12

After inserting 19

After inserting 8

Python code

from enum import Enum


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


class Node:
    def __init__(self, color, key, parent, left, right):
        self.color = color
        self.key = key
        self.parent = parent
        self.left = left
        self.right = right


class Tree:
    def __init__(self):
        self.nil = Node(Color.BLACK, None, None, None, None)
        self.nil.parent = self.nil
        self.nil.left = self.nil
        self.nil.right = self.nil

        self.root = self.nil

    def insert(self, key):
        z = Node(Color.RED, key, None, None, None)
        y = self.nil
        x = self.root
        while x is not self.nil:
            y = x
            if z.key < x.key:
                x = x.left
            else:
                x = x.right

        z.parent = y

        if y is self.nil:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z

        z.left = self.nil
        z.right = self.nil
        z.color = Color.RED

        self.fixup(z)

    def fixup(self, z):
        while z.parent.color == Color.RED:
            if z.parent is z.parent.parent.left:
                y = z.parent.parent.right
                if y.color == Color.RED:
                    z.parent.color = Color.BLACK
                    y.color = Color.BLACK
                    z.parent.parent.color = Color.RED
                    z = z.parent.parent
                else:
                    if z is z.parent.right:
                        z = z.parent
                        self.left_rotate(z)
                    z.parent.color = Color.BLACK
                    z.parent.parent.color = Color.RED
                    self.right_rotate(z.parent.parent)
            else:
                y = z.parent.parent.left
                if y.color == Color.RED:
                    z.parent.color = Color.BLACK
                    y.color = Color.BLACK
                    z.parent.parent.color = Color.RED
                    z = z.parent.parent
                else:
                    if z is z.parent.left:
                        z = z.parent
                        self.right_rotate(z)
                    z.parent.color = Color.BLACK
                    z.parent.parent.color = Color.RED
                    self.left_rotate(z.parent.parent)
        self.root.color = Color.BLACK

    def left_rotate(self, x):
        y = x.right
        x.right = y.left

        if y.left is not self.nil:
            y.left.parent = x

        y.parent = x.parent

        if x.parent is self.nil:
            self.root = y
        elif x is x.parent.left:
            x.parent.left = y
        else:
            x.parent.right = y

        y.left = x
        x.parent = y

    def right_rotate(self, y):
        x = y.left
        y.left = x.right

        if x.right is not self.nil:
            x.right.parent = y

        x.parent = y.parent

        if y.parent is self.nil:
            self.root = x
        elif y is y.parent.left:
            y.parent.left = x
        else:
            y.parent.right = x

        x.right = y
        y.parent = x