Exercise 13.4.3
In Exercise 13.3-2, you found the red-black tree that results from successively inserting the keys $41, 38, 31, 12, 19, 8$ into an initially empty tree. Now show the red-black trees that result from the successive deletion of the keys in the order $8, 12, 19, 31, 38, 41$.
I did this on paper, but in order to be certain of the results, it's worth implementing deletion and seeing whether they match when I came up with. Let's see.
After deleting 8
After deleting 12
After deleting 19
After deleting 31
After deleting 38
Python code
from enum import Enum from collections import deque 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 def sexp(self, nil): if self is nil: return 'NIL' color = 'R' if self.color == Color.RED else 'B' return f"{color}({self.key}, {self.left.sexp(nil)}, {self.right.sexp(nil)})" def black_height(self, nil): node = self height = 0 while node is not nil: if node.color == Color.BLACK: height += 1 node = node.parent return height 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 __str__(self): return self.root.sexp(self.nil) def search(self, key): node = self.root while node is not self.nil: if node.key == key: return node elif key < node.key: node = node.left else: node = node.right return None def nodes(self): items = deque() if self.root is not self.nil: items.append(self.root) while items: node = items.popleft() yield node if node.left is not self.nil: items.append(node.left) if node.right is not self.nil: items.append(node.right) 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.insert_fixup(z) def insert_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 delete(self, z): z = self.search(z) y = z y_original_color = y.color if z.left is self.nil: x = z.right self.transplant(z, z.right) elif z.right is self.nil: x = z.left self.transplant(z, z.left) else: y = self.minimum(z.right) y_original_color = y.color x = y.right if y.parent is z: x.parent = y else: self.transplant(y, y.right) y.right = z.right y.right.parent = y self.transplant(z, y) y.left = z.left y.left.parent = y y.color = z.color if y_original_color == Color.BLACK: self.delete_fixup(x) def delete_fixup(self, x): while x is not self.root and x.color == Color.BLACK: if x is x.parent.left: w = x.parent.right if w.color == Color.RED: w.color = Color.BLACK x.parent.color = Color.RED self.left_rotate(x.parent) w = x.parent.right if w.left.color == Color.BLACK and w.right.color == Color.BLACK: w.color = Color.RED x = x.parent else: if w.right.color == Color.BLACK: w.left.color = Color.BLACK w.color = Color.RED self.right_rotate(w) w = x.parent.right w.color = x.parent.color x.parent.color = Color.BLACK w.right.color = Color.BLACK self.left_rotate(w.parent) x = self.root else: w = x.parent.left if w.color == Color.RED: w.color = Color.BLACK x.parent.color = Color.RED self.right_rotate(x.parent) w = x.parent.left if w.left.color == Color.BLACK and w.right.color == Color.BLACK: w.color = Color.RED x = x.parent else: if w.left.color == Color.BLACK: w.left.color = Color.BLACK w.color = Color.RED self.left_rotate(w) w = x.parent.left w.color = x.parent.color x.parent.color = Color.BLACK w.left.color = Color.BLACK self.right_rotate(w.parent) x = self.root x.color = Color.BLACK def minimum(self, node): while node.left is not self.nil: node = node.left return node def transplant(self, u, v): if u.parent is self.nil: self.root = v elif u is u.parent.left: u.parent.left = v else: u.parent.right = v v.parent = u.parent 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