沉思录

种一棵树最好的时间是十年前，其次是现在。

红黑树

1972年，Rudolf Bayer 创造了一种完美的平衡树 (并非二叉搜索树)，当时称为对称二元B树 (symmetric binary B-tree)，后来以2-3-4树或2-4树的形式开始流行。同年，Leonidas J. Guibas 和 Robert Sedgewick 在论文〈A Dichromatic Framework for Balanced Trees〉中，从对称二元B树中推导出红黑树(Red-black tree)。

红黑树是另一种自平衡二叉查找树，它的节点状态用红色和黑色来表示，也就是说，它的每一个节点，要么是红色，要么是黑色。节点颜色只是一个比喻，并不是非得红色和黑色，可以用任意两种颜色或能区分开来的值来表示。下图是一棵典型的红黑树。

一棵红黑树

红黑树可以在 O(log__n__) 时间内完成插入、查找和删除。它的结构复杂，它是一种特殊的二叉查找树，它拥有这五个性质：

  1. 每个节点要么是黑色要么是红色。
  2. 根节点始终是黑色。
  3. 每个 None/null 结点都是黑色。
  4. 两个红色节点不能直接相连。
  5. 从任一节点到其每个叶节点的所有简单路径，包含相同数目的黑色节点。

这五个性质也称为红黑性质。需要特别说明的是第3点：空节点算作黑色节点，有时会在图中画出，有时不画。但不管怎样，空节点始终算作黑色节点。第4点指的是两个红色节点不能互为父子关系，即同一条简单路径的两个红色节点中间，至少存在一个黑色节点将它们隔开，两个红色节点不能父子相连。第5点确保了最长路径的长度最多只能是最短路径的两倍，黑树是近似平衡的二叉查找树。如果从任一节点到叶结点的路径中都是黑色节点，这时路径最短。如果路径中是红黑相间的节点，这时路径最长。

当插入节点和删除节点时，若破坏了任意一个红黑性质，需要重新调整以满足红黑性质。不同于AVL树仅需通过旋转即可恢复平衡，红黑树的自平衡除了旋转，还需要变色。红黑树的旋转跟 AVL 树并没有什么不同，变色指的是将节点颜色由红变黑或黑变红。

添加节点

红黑树本身是二叉查找树，也是以二叉查找树的标准方式插入节点。新节点会被标记为红色，然后通过旋转相应子树和对相应节点重新标记颜色使之恢复平衡。

之所以将新节点设置为红色，是因为红色破坏属性的可能性最小。如果将新节点设为黑色，那么从根到叶结点这条路径上的黑色节点数量会比其它路径多1，违背了特性5，很难调整，设定成红色能让我们少违背一条特性，即便可能会出现两个连续红色节点的冲突违背特性4的情况，也是可以通过后续对树的旋转和颜色调换(color flips) 来修正。以下图为例。

基础示例

💡 TIP
设计红黑树时，通常不允许重复数据，如果插入相等的值，那么新值会在相应节点上替换旧值。

首先，将新插入的节点标记为红色。如果它是根节点，则将其更改为黑色，此时插入过程已经结束；如果它不是作为根节点插入，则检查其父节点的颜色，如果父节点是黑色的，那么插入过程结束；如果父节点是红色的，则需检查叔节点的颜色。根据叔节点的不同颜色，对应着不同的处理方式。

叔节点是红色

需要将父节点和叔叔节点都改为黑色，并且祖父节点改为红色。接着将祖父节点当成新插入的节点，重复这个过程，直至根节点(根节点不需要改为红色)。如下图。

叔节点是红色

叔节点是黑色

这种情况会复杂些，可将它归结为这四种可能的情形：

  • 左-左
    这种情形的父节点和新节点都位于左子节点。右旋转祖父节点 G，然后交换 G 和 P 的颜色可恢复平衡。如下图。

左-左情形

  • 左-右
    这种情形的父节点位于左子节点，新节点位于右子节点。先左旋转父节点 P，现在变成了上面“左-左”的情形，按照“左-左”的规则操作即可恢复平衡。如下图。

左-右情形

  • 右-右
    这是“左-左”的对称情形。父节点和新节点都位于右子节点。左旋转祖父节点 G，然后交换 G 和 P 的颜色可恢复平衡。如下图。

