玄妙的数据结构

左偏红黑树是红黑树的一个变体，它的对红边（点）的位置做了一定限制，使得其插入操作可以与 2-3-4 树构成一一对应。但是删除操作我怎么都对应不起来。

红黑树

性质

1. 节点是红色或黑色；
2. 从每个叶子到根的所有路径上不能有两个连续的红色节点；
3. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。（黑高平衡）

这保证了从根节点到任意叶子的最长路径（红黑交替）不会超过最短路径（全黑）的二倍。从而保证了树的平衡性。

维护这些性质是比较令人头秃的，如果我们要插入一个节点，首先它一定会被染色成红色，否则会破坏性质 3 。即使这样，我们还是有可能会破坏性质 2。因此需要进行各种奇妙的调整。而删除节点就更加麻烦，与插入类似，我们不能删除黑色节点，否则会破坏黑高的平衡。如何方便地解决这些问题呢？

左偏红黑树（Left Leaning Red Black Tree）

与普通的红黑树不同的是，在左偏红黑树中，我们习惯用一个节点的颜色代指它的父亲边的颜色。

左偏红黑树对红黑树进行了进一步限制，一个黑色节点的左右儿子：

• 要么全是黑色；
• 要么左儿子是红色，右儿子是黑色。

符合条件的情况：

不符合条件的情况：

这是左偏树的「左偏」性质：红色边只能是左偏的。

插入

我们首先使用普通的 BST 插入方法，在树的底部插入一个红色的叶子节点，然后通过从下向上的调整，使得插入后的树仍然符合左偏红黑树的性质。下面描述调整的过程：

插入后， 可能会产生一条右偏的红色边，因此需要对右偏的情况进行一次左旋：

考虑左旋后会产生两条连续的左偏红色边：

因此需要把它进行一次右旋。而对于右旋后的情况，我们应该对它进行 color_filp ：

从而消灭右偏的红边。

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

删除

感觉插入还行！现在我们来大战删除。

删除操作基于这样的思想：我们不能删除黑色的节点，这样会破坏黑高。因此我们需要保证我们最后删除的节点是红色的。

delete_min

首先来试一下删除整棵树里的最小值。

怎么才能保证最后删除的节点是红色的呢？我们需要在向下递归的过程中保证一个性质：如果当前节点是 h，那么需要保证 h 是红色，或者 h->lc 是红色。

考虑这样做的正确性，如果我们能够通过各种旋转和反转颜色操作成功维护这个性质，那么当我们到达最小的节点 h_min 的时候，有 h_min 是红色，或者 h_min -> lc ，嗯？？ 但是 h_min 根本没有左子树！，所以这就保证了最小值节点一定是红的，既然它是红色的，我们就可以大胆的删除它，然后用与插入操作相同的调整思路对树进行调整。

下面我们来考虑怎么满足这个性质，注意，我们会在向下递归的时候临时地破坏左偏红黑树的若干性质，但是当我们从递归返回时还会将其恢复。

上图描述一种简单的情况，我们只需要一次翻转颜色即可。

但如果 h->rc->lc 是红色，情况会比较复杂：

如果只进行翻转颜色，会产生连续红边，而考虑我们递归返回的时候，是无法修复这样的情况的，因此需要再转几下。

然后就可以删了：

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

delete_arbitrary

删，都可以删。

我们首先考虑删除叶子：与删最小值类似，我们这次也要维护一个性质，不过这次比较特殊，因为我们不是只能向左边走，而是可以 xjb 走，因此在删除过程中维护的性质是这样的：如果往左走，当前节点是 h，那么需要保证 h 是红色，或者 h->lc 是红色；如果往右走，当前节点是 h，那么需要保证 h 是红色，或者 h->rc 是红色。这样保证我们最后会删掉一个红色节点。

下面考虑删除非叶子节点，我们只需要找到其右子树（如果有）里的最大节点，然后用右子树的最大节点的值代替该节点的值，最后删除右子树里的最大节点。

那如果没有右子树怎么办？我们需要把左子树给转过来，就不会出现这个问题了。

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

}

Reference

• Left-Leaning Red-Black Trees - Robert Sedgewick Princeton University
• Balanced Search Trees - Algorithms Robert Sedgewick | Kevin Wayne