跳转至

左偏紅黑樹

左偏紅黑樹是紅黑樹的一種變體，它的對紅邊（點）的位置做了一定限制，使得其插入與刪除操作可以與 2-3 樹構成一一對應。

我們假設讀者已經至少掌握了一種基於旋轉的平衡樹，因此本文不會對旋轉操作進行講解。

紅黑樹

性質

一棵紅黑樹滿足如下性質：

  1. 節點是紅色或黑色；
  2. NIL 節點（空葉子節點）為黑色；
  3. 紅色的節點的所有兒子的顏色必須是黑色，即從每個葉子到根的所有路徑上不能有兩個連續的紅色節點；
  4. 從任一節點到其子樹中的每個葉子的所有簡單路徑上都包含相同數目的黑色節點。（黑高平衡）

這保證了從根節點到任意葉子的最長路徑（紅黑交替）不會超過最短路徑（全黑）的二倍。從而保證了樹的平衡性。

維護這些性質是比較複雜的，如果我們要插入一個節點，首先，它一定會被染色成紅色，否則會破壞性質 3。即使這樣，我們還是有可能會破壞性質 2。因此需要進行調整。而刪除節點就更加麻煩，與插入類似，我們不能刪除黑色節點，否則會破壞黑高的平衡。如何方便地解決這些問題呢？

左偏紅黑樹（Left Leaning Red Black Tree）

解釋

左偏紅黑樹是一種容易實現的紅黑樹變體。

在以下左偏紅黑樹示意圖中，是邊具有顏色而不是節點具有顏色。我們習慣用一個節點的顏色代指它的父親邊的顏色。

左偏紅黑樹對紅黑樹進行了進一步限制，一個黑色節點的左右兒子：

  • 要麼全是黑色；
  • 要麼左兒子是紅色，右兒子是黑色。

符合條件的情況：

llrbt1

不符合條件的情況：

llrbt2

這是左偏樹的「左偏」性質：紅色邊只能是左偏的。

過程

插入

我們首先使用普通的 BST 插入方法，在樹的底部插入一個紅色的葉子節點，然後通過從下向上的調整，使得插入後的樹仍然符合左偏紅黑樹的性質。下面描述調整的過程：

llrbt3

插入後，可能會產生一條右偏的紅色邊，因此需要對紅邊右偏的情況進行一次左旋：

llrbt4

考慮左旋後會產生兩條連續的左偏紅色邊：

llrbt5

因此需要把它進行一次右旋。而對於右旋後的情況，我們應該對它進行 color_flip：即翻轉該節點和它的兩個兒子的顏色

llrbt6

從而消滅右偏的紅邊。

參考代碼（部分） 
 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);
}

刪除

刪除操作基於這樣的思想：我們不能刪除黑色的節點，因為這樣會破壞黑高。所以我們需要保證我們最後刪除的節點是紅色的。

刪除最小值節點

首先來試一下刪除整棵樹裏的最小值。

怎麼才能保證最後刪除的節點是紅色的呢？我們需要在向下遞歸的過程中保證一個性質：如果當前節點是 h，那麼需要保證 h 是紅色，或者 h->lc 是紅色。

考慮這樣做的正確性，如果我們能夠通過各種旋轉和反轉顏色操作成功維護這個性質，那麼當我們到達最小的節點 h_min 的時候，有 h_min 是紅色，或者 h_min 的左子樹——但是 h_min 根本沒有左子樹！所以這就保證了最小值節點一定是紅的，既然它是紅色的，我們就可以大膽的刪除它，然後用與插入操作相同的調整思路對樹進行調整。

下面我們來考慮怎麼滿足這個性質，注意，我們會在向下遞歸的時候 臨時地 破壞左偏紅黑樹的若干性質，但是當我們從遞歸中返回時還會將其恢復。

llrbt-7

下圖描述一種簡單的情況，我們只需要一次翻轉顏色即可。

但如果 h->rc->lc 是紅色，情況會比較複雜：

llrbt-8

如果只進行翻轉顏色，會產生連續的紅邊，而考慮我們遞歸返回的時候，是無法修復這樣的情況的，因此需要進行處理。

然後就可以進行刪除了：

參考代碼（部分） 
 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);
}
刪除任意節點

我們首先考慮刪除葉子：與刪最小值類似，我們在刪除任意值的過程中也要維護一個性質，不過這次比較特殊，因為我們不是隻向左邊走，而是可以向左右兩個方向走，因此在刪除過程中維護的性質是這樣的：如果往左走，當前節點是 h，那麼需要保證 h 是紅色，或者 h->lc 是紅色；如果往右走，當前節點是 h，那麼需要保證 h 是紅色，或者 h->rc 是紅色。這樣可以保證我們最後總會刪掉一個紅色節點。

下面考慮刪除非葉子節點，我們只需要找到其右子樹（如果有）裏的最小節點，然後用右子樹的最小節點的值代替該節點的值，最後刪除右子樹裏的最小節點。

llrbt-9

那如果沒有右子樹怎麼辦？我們需要把左子樹旋轉過來，這樣就不會出現這個問題了。

參考代碼（部分） 
 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);
}

實現

下面的代碼是用左偏紅黑樹實現的 Set，即有序不可重集合：

參考代碼 
  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
311
#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:
  typedef Key KeyType;
  typedef Key ValueType;
  typedef std::size_t SizeType;
  typedef std::ptrdiff_t DifferenceType;
  typedef Compare KeyCompare;
  typedef Compare ValueCompare;
  typedef Key &Reference;
  typedef const Key &ConstReference;

  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);
}

參考資料與拓展閲讀

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