Problem 13.1

Persistent dynamic sets

During the course of an algorithm, we sometimes find that we need to maintain past versions of a dynamic set as it is updated. We call such a set persistent. One way to implement a persistent set is to copy the entire set whenever it is modified, but this approach can slow down a program and also consume much space. Sometimes, we can do much better.

Consider a persistent set $S$ with the operations INSERT, DELETE, and SEARCH which we implement using binary search trees as shown in Figure 13.8(a). We maintain a separate root for every version of the set. In order to insert the key 5 into the set, we create a new node with key 5. This node becomes the left child of a new node with key 7, since we cannot modify the existing node with key 7. Similarly, the new node with key 7 becomes the left child of a new node with key 8 whose right child is the existing node with key 10. The new node with key 8 become, in turn, the right child of a new root $r'$ with key 4 whose left child is the existing node with key 3. We thus copy only part of the tree and share some of the nodes with the original tree, as shown in Figure 13.8(b).

Assume that each tree node has the attributes $key$, $left$, and $right$ but no parent (See also Exercise 13.3-6).

  1. For a general persistent binary search tree, identify the nodes that we need to change to insert a key $k$ or delete a node $y$.
  2. Write a procedure PERSISTENT-TREE-INSERT that, given a persistent tree $T$ and a key $k$ to insert, return a new persistent tree $T'$ that is the result of inserting $k$ into $T$.
  3. If the height of the persistent binary search tree $T$ is $h$, what are the time and space requirements of your implementation of PERSISTENT-TREE-INSERT? (The space requirement is proportional to the number of new nodes allocated.)
  4. Suppose that we had included the parent attribute in each node. In this case, PERSISTENT-TREE-INSERT would need to perform additional copying. Prove that PERSISTENT-TREE-INSERT would then require $\Omega(n)$ time and space, where $n$ is the number of nodes in the tree.
  5. Show how to use red-black trees to guarantee that the worst-case running time and space are $\O(\lg n)$ per insertion and deletion.

What needs to change

Very simply, every time we need to change a node, we have to make a copy of the node an all its ancestors.

Including a parent attribute

If we included a parent attribute, every time we make a copy of the parent, we would have to copy both of it's children, because the children need to refer to the new parent. This essentially means that the whole tree will need to be copied. By not keeping track of the parent, we can reuse the unchanged child.

Complexity

The complexity of insertion and deletion is $\O(\lg n)$, since We only modify nodes from the inserted/deleted position to the root, plus a constant number of other nodes.

Implementation

The exercise just for PERSISTENT-TREE-INSERT, but I decided to go for the full thing, and implement a persistent red-black tree. It was a horrible ordeal that was pretty hard to debug and get right. I shudder to imagine the agony if I attempted to do it in C, instead of Python.

Anyway, here are some notes.

First, both RB-INSERT-FIXUP and RB-DELETE-FIXUP repeat a lot of code in the two branches, with "left" and "right" reversed. This is too much work, so I will generalized the operations a bit so they can work with a direction (that can be either left or right) and flip that direction when necessary.

Since we no longer keep track of parents, we need to calculate the ancestor chain when we get to a node, so we can later make copies. A few functions have been modified to keep track of the chain.

Maintaining a sentinel becomes tricky as well, so the sentinel is removed and replaced with None, along with all the necessary checks.

Python code

from enum import Enum
from collections import deque


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


UNCHANGED = object()


# In order to avoid duplicating symmetric code based on whether a child is left
# or right, we can work with directions instead. In order to be able to, we need
# to be able to flip a direction as well.
def other(direction):
    if direction == 'left':
        return 'right'
    elif direction == 'right':
        return 'left'
    else:
        assert(False)


