Skip to content

Left-Leaning Red–Black Tree

The Left-Leaning Red-Black Tree is a variant of the Red-Black Tree that imposes additional restrictions on the positions of red edges (nodes), enabling its insertion and deletion operations to have a one-to-one correspondence with the 2-3 tree.

We assume the reader is already familiar with at least one rotation-based balanced tree, so this article will not explain rotation operations.

Red-Black Tree

Properties

A red-black tree satisfies the following properties:

  1. Every node is either red or black.
  2. NIL nodes (empty leaf nodes) are black.
  3. All children of a red node must be black, meaning no two consecutive red nodes can appear on any path from a leaf to the root.
  4. Every simple path from any node to each leaf in its subtree contains the same number of black nodes. (Black-height balance)

These properties ensure that the longest path from the root to any leaf (alternating red and black) is at most twice as long as the shortest path (all black), thereby maintaining the tree's balance.

Maintaining these properties is relatively complex. If we insert a node, it must initially be colored red; otherwise, property 4 would be violated. Even so, we might still violate property 3, requiring adjustments. Deletion is even more troublesome: similar to insertion, we cannot delete a black node directly, as it would disrupt the black-height balance. How can we conveniently solve these problems?

Left-Leaning Red-Black Tree (LLRB Tree)

Explanation

The Left-Leaning Red-Black Tree is an easier-to-implement variant of the red-black tree.

In the following LLRB tree diagrams, the edges have colors rather than the nodes. By convention, we refer to a node's color as the color of the edge connecting it to its parent.

The LLRB tree imposes an additional restriction on the red-black tree: for any black node, its left and right children must satisfy one of the following:

  • Both children are black;
  • The left child is red, and the right child is black.

Valid cases:

llrbt1

Invalid cases:

llrbt2

This is the "left-leaning" property: red edges can only lean to the left.

Process

Insertion

We first use the standard BST insertion method to insert a red leaf node at the bottom of the tree. Then, through bottom-up adjustments, we ensure the tree still satisfies the LLRB tree properties after insertion. The adjustment process is described below:

llrbt3

After insertion, a right-leaning red edge may appear, so we perform a left rotation to fix the right-leaning red edge:

llrbt4

After the left rotation, two consecutive left-leaning red edges may appear:

llrbt5

Thus, we need to perform a right rotation. After the right rotation, we should perform a color_flip: i.e., flip the colors of this node and its two children.

llrbt6

This eliminates the right-leaning red edge.

Reference Code (Partial) 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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

The deletion operation is based on the idea that we cannot delete a black node because it would break the black-height. Therefore, we need to ensure that the node we finally delete is red.

Deleting the Minimum Node

First, let's try deleting the minimum node in the entire tree.

How can we ensure the final deleted node is red? We need to maintain an invariant during the downward recursion: if the current node is h, then we must ensure that h is red, or h->lc is red.

Consider the correctness of this approach: if we can successfully maintain this invariant through various rotations and color flips, then when we reach the minimum node h_min, we have that h_min is red, or h_min's left subtree—but h_min has no left subtree at all! This guarantees that the minimum node must be red. Since it is red, we can safely delete it, and then adjust the tree using the same adjustment logic as the insertion operation.

Now, let's consider how to satisfy this invariant. Note that we will temporarily break some properties of the LLRB tree during the downward recursion, but we will restore them when returning from the recursion.

As shown in the following diagram, this is a simpler case where h->rc->lc is black; we only need a single color flip:

llrbt-7

Moreover, after the flip as shown above, it will not create consecutive red edges between h->rc and h->rc->lc.

However, if h->rc->lc is red, the situation becomes more complex:

llrbt-8

If we only perform a color flip, consecutive red edges will appear. Considering that we cannot fix such a situation when returning from recursion, we need to handle it differently.

Then we can proceed with the deletion:

Reference Code (Partial) 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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

We first consider deleting a leaf: similar to deleting the minimum, we also need to maintain an invariant during the deletion of an arbitrary value. However, this time it's more special because we are not only moving left but can go in both left and right directions. Therefore, the invariant maintained during deletion is: if moving left, the current node is h, then we must ensure h is red, or h->lc is red; if moving right, the current node is h, then we must ensure h is red, or h->rc is red. This ensures we will eventually delete a red node.

Now consider deleting a non-leaf node. We only need to find the minimum node in its right subtree (if it exists), replace the node's value with the minimum node's value from the right subtree, and finally delete that minimum node from the right subtree.

llrbt-9

What if there is no right subtree? We need to rotate the left subtree over, which avoids this problem.

Reference Code (Partial) 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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 (ordered unique set) using a Left-Leaning Red-Black Tree:

Reference Code 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
#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);
}

Relationship with 2-3 Trees

A 2-3 tree is a 3rd-order B-tree where each node is either a 2-node or a 3-node, storing one or two data elements. Non-leaf 2-nodes and 3-nodes can only have two or three children, respectively. Moreover, all data stored in a 2-3 tree are ordered.

2-3 trees and left-leaning red-black trees are essentially equivalent. A node in a 2-3 tree can store 1 or 2 elements, while a node in a red-black tree can only store one element. As shown in the following diagrams, a 2-node in a 2-3 tree corresponds to a black node, and a 3-node corresponds to a red node and a black node (consider bc as parallel).

2-3-tree-rbt

2-3-tree-rbt

The following diagram shows a left-leaning red-black tree corresponding to a 2-3 tree.

2-3-tree-rbt

The insertion and deletion operations of 2-3 trees and left-leaning red-black trees have a one-to-one correspondence.1

References and Further Reading

  1. This blog post provides a detailed description. The "red-black tree" mentioned in the article actually refers to the "left-leaning red-black tree". ↩

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用