右-右情形

  • 右-左
    这是“左-右”的对称情形。父节点位于右子节点，新节点位于左自节点。先右旋转父节点 P，此时变成了上面“右-右”的情形，按照“右-右”的规则操作即可恢复平衡。如下图。

右-左情形

算法描述

假设 X 是新插入的节点，接下来总结插入节点算法的步骤：

  1. 执行标准的二叉查找树插入，并将新插入的节点的颜色设置为红色。
  2. 如果 X 是根节点，则将 X 的颜色更改为黑色。此时整棵树的黑色高度增加1。
  3. 如果 X 的父节点颜色是红色，并且 X 不是根节点：
    • X 的叔节点是红色
      (从红黑树第四个属性可知，祖父节点肯定是黑色的)
      1. 将父节点和叔节点的颜色改为黑色。
      2. 祖父节点的颜色改为红色。
      3. 把 X 的祖父 G 当成 X，重复步骤2和3。
    • X 的叔节点是黑色
      那么 X 的父节点 P 和祖父节点 G 可以有这四种组合情形(这一点类似于AVL树)
      1. 左-左情形：右旋转 G，交换 P 和 G 的颜色。
      2. 左-右情形：左旋转 P，变成“左左”情形继续处理。
      3. 右-右情形：“左左”的镜像；左旋转 G，交换 P 和 G 的颜色。
      4. 右-左情形：“左右”的镜像；右旋转 P，变成“右右”情形继续处理。

删除节点

红黑树删除节点是一个相当复杂的过程。在插入操作中，我们检查叔节点的颜色来决定恢复平衡操作的情形。而在删除操作中，我们检查兄弟节点的颜色来决定恢复平衡操作情形。

由红黑性质5可知，每个 None 节点的黑色高度是相同的。插入节点违反的主要属性是两个连续的红色节点。而在删除中，主要违反的属性是改变了子树中的黑色高度，可能会因为删除黑色节点而导致从根到叶路径中的黑色高度变小。

我们先来回顾标准二叉查找树的删除过程：

  1. 如果要删除的节点没有子节点，只需删除它并更新父节点。
  2. 如果要删除的节点只有一个子节点，则用其子节点替换它。
  3. 如果要删除的节点有两个子节点，那么用它的顺序继承者替它，可以是右子树中最左边的节点，也可以是左子树中最右边的节点。然后删除后继节点，后继节点最多只有一个子节点。

红黑树的删除过程首先执行标准二叉查找树删除节点的过程。最终删除的节点要么是叶子节点，要么只有一个子节点。因此，我们只需要处理节点是叶节点或只有一个子节点的情况。下图中，假设 V 是要删除的节点 (a)，U 是用来替换 V 的子节点。要注意的是 (b) 中，当 V 是叶节点时，U 是空的，空节点被当作是黑色。

删除节点

简单情形：U 或 V 是红色

由于 U 和 V 是父子关系，它们不能同时是红色。因此这时不管要删除的节点是红色还是黑色，只需要将作为替换的子节点标记为黑色即可，这条路径上的黑色节点高度最终并没有被改变。

U 或 V 是红色

简单情形：U 是根节点

一棵空的树也符合红黑树5个性质，删除过程结束。

复杂情形：U 和 V 都是黑色

为了更易于理解，我们引入双黑概念，当一个黑色节点被删除并被其黑色子节点替换时，这个用作替换的黑色子节点称为双黑。接下来的主要任务是将这个双黑的子节点转换为单黑。

删除 V 后，U 会变为双黑。下图中，如果 V 是叶节点，则 U 是 null，我们知道， null 的是黑色的。因此，删除一个黑色叶节点也会导致双黑。

删除黑色叶节点会出现双黑

我们的任务已被简化成将双黑变为单黑。根据兄弟节点和其子节点的颜色不同情况，对应着下面三种情形。

情形1. 兄弟节点是黑色，兄弟子节点至少有一个是红色

