数据结构算法 - 红黑树

红黑树是一棵自平衡的二叉搜索树，因此在学习红黑树之前，我们需要回顾一下之前所学的知识二叉搜索树和平衡二叉树。

1.二叉搜索树

二叉搜索树又叫二叉查找树或者二叉排序树，它首先是一个二叉树，而且必须满足下面的条件：

1）若左子树不空，则左子树上所有结点的值均小于它的根节点的值；

2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值

3）左、右子树也分别为二叉搜索树

二叉搜索树示例

2.平衡二叉树

二叉搜索树解决了许多问题，比如可以快速的查找最大值和最小值，可以快速找到排名第几位的值，快速排序等等。但普通的二叉搜索树有可能出现极不平衡的情况（斜树），这样我们的时间复杂度就有可能退化成 O(N) 的情况。比如我们现在插入的数据是 [1,2,3,4,5,6,7] 转换为二叉树如下：

斜树

由于普通的二叉搜索树会出现极不平衡的情况，那么我们就必须得想想办法了，这个时候平衡二叉树就能帮到我们了。什么是平衡二叉树？平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

平衡二叉树有一个很重要的性质：左右两个子树的高度差的绝对值不超过1。那么解决方案就是如果二叉树的左右高度超过 1 ，我们就把当前树调整为一棵平衡二叉树。这就涉及到左旋、右旋、先右旋再左旋、先左旋再右旋。

2.1 右旋：

右旋.png

   TreeNode<K, V> *R_Rotation(TreeNode<K, V> *pNode) {
        TreeNode<K, V> *left = pNode->left;
        TreeNode<K, V> *right = left->right;
        left->right = pNode;
        pNode->left = right;
        // 重新调整高度
        pNode->height = max(getHeight(pNode->left), getHeight(pNode->right)) + 1;
        left->height = max(getHeight(left->left), getHeight(left->right)) + 1;
        return left;
    }

2.2 左旋：

左旋

  TreeNode<K, V> *L_Rotation(TreeNode<K, V> *pNode) {
        TreeNode<K, V> *right = pNode->right;
        TreeNode<K, V> *left = right->left;
        right->left = pNode;
        pNode->right = left;
        // 重新调整高度
        pNode->height = max(getHeight(pNode->left), getHeight(pNode->right)) + 1;
        right->height = max(getHeight(right->left), getHeight(right->right)) + 1;
        return right;
    }

2.3 先右旋再左旋：

先右旋再左旋

  TreeNode<K, V> *R_L_Rotation(TreeNode<K, V> *pNode) {
    pNode->right = R_Rotation(pNode->right);
    return L_Rotation(pNode);
  }

2.4 先左旋再右旋：

先左旋再右旋

  TreeNode<K, V> *L_R_Rotation(TreeNode<K, V> *pNode) {
    pNode->left = L_Rotation(pNode->left);
    return R_Rotation(pNode);
  }

2.红黑树

红黑树用法就比较广了，比如 JDK 1.8 的 HashMap，TreeMap，C++ 中的 map 和 multimap 等等。红黑树学习起来还是有一点难度的，这时如果我们心中有 B 树就有助于理解它，如果没有 B 树也没有关系。

红黑树的特性:
（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
（4）如果一个节点是红色的，则它的子节点必须是黑色的。
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

红黑树

假设我们现在要插入一个新的节点，如过插入的这个新的节点为黑色，那么必然会违反性质(5)，所以我们把新插入的点定义为红色的。但是如果插入的新节点为红色，就可以能会违反性质(4) ，因此我们需要对其进行调整，使得整棵树依然满足红黑树的性质，也就是双红修正。接下来我们只要分情况分析就可以了：

1. 如果没有出现双红现象，父亲是黑色的不需要修正；
2. 叔叔是红色的 ，将叔叔和父亲黑，然后爷爷染红；
3. 叔叔是黑色的，父亲是爷爷的左节点，且当前节点是其父节点的右孩子，将“父节点”作为“新的当前节点”，以“新的当前节点”为支点进行左旋。然后将“父节点”设为“黑色”，将“祖父节点”设为“红色”，以“祖父节点”为支点进行右旋；
4. 叔叔是黑色的，父亲是爷爷的左节点，且当前节点是其父节点的左孩子，将“父节点”设为“黑色”，将“祖父节点”设为“红色”，以“祖父节点”为支点进行右旋；
5. 叔叔是黑色的，父亲是爷爷的右节点，且当前节点是其父节点的左孩子，将“父节点”作为“新的当前节点”，以“新的当前节点”为支点进行右旋。然后将“父节点”设为“黑色”，将“祖父节点”设为“红色”，以“祖父节点”为支点进行左旋；
6. 叔叔是黑色的，父亲是爷爷的右节点，且当前节点是其父节点的右孩子，将“父节点”设为“黑色”，将“祖父节点”设为“红色”，以“祖父节点”为支点进行左旋；

上面的双红修正现象看似比较负责，但实际上只有三种情况，一种是没有双红现象，另一种是父亲和叔叔都是红色的，最后一种是叔叔是黑色的。我们来画个实例看下：

template<class K, class V>
void map<K, V>::solveDoubleRedTree(RB_Node *pNode) {
    RB_Node *node = pNode;
    // 不是根节点，父亲是红色
    while (node->parent && node->parent->color == RB_COLOR_RED) { // 情况1
        // 需要判断的亲戚
        RB_Node *parent = node->parent;
        RB_Node *uncle = brother(parent);
        RB_Node *grandfather = parent->parent;

        // 叔叔是红色
        if (getColor(uncle)) { // 情况2
            // 父亲和叔叔染黑，爷爷染红
            grandfather->color = RB_COLOR_RED;
            parent->color = RB_COLOR_BLACK;
            uncle->color = RB_COLOR_BLACK;
            // 继续递归
            node = grandfather;
        } else {
            // 叔叔是黑色的，且父亲是爷爷的左儿子
            if (parent == grandfather->left) {
                // 自己是父亲的左儿子
                if (parent->right == node) {// 情况3
                    grandfather->color = RB_COLOR_RED;
                    node->color = RB_COLOR_BLACK;
                    node = parent;
                    L_Rotation(parent);
                    R_Rotation(grandfather);
                } else { // 情况4
                    grandfather->color = RB_COLOR_RED;
                    parent->color = RB_COLOR_BLACK;
                    R_Rotation(grandfather);
                }
            } else {
                // 自己是父亲的右儿子
                if (parent->left == node) {// 情况5
                    grandfather->color = RB_COLOR_RED;
                    node->color = RB_COLOR_BLACK;
                    node = parent;
                    R_Rotation(parent);
                    L_Rotation(grandfather);
                } else { // 情况6
                    grandfather->color = RB_COLOR_RED;
                    parent->color = RB_COLOR_BLACK;
                    L_Rotation(grandfather);
                }
            }
        }
    }
    // 根节点必须要是黑色的
    root->color = RB_COLOR_BLACK;
}