def isBlackOrNil(node):
    return not node or node.isBlack()


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

    def __str__(self):
        return str(self.key)

    __repr__ = __str__

    def isRed(self):
        return self.color == Color.RED

    def isBlack(self):
        return self.color == Color.BLACK

    def child_direction(self, child):
        assert(child is not None)

        if self.left is child:
            return 'left'
        elif self.right is child:
            return 'right'
        else:
            assert(False)

    def child(self, direction):
        if direction == 'left':
            return self.left
        elif direction == 'right':
            return self.right
        else:
            assert(False)

    def set_child(self, direction, child):
        if direction == 'left':
            self.left = child
        elif direction == 'right':
            self.right = child
        else:
            assert(False)

    def with_replaced_child(self, replacement, child):
        assert(child is not None)

        if self.left is child:
            return self.copy(left=replacement)
        elif self.right is child:
            return self.copy(right=replacement)
        else:
            assert(False)

    def replace_child(self, replacement, child):
        assert(child is not None)

        if self.left is child:
            self.left = replacement
            return replacement
        elif self.right is child:
            self.right = replacement
            return replacement
        else:
            assert(False)

    def other(self, direction):
        return self.child(other(direction))

    def sexp(self):
        def sexp(node):
            if node:
                return node.sexp()
            else:
                return '_'

        color = 'R' if self.color == Color.RED else 'B'

        return f"{color}({self.key}, {sexp(self.left)}, {sexp(self.right)})"

    def copy(self, key=UNCHANGED, color=UNCHANGED, left=UNCHANGED, right=UNCHANGED):
        new = Node(self.color, self.key, self.left, self.right)

        if key is not UNCHANGED:
            new.key = key
        if color is not UNCHANGED:
            new.color = color
        if left is not UNCHANGED:
            new.left = left
        if right is not UNCHANGED:
            new.right = right

        return new

    def left_rotate(self):
        y = self.right
        return y.copy(left=self.copy(right=y.left))

    def right_rotate(self):
        x = self.left
        return x.copy(right=self.copy(left=x.right))

    def rotate(self, direction):
        if direction == 'left':
            return self.left_rotate()
        elif direction == 'right':
            return self.right_rotate()
        else:
            assert(False)

    # Returns the minimal node and the chain of ancestors that was traversed in
    # order to find it
    def minimum_with_ancestors(self):
        node = self
        ancestors = []

        while node.left:
            ancestors.append(node)
            node = node.left

        return (node, ancestors)


# Replaces a node at the bottom of an ancestor chains, and creates a new version
# of the chain where each parent is copied and updated to point to a newly
# created child.
#
# The final parent in `ancestors` should have `replaced` as a child. It creates
# a copy of the parent, replacing the child with `inserted` and then proceeds up
# the chain, updating every ancestor.
#
# At the end, it returns a new ancestor chain, where each node is a copy of the
# original, with an updated child.
def update_ancestor_chain(inserted, replaced, ancestors):
    ancestors = ancestors[:]
    result = [inserted]

    while ancestors:
        ancestor = ancestors.pop()
        inserted = ancestor.with_replaced_child(inserted, replaced)
        result.append(inserted)
        replaced = ancestor

    result.reverse()

    return result


