Search⌘ K
AI Features
Home
Courses
Data Structures with Generic Types in Python

Red-Black Tree Operations

Explore the key operations to add and remove nodes in red-black trees, including fixing violations of tree properties through rotations and recoloring. Understand how these maintain balanced search trees with guaranteed O(log n) performance. This lesson helps you grasp complex balancing techniques fundamental for efficient data storage and retrieval.

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).

Python 3.10.4
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.

Python 3.10.4
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 ...