A left-leaning red-black tree is a variant of a red-black tree. It restricts the positions of red edges (or nodes), so its insertion and deletion operations correspond one-to-one with those of a 2-3 tree.
We assume that readers know at least one rotation-based balanced tree, so this article does not explain rotations.
Red-black tree
Properties
A red-black tree satisfies the following properties:
- Every node is red or black.
- A NIL node (an empty leaf node) is black.
- Every child of a red node is black; equivalently, no path from a leaf to the root contains two consecutive red nodes.
- Every simple path from any node to each leaf in its subtree contains the same number of black nodes (black-height balance).
This ensures that the longest path from the root to any leaf (with alternating red and black nodes) is no more than twice the shortest path (all black), and therefore keeps the tree balanced.
Maintaining these properties is complicated. When a node is inserted, it must first be colored red; otherwise property 4 is broken. Even then, property 3 may be broken, so rebalancing is needed. Deletion is even more troublesome: as with insertion, a black node cannot be deleted because that would break black-height balance. How can these problems be handled conveniently?
Left-Leaning Red-Black Tree
Explanation
A left-leaning red-black tree is an easy-to-implement variant of a red-black tree.
In the diagrams below, edges rather than nodes are colored. We conventionally use the color of a node to mean the color of the edge from its parent.
A left-leaning red-black tree imposes a further restriction on the children of a black node:
- either both children are black;
- or the left child is red and the right child is black.
A valid configuration:
An invalid configuration:
This is the left-leaning property: red edges may lean only to the left.
Procedure
Insertion
First use ordinary BST insertion to add a red leaf at the bottom of the tree, then rebalance upward so that the resulting tree still satisfies the properties of a left-leaning red-black tree. The adjustment process is described below.
Insertion may create a right-leaning red edge, so perform a left rotation:
After the left rotation, two consecutive left-leaning red edges may appear:
Therefore perform a right rotation. After the right rotation, apply color_flip, that is, flip the colors of the node and its two children.
This eliminates the right-leaning red edge.
Reference code (partial)
template <class Key, class Compare>
typename Set<Key, Compare>::Node *Set<Key, Compare>::fix_up(
Set::Node *root) const {
if (is_red(root->rc) && !is_red(root->lc)) // fix right leaned red link
root = rotate_left(root);
if (is_red(root->lc) &&
is_red(root->lc->lc)) // fix doubly linked left leaned red link
// if (root->lc == nullptr), then the second expr won't be evaluated
root = rotate_right(root);
if (is_red(root->lc) && is_red(root->rc))
// break up 4 node
color_flip(root);
root->size = size(root->lc) + size(root->rc) + 1;
return root;
}
template <class Key, class Compare>
typename Set<Key, Compare>::Node_Set<Key, Compare>::insert(
Set::Node_root, const Key &key) const {
if (root == nullptr) return new Node(key, kRed, 1);
if (root->key == key)
;
else if (cmp\_(key, root->key)) // if (key < root->key)
root->lc = insert(root->lc, key);
else
root->rc = insert(root->rc, key);
return fix_up(root);
}
Deletion
Deletion is based on the following idea: a black node cannot be deleted because that would break black-height balance. Therefore, we must ensure that the node deleted at the end is red.
Deleting the minimum node
First consider deleting the minimum value in the entire tree.
How can we ensure that the final node deleted is red? During downward recursion, maintain this invariant: if the current node is h, then either h is red or h->lc is red.
If rotations and color flips can maintain this invariant, then when we reach the minimum node h_min, either h_min is red or its left subtree is red. But h_min has no left subtree at all, so the minimum node must be red. Since it is red, the reached node h_min can be deleted directly, and then the tree can be rebalanced using the same idea as for insertion.
We now consider how to satisfy this invariant. During downward recursion, some properties of the left-leaning red-black tree are temporarily violated, but they are restored when the recursion returns.
The following diagram shows a relatively simple case. Here h->rc->lc is black, so one color flip is enough:
After the flip shown above, h->rc and h->rc->lc do not form consecutive red edges.
If h->rc->lc is red, however, the situation is more complicated:
A color flip alone would create consecutive red edges, and this could not be repaired when returning from recursion, so additional handling is needed.
We can now perform the deletion:
Reference code (partial)
template <class Key, class Compare>
typename Set<Key, Compare>::Node *Set<Key, Compare>::move_red_left(
Set::Node *root) const {
color_flip(root);
if (is_red(root->rc->lc)) {
// assume that root->rc != nullptr when calling this function
root->rc = rotate_right(root->rc);
root = rotate_left(root);
color_flip(root);
}
return root;
}
template <class Key, class Compare>
typename Set<Key, Compare>::Node *Set<Key, Compare>::delete_min(
Set::Node *root) const {
if (root->lc == nullptr) {
delete root;
return nullptr;
}
if (!is_red(root->lc) && !is_red(root->lc->lc)) {
// make sure either root->lc or root->lc->lc is red
// thus make sure we will delete a red node in the end
root = move_red_left(root);
}
root->lc = delete_min(root->lc);
return fix_up(root);
}
Deleting an arbitrary node
First consider deleting a leaf. As with deleting the minimum, we maintain an invariant while deleting an arbitrary value. This time the situation is special because we may move either left or right. When moving left from a current node h, ensure that either h is red or h->lc is red; when moving right, ensure that either h is red or h->rc is red. This guarantees that the current node h is handled safely and that the final deleted node is always red.
Next consider deleting a non-leaf node. Find the minimum node in its right subtree, if one exists, replace the node's value with the minimum value of the right subtree, and finally delete that minimum node from the right subtree.
What if there is no right subtree? Rotate the left subtree into place so that this situation does not occur.
Reference code (partial)
template <class Key, class Compare>
typename Set<Key, Compare>::Node *Set<Key, Compare>::delete_arbitrary(
Set::Node *root, Key key) const {
if (cmp_(key, root->key)) {
// key < root->key
if (!is_red(root->lc) && !(is_red(root->lc->lc)))
root = move_red_left(root);
// ensure the invariant: either root->lc or root->lc->lc (or root and
// root->lc after dive into the function) is red, to ensure we will
// eventually delete a red node. therefore we will not break the black
// height balance
root->lc = delete_arbitrary(root->lc, key);
} else {
// key >= root->key
if (is_red(root->lc)) root = rotate_right(root);
if (key == root->key && root->rc == nullptr) {
delete root;
return nullptr;
}
if (!is_red(root->rc) && !is_red(root->rc->lc)) root = move_red_right(root);
if (key == root->key) {
root->key = get_min(root->rc);
root->rc = delete_min(root->rc);
} else {
root->rc = delete_arbitrary(root->rc, key);
}
}
return fix_up(root);
}
Implementation
The following code implements a Set using a left-leaning red-black tree; that is, an ordered set without duplicate elements.
Reference code
#include <algorithm>
#include <memory>
#include <vector>
template <class Key, class Compare = std::less<Key>>
class Set {
private:
enum NodeColor { kBlack = 0, kRed = 1 };
struct Node {
Key key;
Node *lc{nullptr}, *rc{nullptr};
size_t size{0};
NodeColor color; // the color of the parent link
Node(Key key, NodeColor color, size_t size)
: key(key), color(color), size(size) {}
Node() = default;
};
void destroyTree(Node *root) const {
if (root != nullptr) {
destroyTree(root->lc);
destroyTree(root->rc);
root->lc = root->rc = nullptr;
delete root;
}
}
bool is_red(const Node *nd) const {
return nd == nullptr ? false : nd->color; // kRed == 1, kBlack == 0
}
size_t size(const Node *nd) const { return nd == nullptr ? 0 : nd->size; }
Node *rotate_left(Node *node) const {
// left rotate a red link
// <1> <2>
// / \\ // \
// * <2> ==> <1> *
// / \ / \
// * * * *
Node *res = node->rc;
node->rc = res->lc;
res->lc = node;
res->color = node->color;
node->color = kRed;
res->size = node->size;
node->size = size(node->lc) + size(node->rc) + 1;
return res;
}
Node *rotate_right(Node *node) const {
// right rotate a red link
// <1> <2>
// // \ / \\
// <2> * ==> * <1>
// / \ / \
// * * * *
Node *res = node->lc;
node->lc = res->rc;
res->rc = node;
res->color = node->color;
node->color = kRed;
res->size = node->size;
node->size = size(node->lc) + size(node->rc) + 1;
return res;
}
NodeColor neg_color(NodeColor n) const { return n == kBlack ? kRed : kBlack; }
void color_flip(Node *node) const {
node->color = neg_color(node->color);
node->lc->color = neg_color(node->lc->color);
node->rc->color = neg_color(node->rc->color);
}
Node *insert(Node *root, const Key &key) const;
Node *delete_arbitrary(Node *root, Key key) const;
Node *delete_min(Node *root) const;
Node *move_red_right(Node *root) const;
Node *move_red_left(Node *root) const;
Node *fix_up(Node *root) const;
const Key &get_min(Node *root) const;
void serialize(Node *root, std::vector<Key> *) const;
void print_tree(Set::Node *root, int indent) const;
Compare cmp_ = Compare();
Node *root_{nullptr};
public:
using KeyType = Key;
using ValueType = Key;
using SizeType = std::size_t;
using DifferenceType = std::ptrdiff_t;
using KeyCompare = Compare;
using ValueCompare = Compare;
using Reference = Key &;
using ConstReference = const Key &;
Set() = default;
Set(Set &) = default;
Set(Set &&) noexcept = default;
~Set() { destroyTree(root_); }
SizeType size() const;
SizeType count(const KeyType &key) const;
SizeType erase(const KeyType &key);
void clear();
void insert(const KeyType &key);
bool empty() const;
std::vector<Key> serialize() const;
void print_tree() const;
};
template <class Key, class Compare>
typename Set<Key, Compare>::SizeType Set<Key, Compare>::count(
ConstReference key) const {
Node *x = root_;
while (x != nullptr) {
if (key == x->key) return 1;
if (cmp_(key, x->key)) // if (key < x->key)
x = x->lc;
else
x = x->rc;
}
return 0;
}
template <class Key, class Compare>
typename Set<Key, Compare>::SizeType Set<Key, Compare>::erase(
const KeyType &key) {
if (count(key) > 0) {
if (!is_red(root_->lc) && !(is_red(root_->rc))) root_->color = kRed;
root_ = delete_arbitrary(root_, key);
if (root_ != nullptr) root_->color = kBlack;
return 1;
} else {
return 0;
}
}
template <class Key, class Compare>
void Set<Key, Compare>::clear() {
destroyTree(root_);
root_ = nullptr;
}
template <class Key, class Compare>
void Set<Key, Compare>::insert(const KeyType &key) {
root_ = insert(root_, key);
root_->color = kBlack;
}
template <class Key, class Compare>
bool Set<Key, Compare>::empty() const {
return size(root_) == 0;
}
template <class Key, class Compare>
typename Set<Key, Compare>::Node *Set<Key, Compare>::insert(
Set::Node *root, const Key &key) const {
if (root == nullptr) return new Node(key, kRed, 1);
if (root->key == key)
;
else if (cmp_(key, root->key)) // if (key < root->key)
root->lc = insert(root->lc, key);
else
root->rc = insert(root->rc, key);
return fix_up(root);
}
template <class Key, class Compare>
typename Set<Key, Compare>::Node *Set<Key, Compare>::delete_min(
Set::Node *root) const {
if (root->lc == nullptr) {
delete root;
return nullptr;
}
if (!is_red(root->lc) && !is_red(root->lc->lc)) {
// make sure either root->lc or root->lc->lc is red
// thus make sure we will delete a red node in the end
root = move_red_left(root);
}
root->lc = delete_min(root->lc);
return fix_up(root);
}
template <class Key, class Compare>
typename Set<Key, Compare>::Node *Set<Key, Compare>::move_red_right(
Set::Node *root) const {
color_flip(root);
if (is_red(root->lc->lc)) { // assume that root->lc != nullptr when calling
// this function
root = rotate_right(root);
color_flip(root);
}
return root;
}
template <class Key, class Compare>
typename Set<Key, Compare>::Node *Set<Key, Compare>::move_red_left(
Set::Node *root) const {
color_flip(root);
if (is_red(root->rc->lc)) {
// assume that root->rc != nullptr when calling this function
root->rc = rotate_right(root->rc);
root = rotate_left(root);
color_flip(root);
}
return root;
}
template <class Key, class Compare>
typename Set<Key, Compare>::Node *Set<Key, Compare>::fix_up(
Set::Node *root) const {
if (is_red(root->rc) && !is_red(root->lc)) // fix right leaned red link
root = rotate_left(root);
if (is_red(root->lc) &&
is_red(root->lc->lc)) // fix doubly linked left leaned red link
// if (root->lc == nullptr), then the second expr won't be evaluated
root = rotate_right(root);
if (is_red(root->lc) && is_red(root->rc))
// break up 4 node
color_flip(root);
root->size = size(root->lc) + size(root->rc) + 1;
return root;
}
template <class Key, class Compare>
const Key &Set<Key, Compare>::get_min(Set::Node *root) const {
Node *x = root;
// will crash as intended when root == nullptr
for (; x->lc != nullptr; x = x->lc);
return x->key;
}
template <class Key, class Compare>
typename Set<Key, Compare>::SizeType Set<Key, Compare>::size() const {
return size(root_);
}
template <class Key, class Compare>
typename Set<Key, Compare>::Node *Set<Key, Compare>::delete_arbitrary(
Set::Node *root, Key key) const {
if (cmp_(key, root->key)) {
// key < root->key
if (!is_red(root->lc) && !(is_red(root->lc->lc)))
root = move_red_left(root);
// ensure the invariant: either root->lc or root->lc->lc (or root and
// root->lc after dive into the function) is red, to ensure we will
// eventually delete a red node. therefore we will not break the black
// height balance
root->lc = delete_arbitrary(root->lc, key);
} else {
// key >= root->key
if (is_red(root->lc)) root = rotate_right(root);
if (key == root->key && root->rc == nullptr) {
delete root;
return nullptr;
}
if (!is_red(root->rc) && !is_red(root->rc->lc)) root = move_red_right(root);
if (key == root->key) {
root->key = get_min(root->rc);
root->rc = delete_min(root->rc);
} else {
root->rc = delete_arbitrary(root->rc, key);
}
}
return fix_up(root);
}
template <class Key, class Compare>
std::vector<Key> Set<Key, Compare>::serialize() const {
std::vector<int> v;
serialize(root_, &v);
return v;
}
template <class Key, class Compare>
void Set<Key, Compare>::serialize(Set::Node *root,
std::vector<Key> *res) const {
if (root == nullptr) return;
serialize(root->lc, res);
res->push_back(root->key);
serialize(root->rc, res);
}
template <class Key, class Compare>
void Set<Key, Compare>::print_tree(Set::Node *root, int indent) const {
if (root == nullptr) return;
print_tree(root->lc, indent + 4);
std::cout << std::string(indent, '-') << root->key << std::endl;
print_tree(root->rc, indent + 4);
}
template <class Key, class Compare>
void Set<Key, Compare>::print_tree() const {
print_tree(root_, 0);
}
Relation to 2-3 trees
A 2-3 tree is a B-tree of order 3. Each node is either a 2-node or a 3-node and stores one or two data elements. A non-leaf 2-node or 3-node can have exactly two or three children, respectively. All data stored in a 2-3 tree are ordered.
A 2-3 tree and a left-leaning red-black tree are essentially equivalent. A 2-3 tree node can store one or two elements, whereas a red-black-tree node can store only one. As shown below, a 2-node corresponds to one black node, while a 3-node corresponds to one red node and one black node; the two can be viewed as parallel.
The following is the left-leaning red-black tree corresponding to a 2-3 tree.
Insertion and deletion in 2-3 trees and left-leaning red-black trees correspond one-to-one.1
References and further reading
- Left-Leaning Red-Black Trees - Robert Sedgewick, Princeton University
- Balanced Search Trees - Algorithms, Robert Sedgewick | Kevin Wayne
Footnotes
-
This blog post provides a detailed description. The term “red-black tree” in the post actually refers to a “left-leaning red-black tree”. ↩