Data Structures with Generic Types in Python/

...

/

Red-Black Tree Operations

Red-Black Tree Operations

Learn to add and remove an element in red-black trees.

We'll cover the following...

Addition

To implement add(x) in a RedBlackTree, we perform a standard BinarySearchTree insertion to add a new leaf, u, with u.x = x and set u.colour = red. Note that this does not change the black height of any node, so it does not violate the black-height property. It may, however, violate the left-leaning property (if u is the right child of its parent), and it may violate the no-red-edge property (if u’s parent is red). To restore these properties, we call the method add_fixup(u).

class RedBlackTree(BinarySearchTree):
    class Node(BinarySearchTree.Node):
        def __init__(self, x):
            super(RedBlackTree.Node, self).__init__(x)
            self.colour = black
        
    def __init__(self, iterable=[]):
        self.nil = RedBlackTree.Node(None)
        self.nil.right = self.nil.left = self.nil.parent = self.nil
        super(RedBlackTree, self).__init__([], self.nil)
        self.r = self.nil
        self.add_all(iterable)
        
    def add(self, x):
        u = self._new_node(x)
        u.colour = red
        if self.add_node(u):
            self.add_fixup(u)
            return True
        return False

A single round in the process of fixing Property 2 after an insertion is illustrated in the below illustration:

The add_fixup(u) method takes as input a node u whose color is red and which may violate the no-red-edge property and/or the left-leaning property. The following discussion is probably impossible to follow without referring to the above figure or recreating it on a piece of paper. Indeed, the reader may wish to study the above figure before continuing.

If u is the root of the tree, then we can color u black to restore both properties. If u’s sibling is also red, then u’s parent must be black, so both the left-leaning and no-red-edge properties already hold.

Otherwise, we first determine if u’s parent, w, violates the left-leaning property and, if so, perform a flip_left(w) operation and set u = w. This leaves us in a well-defined state: u is the left child of its parent, w, so w now satisfies the left-leaning property. All that remains is to ensure the no-red-edge property at u. We only have to worry about the case in which w is red, since otherwise u already satisfies the no-red-edge property.

Since we are not done yet, u is red and w is red. The no-red-edge property (which is only violated by u and not by w) implies that u’s grandparent g exists and is black. If g’s right child is red, then the left-leaning property ensures that both g’s children are red, and a call to push_black(g) makes g red and w black. This restores the no-red-edge property at u, but may cause it to be violated at g, so the whole process starts over with u = g.

If g's right child is black, then a call to flip_right(g) makes w the (black) parent of g and gives w two red children, u and g. This ensures that u satisfies the no-red-edge property and g satisfies the left-leaning property. In this case we can stop.

class RedBlackTree(BinarySearchTree):
    class Node(BinarySearchTree.Node):
        def __init__(self, x):
            super(RedBlackTree.Node, self).__init__(x)
            self.colour = black
  
    def __init__(self, iterable=[]):
        self.nil = RedBlackTree.Node(None)
        self.nil.right = self.nil.left = self.nil.parent = self.nil
        super(RedBlackTree, self).__init__([], self.nil)
        self.r = self.nil
        self.add_all(iterable)
    
    def add_fixup(self, u):
        while u.colour == red:
            if u == self.r:
                u.colour = black
            w = u.parent
            if w.left.colour == black:
                self.flip_left(w)
                u = w
                w = u.parent
            if w.colour == black:
                return   # red-red edge is eliminated - done
            g = w.parent
            if g.right.colour == black:
                self.flip_right(g)
                return
            self.push_black(g)
            u = g

The add_fixup(u) method takes constant time per iteration and each iteration either finishes or moves u closer to the root. Therefore, the add_fixup(u) method finishes after O(log⁡n)O(\log n) iterations in O(log⁡n)O(\log n) time.

Removal

The remove(x) operation in a RedBlackTree is the most complicated to implement, and this is true of all known red-black tree variants. Just like the remove(x) operation in a BinarySearchTree, this operation boils down to finding a node w with only one child, u, and splicing w out of the tree by having w.parent adopt u.

The problem with this is that, if w is black, then the black-height property will now be violated at w.parent. We may avoid this problem, temporarily, by adding w.colour to u.colour. Of course, this introduces two other problems: (1) if u and w both started out black, then ...