class Tree:
    def __init__(self, root=None):
        self.root = root

    def __str__(self):
        if self.root:
            return self.root.sexp()
        else:
            return "NIL"

    __repr__ = __str__

    def search(self, key):
        node = self.root

        while node:
            if node.key == key:
                return node
            elif key < node.key:
                node = node.left
            else:
                node = node.right

        return None

    def black_heights(self):
        if not self.root:
            return {0}

        heights = set()
        left = deque()

        if self.root:
            left.append((self.root, 0))

        while left:
            (node, height) = left.popleft()
            if node.isBlack():
                height += 1

            if node.left:
                left.append((node.left, height))
            else:
                heights.add(height + 1)

            if node.right:
                left.append((node.right, height))
            else:
                heights.add(height + 1)

        return heights

    def nodes(self):
        items = deque()

        if self.root:
            items.append(self.root)

        while items:
            node = items.popleft()

            yield node

            if node.left:
                items.append(node.left)

            if node.right:
                items.append(node.right)

    def insert(self, key):
        new = Node(Color.RED, key)
        parent = None
        current = self.root
        ancestors = []

        while current:
            parent = current
            ancestors.append(parent)

            if new.key < current.key:
                current = current.left
            else:
                current = current.right

        if ancestors:
            ancestors.pop()

        if not parent:
            return Tree(root=new.copy(color=Color.BLACK))
        elif new.key < parent.key:
            ancestors = update_ancestor_chain(parent.copy(left=new), parent, ancestors)
        else:
            ancestors = update_ancestor_chain(parent.copy(right=new), parent, ancestors)

        root = self.insert_fixup(new, ancestors)

        return Tree(root=root)

    def insert_fixup(self, current, ancestors):
        root = ancestors[0]

        while ancestors and ancestors[-1].isRed():
            parent = ancestors[-1]
            direction = ancestors[-2].child_direction(parent)
            grandfather = ancestors[-2]
            uncle = grandfather.other(direction)

            if uncle and uncle.isRed():
                parent.color = Color.BLACK
                grandfather.color = Color.RED
                grandfather.set_child(other(direction), uncle.copy(color=Color.BLACK))

                current = grandfather
                ancestors.pop()
                ancestors.pop()
            else:
                if current is parent.other(direction):
                    parent = parent.rotate(direction)
                    grandfather.set_child(direction, parent)
                    ancestors[-1] = parent
                    current = parent.child(direction)

                parent.color = Color.BLACK
                grandfather.color = Color.RED
                grandgrandfather = ancestors[-3] if len(ancestors) >= 3 else None
                parent = grandfather.rotate(other(direction))

                if not grandgrandfather:
                    root = parent
                else:
                    grandgrandfather.replace_child(parent, grandfather)

                break

        root.color = Color.BLACK

        return root

    def search_with_ancestors(self, key):
        node = self.root
        ancestors = []

        while node:
            if key == node.key:
                return (node, ancestors)
            elif key < node.key:
                ancestors.append(node)
                node = node.left
            else:
                ancestors.append(node)
                node = node.right

        return (None, None)

    def delete(self, key):
        deleted, ancestors = self.search_with_ancestors(key)
        original_color = deleted.color

        if not deleted.left and not deleted.right:
            ancestors = update_ancestor_chain(None, deleted, ancestors)
        elif not deleted.left:
            ancestors = update_ancestor_chain(deleted.right.copy(), deleted, ancestors)
        elif not deleted.right:
            ancestors = update_ancestor_chain(deleted.left.copy(), deleted, ancestors)
        else:
            moved, moved_ancestors = deleted.right.minimum_with_ancestors()

            original_color = moved.color
            extra_black = moved.right.copy() if moved.right else None
            span = []

            if moved_ancestors:
                span = update_ancestor_chain(extra_black, moved, moved_ancestors)
                moved = moved.copy(right=span[0])
                span.pop()

            elif moved.right:
                moved = moved.copy(right=extra_black)

            ancestors = update_ancestor_chain(
                    moved.copy(left=deleted.left, color=deleted.color),
                    deleted,
                    ancestors
                )

            ancestors += span
            ancestors.append(extra_black)

        root = ancestors[0]

        if original_color == Color.BLACK:
            root = self.delete_fixup(ancestors)

        return Tree(root=root)

    def delete_fixup(self, ancestors):
        ancestors = ancestors[:]
        node = ancestors.pop()

        def replace_top(new_top):
            old_top = ancestors.pop()
            if ancestors:
                ancestors[-1].replace_child(new_top, old_top)

            ancestors.append(new_top)

        while ancestors and isBlackOrNil(node):
            if node:
                direction = ancestors[-1].child_direction(node)
            elif ancestors[-1].left:
                direction = 'right'
            else:
                direction = 'left'

            sibling = ancestors[-1].other(direction)

            if sibling and sibling.isRed():
                new_top = ancestors[-1].rotate(direction)
                new_top.color = Color.BLACK
                new_top.child(direction).color = Color.RED

                replace_top(new_top)
                ancestors.append(new_top.child(direction))
                node = new_top.child(direction).child(direction)
                sibling = new_top.child(direction).other(direction)

            if isBlackOrNil(sibling.left) and isBlackOrNil(sibling.right):
                ancestors[-1].replace_child(sibling.copy(color=Color.RED), sibling)
                node = ancestors.pop()
            else:
                if isBlackOrNil(sibling.other(direction)):
                    new_sibling = sibling.rotate(other(direction))
                    new_sibling.color = Color.BLACK
                    new_sibling.other(direction).color = Color.RED

                    ancestors[-1].replace_child(new_sibling, sibling)
                    sibling = new_sibling

                new_top = ancestors[-1].rotate(direction)
                new_top.color = ancestors[-1].color
                new_top.child(direction).color = Color.BLACK
                new_top.replace_child(new_top.other(direction).copy(color=Color.BLACK), new_top.other(direction))
                node = None
                replace_top(new_top)
                break

        if node:
            node.color = Color.BLACK

        return ancestors[0] if ancestors else node