S 的红色子节点是 R。根据 S 和 R 的位置的不同，分为四种子情形：

  • 左-左
    如下图，兄弟节点 S 是左子节点，红色子节点 R 也是左子节点。删除 V 后 U 变双黑 (b)。对 S 右旋转，并将 R 改成黑色 (c)。

    左-左情形

  • 左-右
    如下图，兄弟节点 S 是左子节点，红色子节点 R 是右子节点。删除 V 后 U 变双黑 (b)。首先对 R 左旋转，并与 S 交换颜色 (c)。接着对 S 右旋转，并将 S 设为黑色 (d)。

    左-右情形

  • 右-右
    与“左-左”情形互为镜像。如下图，兄弟节点 S 是右子节点，红色子节点 R 也是右子节点。删除 V 后 U 变双黑 (b)。对 S 左旋转，并将 R 改成黑色 (c)。

    右-右情形

  • 右-左
    与“左-右”情形互为镜像。如下图，兄弟节点 S 是右子节点，红色子节点 R 是左子节点。删除 V 后 U 变双黑 (b)。首先对 R 右旋转，并与 S 交换颜色 (c)。接着对 S 左旋转，并将 S 设为黑色 (d)。

    右-左情形

💡 TIP
当 S 有两个红色子节点当情况下，对应哪种情形取决于选哪个子节点作为 R。

情形2. 兄弟节点是黑色，兄弟的子节点都是黑色

删除 V 后，U 变成双黑 (b)。首先将兄弟节点 S 变成红色。如果父节点 P 是红色，只需将 P 变成黑色即可。如果 P 是黑色，那么此时 P 便是双黑，需持续向上处理，直至根节点。如下图。

P 为黑色，持续向上处理

情形3. 兄弟节点是红色

先执行旋转，将兄弟节点向上提，并对新的父节点和旧的父节点重新着色。分为左右两个不同的子情形。

  • 左
    S 是左子节点。删除节点 V 后，将 P 向右旋转。转为情形1或情形2继续处理。如下图。

    左情形

  • 右
    S 是右子节点。删除节点 V 后，将 P 向左旋转。转到情形1或情形2继续处理。如下图。

    右情形

执行操作后，兄弟节点始终是黑色的，需要转为情形1或情形2继续处理。这取决于兄弟节点的子节点颜色，至少有一个红的转到情形1处理；全是黑的转到情形2处理。

代码实现

#include <iostream>
#include <queue>
using namespace std;

enum COLOR { RED, BLACK };

class Node {
public:
  int val;
  COLOR color;
  Node *left, *right, *parent;

  Node(int val) : val(val) {
    parent = left = right = NULL;

    // Node is created during insertion
    // Node is red at insertion
    color = RED;
  }

  // returns pointer to uncle
  Node *uncle() {
    // If no parent or grandparent, then no uncle
    if (parent == NULL or parent->parent == NULL)
      return NULL;

    if (parent->isOnLeft())
      // uncle on right
      return parent->parent->right;
    else
      // uncle on left
      return parent->parent->left;
  }

  // check if node is left child of parent
  bool isOnLeft() { return this == parent->left; }

  // returns pointer to sibling
  Node *sibling() {
    // sibling null if no parent
    if (parent == NULL)
      return NULL;

    if (isOnLeft())
      return parent->right;

    return parent->left;
  }

  // moves node down and moves given node in its place
  void moveDown(Node *nParent) {
    if (parent != NULL) {
      if (isOnLeft()) {
        parent->left = nParent;
      } else {
        parent->right = nParent;
      }
    }
    nParent->parent = parent;
    parent = nParent;
  }

  bool hasRedChild() {
    return (left != NULL and left->color == RED) or
           (right != NULL and right->color == RED);
  }
};

class RBTree {
  Node *root;

  // left rotates the given node
  void leftRotate(Node *x) {
    // new parent will be node's right child
    Node *nParent = x->right;

    // update root if current node is root
    if (x == root)
      root = nParent;

    x->moveDown(nParent);

    // connect x with new parent's left element
    x->right = nParent->left;
    // connect new parent's left element with node
    // if it is not null
    if (nParent->left != NULL)
      nParent->left->parent = x;

    // connect new parent with x
    nParent->left = x;
  }

  void rightRotate(Node *x) {
    // new parent will be node's left child
    Node *nParent = x->left;

    // update root if current node is root
    if (x == root)
      root = nParent;

    x->moveDown(nParent);

    // connect x with new parent's right element
    x->left = nParent->right;
    // connect new parent's right element with node
    // if it is not null
    if (nParent->right != NULL)
      nParent->right->parent = x;

    // connect new parent with x
    nParent->right = x;
  }

  void swapColors(Node *x1, Node *x2) {
    COLOR temp;
    temp = x1->color;
    x1->color = x2->color;
    x2->color = temp;
  }

