Single Pass Top-Down Deletion for Red/Black Trees

mgcadmin 01-09-2026

Depending on which resource you first encounter an algorithmic description of red black trees in you will encounter one of two lineages (and possibly a third, more on that in a bit): Those which descend from the original Sedgewick/Guibas[1] algorithms, and those which descend from the listing in CLRS[2]. Before 2008, this meant either top down without parent pointers, or bottom up with parent pointers. Both lineages model 2-3-4 trees with red links slanting in any direction. For the most part, both lineages were presented as iterative algorithms, with the exception of the implementation presented in the 3rd edition of "Algorithms", which was recursive.

With few exceptions, every production-grade implementation of Red/Black Trees, such as the versions included in the C++ STL are derived from the CLRS lineage. There is two predominant circumstances which lead to this being the case. The first and most cited reason is that number of rotation performed for each insertion and deletion is bounded in bottom up red black trees. Additionally, the use of parent pointers allows for the implementation of iterators which use O(1) space instead of storing their path for backtracking. Another, albeit somewhat less important reason is that while there was an (incomplete) description of the algorithm in the 1978 paper, none of Sedgewicks books included the deletion algorithm!  

This last issue was finally addressed (at least partially) In 2008 when Sedgewick revived an old idea first leveraged by Arne Anderson to enforce a constraint on the direction which red links leaned[4]. The result was Left Leaning Red/Black trees, which replaced the original Red/Black tree in the fourth edition of his book "Algorithms". And unlike the first three editions of the text, this one included a full implementation of the delete algorithm.

I said it was partially addressed because while it is a top down algorithm, as presented it unfortunately only works for the 2-3 tree based variant of the left-leaning trees. It is also not a "true" top-down algorithm as it still requires rotations on the way back up the tree. Something is better than nothing however, and while not exactly the same as the original, the algorithm from the 2008 paper does follow the same general idea originally proposed in the 1978 paper and later reiterated as an exercise of the 3rd edition of "Algorithms".

After alot of research, frustration, and false starts, it was ultimately the 2008 paper which would act as a sort of "rosetta stone" between the high level description presented as an exercise in the 3rd edition book, and the not-so-clear pseudocode of the 1978 paper, and enabled me to implement the single pass top dop algorithm I'm going to present in this article. So without further ado, let's get to it.

The Driving Idea

As mentioned, top down deletion works from a simple premise as described in the original 1978 article. We know that deleting a leaf node from a binary search tree requires no additional work besides removing the leaf. Additionally, deleting a red node  from a red/black tree does not effect the black height of the tree and so requires no after-deletion fix up logic once completed. It then holds that if we can reduce every deletion to such a case (which we can, as shown by the fundamental theorem of rotations) then we should be able to delete any value from the tree in a single top-down pass.

This approach was repeated as two exercises where the reader was first encouraged to "develop an implementation of the search procedure that through the use of rotations and colorflips ensured that the current node or one of it's children is red." And then use this search procedure to implement deletion by ensuring that the node being removed from the tree was always red. We accomplish this by "pushing" a red node down the tree towards the leaf through a series of color flips and rotations, using what is essentially the reverse logic of insertion.

       link rotL(link h) {
            link x = h->right; h->right = x->left; x->left = h;
            x->color = h->color;
            h->color = red;
            return x;
        }

        link rotR(link h) {
            link x = h->left; h->left = x->right; x->right = h;
            x->color = h->color;
            h->color = red;
            return x;
        }

        link colorFlip(link h) {
            h->color = !h->color;
            if (h->left)
                h->left->color = !h->left->color;
            if (h->right)
                h->right->color = !h->right->color;
            return h;
        }

Top-Down BST Deletion

What's great about this method, is that it is almost identical to normal deletion in a binary search tree. So long as we maintain the invariant that the node to be deleted is a red leaf, everything proceeds identically to a normal top down deletion. To help maintain the invariant, we begin by coloring the root node red.

void erase(K data) {
       if (empty()) 
           return;
       if (isBlack(root->left) && isBlack(root->right)) {
           root->color = red;
       }
       root = eraseR(root, data);
       if (root != nullptr) root->color = black;
}

Since we want to maintain this invariant at all times, it is performed as soon as we know the current root is not null. Once the path is prepared, we continue searching down the tree for the desired value.

        link eraseR(link h, K key) {
            if (h == nullptr)
                return h;
            h = pushRedDown(h, key);
            if (key < h->info) {
                h->left = eraseR(h->left, key);
            } else if (key > h->info) {
                h->right = eraseR(h->right, key);
            } else {
                if (key == h->info && h->right == nullptr) {
                    link t = h;
                    h = h->left;
                    delete t;
                    return h;
                }
                link tmp = min(h->right);
                h->info = tmp->info;
                h->right = eraseR(h->right, h->info);
            }
            return h;
        }

When we find the value we want to delete from the tree, we proceed one of two ways based on it's position in the greater tree. If the key we're looking for also happens to be a leaf node, we simply remove it and were done. If the key is at an internal node, we replace it's value by that of it's in-order successor, and then continue the deletion by deleting the node we just copy the replacement value from.

Pushing Red Nodes "Down"

 

        link pushRedDown(link p, K key) {
            link x, s;
            bool wentLeft = key < p->info;
            if (wentLeft) {
                x = p->left;
                s = p->right;
            } else {
                x = p->right;
                s = p->left;
            }
            if (isBlack(x) && isRed(s)) {
                p = wentLeft ? rotL(p):rotR(p);
            }
            x = wentLeft ? p->left:p->right;
            if (x && isBlack(x) && isBlack(x->left) && isBlack(x->right)) {
                p = key < p->info ? pushLeft(p):pushRight(p);
            }
            return p;
        }

 

        link pushRight(link h) {
            h = colorFlip(h);
            if (h->left) {
                if (isRed(h->left) && isRed(h->left->right)) {
                    h->left = rotL(h->left);
                    h = rotR(h);
                    h = colorFlip(h);
                } else if (isRed(h->left) && isRed(h->left->left)) {
                    h = rotR(h);
                    h = colorFlip(h);
                }
            }
            return h;
        }
        link pushLeft(link h) {
            h = colorFlip(h);
            if (h->right) {
                if (isRed(h->right) && isRed(h->right->left)) {
                    h->right = rotR(h->right);
                    h = rotL(h);
                    h = colorFlip(h);
                } else if (isRed(h->right) && isRed(h->right->right)) {
                    h = rotL(h);
                    h = colorFlip(h);
                }
            }
            return h;
        }

Further Reading

[1] Sedgewick, Guibas "A dichromatic framework for balanced trees", 1978

[2] Cormen, Et. Al. "Introduction to Algorithms", 1989

[3] Anderson, Arne "Balanced Search Trees Made Simple", 1993

[4] Sedgewick, Wayne "Algorithms", 2011 (4th ed)

[5] Sedgewick "Algorithms", 1992 (2nd ed.)

---