  void swapValues(Node *u, Node *v) {
    int temp;
    temp = u->val;
    u->val = v->val;
    v->val = temp;
  }

  // fix red red at given node
  void fixRedRed(Node *x) {
    // if x is root color it black and return
    if (x == root) {
      x->color = BLACK;
      return;
    }

    // initialize parent, grandparent, uncle
    Node *parent = x->parent, *grandparent = parent->parent,
         *uncle = x->uncle();

    if (parent->color != BLACK) {
      if (uncle != NULL && uncle->color == RED) {
        // uncle red, perform recoloring and recurse
        parent->color = BLACK;
        uncle->color = BLACK;
        grandparent->color = RED;
        fixRedRed(grandparent);
      } else {
        // Else perform LR, LL, RL, RR
        if (parent->isOnLeft()) {
          if (x->isOnLeft()) {
            // for left right
            swapColors(parent, grandparent);
          } else {
            leftRotate(parent);
            swapColors(x, grandparent);
          }
          // for left left and left right
          rightRotate(grandparent);
        } else {
          if (x->isOnLeft()) {
            // for right left
            rightRotate(parent);
            swapColors(x, grandparent);
          } else {
            swapColors(parent, grandparent);
          }

          // for right right and right left
          leftRotate(grandparent);
        }
      }
    }
  }

  // find node that do not have a left child
  // in the subtree of the given node
  Node *successor(Node *x) {
    Node *temp = x;

    while (temp->left != NULL)
      temp = temp->left;

    return temp;
  }

  // find node that replaces a deleted node in BST
  Node *BSTreplace(Node *x) {
    // when node have 2 children
    if (x->left != NULL and x->right != NULL)
      return successor(x->right);

    // when leaf
    if (x->left == NULL and x->right == NULL)
      return NULL;

    // when single child
    if (x->left != NULL)
      return x->left;
    else
      return x->right;
  }

  // deletes the given node
  void deleteNode(Node *v) {
    Node *u = BSTreplace(v);

    // True when u and v are both black
    bool uvBlack = ((u == NULL or u->color == BLACK) and (v->color == BLACK));
    Node *parent = v->parent;

    if (u == NULL) {
      // u is NULL therefore v is leaf
      if (v == root) {
        // v is root, making root null
        root = NULL;
      } else {
        if (uvBlack) {
          // u and v both black
          // v is leaf, fix double black at v
          fixDoubleBlack(v);
        } else {
          // u or v is red
          if (v->sibling() != NULL)
            // sibling is not null, make it red"
            v->sibling()->color = RED;
        }

        // delete v from the tree
        if (v->isOnLeft()) {
          parent->left = NULL;
        } else {
          parent->right = NULL;
        }
      }
      delete v;
      return;
    }

    if (v->left == NULL or v->right == NULL) {
      // v has 1 child
      if (v == root) {
        // v is root, assign the value of u to v, and delete u
        v->val = u->val;
        v->left = v->right = NULL;
        delete u;
      } else {
        // Detach v from tree and move u up
        if (v->isOnLeft()) {
          parent->left = u;
        } else {
          parent->right = u;
        }
        delete v;
        u->parent = parent;
        if (uvBlack) {
          // u and v both black, fix double black at u
          fixDoubleBlack(u);
        } else {
          // u or v red, color u black
          u->color = BLACK;
        }
      }
      return;
    }

    // v has 2 children, swap values with successor and recurse
    swapValues(u, v);
    deleteNode(u);
  }

  void fixDoubleBlack(Node *x) {
    if (x == root)
      // Reached root
      return;

    Node *sibling = x->sibling(), *parent = x->parent;
    if (sibling == NULL) {
      // No sibling, double black pushed up
      fixDoubleBlack(parent);
    } else {
      if (sibling->color == RED) {
        // Sibling red
        parent->color = RED;
        sibling->color = BLACK;
        if (sibling->isOnLeft()) {
          // left case
          rightRotate(parent);
        } else {
          // right case
          leftRotate(parent);
        }
        fixDoubleBlack(x);
      } else {
        // Sibling black
        if (sibling->hasRedChild()) {
          // at least 1 red children
          if (sibling->left != NULL and sibling->left->color == RED) {
            if (sibling->isOnLeft()) {
              // left left
              sibling->left->color = sibling->color;
              sibling->color = parent->color;
              rightRotate(parent);
            } else {
              // right left
              sibling->left->color = parent->color;
              rightRotate(sibling);
              leftRotate(parent);
            }
          } else {
            if (sibling->isOnLeft()) {
              // left right
              sibling->right->color = parent->color;
              leftRotate(sibling);
              rightRotate(parent);
            } else {
              // right right
              sibling->right->color = sibling->color;
              sibling->color = parent->color;
              leftRotate(parent);
            }
          }
          parent->color = BLACK;
        } else {
          // 2 black children
          sibling->color = RED;
          if (parent->color == BLACK)
            fixDoubleBlack(parent);
          else
            parent->color = BLACK;
        }
      }
    }
  }

  // prints level order for given node
  void levelOrder(Node *x) {
    if (x == NULL)
      // return if node is null
      return;

    // queue for level order
    queue<Node *> q;
    Node *curr;

    // push x
    q.push(x);

    while (!q.empty()) {
      // while q is not empty
      // dequeue
      curr = q.front();
      q.pop();

      // print node value
      cout << curr->val << " ";

      // push children to queue
      if (curr->left != NULL)
        q.push(curr->left);
      if (curr->right != NULL)
        q.push(curr->right);
    }
  }

  // prints inorder recursively
  void inorder(Node *x) {
    if (x == NULL)
      return;
    inorder(x->left);
    cout << x->val << " ";
    inorder(x->right);
  }

public:
  // constructor
  // initialize root
  RBTree() { root = NULL; }

  Node *getRoot() { return root; }

  // searches for given value
  // if found returns the node (used for delete)
  // else returns the last node while traversing (used in insert)
  Node *search(int n) {
    Node *temp = root;
    while (temp != NULL) {
      if (n < temp->val) {
        if (temp->left == NULL)
          break;
        else
          temp = temp->left;
      } else if (n == temp->val) {
        break;
      } else {
        if (temp->right == NULL)
          break;
        else
          temp = temp->right;
      }
    }

    return temp;
  }

  // inserts the given value to tree
  void insert(int n) {
    Node *newNode = new Node(n);
    if (root == NULL) {
      // when root is null
      // simply insert value at root
      newNode->color = BLACK;
      root = newNode;
    } else {
      Node *temp = search(n);

      if (temp->val == n) {
        // return if value already exists
        return;
      }

      // if value is not found, search returns the node
      // where the value is to be inserted

      // connect new node to correct node
      newNode->parent = temp;

      if (n < temp->val)
        temp->left = newNode;
      else
        temp->right = newNode;

      // fix red red violation if exists
      fixRedRed(newNode);
    }
  }

  // utility function that deletes the node with given value
  void deleteByVal(int n) {
    if (root == NULL)
      // Tree is empty
      return;

    Node *v = search(n), *u;

    if (v->val != n) {
      cout << "No node found to delete with value:" << n << endl;
      return;
    }

    deleteNode(v);
  }

  // prints inorder of the tree
  void printInOrder() {
    cout << "Inorder: " << endl;
    if (root == NULL)
      cout << "Tree is empty" << endl;
    else
      inorder(root);
    cout << endl;
  }

  // prints level order of the tree
  void printLevelOrder() {
    cout << "Level order: " << endl;
    if (root == NULL)
      cout << "Tree is empty" << endl;
    else
      levelOrder(root);
    cout << endl;
  }
};

总结

相较于AVL树的高度平衡，红黑树舍弃了部分平衡性，换取在添加和删除节点时更少的旋转操作。红黑树中的删除操作平均需要$O(log n)$时间，这使得它成为在大型数据集中搜索和删除元素的好选择。在实践中，红黑树的整体性能优于AVL树。

红黑树在实践中有着广泛的应用。例如，Java 的 TreeMap、TreeSet 和 C++ STL 中的 set、map，它们的底层数据结构便是红黑树；自从 JDK1.8开始，HashMap 便引入了红黑树用来解决哈希冲突，当冲突的链表长度超过8时，会自动转为红黑树。还有 Nginx 的 Timer 管理以及 Linux 虚拟内存管理等等，都能看到它的应用。

一般来说，除非确信当下应用场景AVL树性能表现优于红黑树，否则优先选择红黑树。

版权声明： 本文为原创内容，未经许可，不得转载。