我们这里只实现红黑树的插入和删除，了解他们的底层即可，而后面我们在介绍 map 以及 set 的模拟实现的时候，我们就会进一步将红黑树进行改造！

Ⅱ. 红黑树的概念

红黑树是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是 Red 或 Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。（接近平衡不代表是平衡的，而 AVL 树则是严格平衡的）

Ⅲ. 红黑树的性质

每个结点不是红色就是黑色
根节点是黑色的
每个叶子结点都是黑色的 ( 此处的叶子结点指的是空结点 )
如果一个节点是红色的，则它的两个孩子结点是黑色的
对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点

❓ 思考：为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍？

💡 解答： 因为由性质三可以知道，红黑树没有连续的红色节点，且性质四中每条路径上包含相同数量的黑色节点。那么假设现在每条路径上有 n 个黑色节点，那么我们会发现：

1、如果不存在红色节点的话，那么这棵树的高度就是 $log_2 n$ 。

2、如果存在红色节点的话，且一黑一红布局的情况下，由于没有红色的连续节点，所以这棵树的高度就是 $log_2 2n$ 。所以可以看出红黑树的高度范围是【 $log_2 n$ ， $log_2 2n$ 】，所以其最长路径中节点个数不会超过最短路径节点个数的两倍！

Ⅳ. 红黑树的节点定义

enum Color
{
	BLACK,
	RED
};
 
template <class K, class V>
struct RBTreeNode
{
	RBTreeNode(const pair<K, V>& kv, Color col = RED)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _col(col)
	{}
 
	RBTreeNode<K, V>* _left; // 节点的左孩子
	RBTreeNode<K, V>* _right; // 节点的右孩子
	RBTreeNode<K, V>* _parent; // 节点的双亲(红黑树需要旋转，为了实现简单给出该字段)
	pair<K, V> _kv; // 节点的键值对
	Color _col; // 节点的颜色
};

后面我们在实现 map 和 set 的时候，我们会对节点定义进行一些改变，这些具体后面会讲！

❓ 思考：在节点的定义中，为什么要将节点的默认颜色给成红色的？

💡 解答：

这里插入黑色节点其实也是可以的，但是我们旋转插入颜色，是要根据具体情况，如果这里旋转插入黑色，那我们可能会违反性质四，也就是每条路径上黑色节点的数量，那么如果要调整的话，可能需要调节整棵树的路径的黑色节点，这就比较麻烦了！而如果我们旋转插入红色节点，那么我们可能违反的是性质三，也就是不能有连续红色节点，那么我们每次调整的时候其实只需要调整一棵子树之间的颜色即可，虽然最坏情况可能是要一直调整到根节点，但是相比于插入黑色节点的影响，插入红色节点是比较乐观的选择！

Ⅴ. 红黑树的结构

为了后续实现关联式容器简单，红黑树的实现中增加一个头结点，因为根节点必须为黑色，为了与根节点进行区分，将头结点给成黑色，并且让头结点的 pParent 域指向红黑树的根节点，pLeft 域指向红黑树中最小的节点，pRight 域指向红黑树中最大的节点！

但是我们后面模拟实现红黑树的时候是不带头节点的，其实都是一样的！

Ⅵ. 红黑树的插入Insert

红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：

按照二叉搜索树的规则插入新节点（这个去参考二叉搜索树中的解析）
检测新节点插入后，红黑树的性质是否造到破坏：

因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质（作为结束条件），则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论：

规则：cur 为当前节点，p 为父节点，g 为祖父节点，u 为叔叔节点（注意这里叔叔节点是关键！）

💅 **注意：**下面都已左为 p，右为 u 的情况举例子，而左为 u，右为 p 也是一样的只是方向改变了而已！

情况一： 该树为空树，直接插入根结点的位置，违反性质 1，把节点颜色有红改为黑即可。
情况二： 插入节点 cur 的父节点 p 为黑色，不违反任何性质，无需做任何修改
情况三： cur 为红，p 为红，g 为黑，u 存在且为红色
- 此时将 p 和 u 都变成黑色，将 g 变为红色，然后把 g 作为新的 cur，继续向上调整，直到出现 情况二 或者 p 不存在 的时候的时候结束。
情况四： cur 为红，p 为红，g 为黑，u 不存在 / u 为黑色，且 cur 为 p 的左子树
- 方法： 这种情况其实就是需要旋转来进行高度调节的情况了，很明显这是一个右单旋
- p 为 g 的左孩子， cur 为 p 的左孩子，则对 g 进行右单旋转；
- 相反，p 为 g 的右孩子， cur 为 p 的右孩子，则对 g 进行左单旋转
- p 、 g 变色 --> p 变黑， g 变红

情况五： cur 为红，p 为红，g 为黑，u 不存在/ u 为黑色，且 cur 为 p 的右子树
- 其实情况四和情况五都是属于同一种，只不过他们需要旋转的方式不太一样！
- p 为 g 的左孩子， cur 为 p 的右孩子，则针对 p 做左单旋转
- 相反，p 为 g 的右孩子， cur 为 p 的左孩子，则针对 p 做右单旋转，则转换成了情况四

🔺 注意： 在判断完所有的情况之后，要将根节点的颜色设为黑色，因为有些操作里面最后将根节点设为红色了，所以要改回来！

bool Insert(const pair<K, V>& kv)
{
    if (_root == nullptr)
    {
        _root = new Node(kv);
        _root->_col = BLOCK; // 记得将根节点的颜色变成黑色
        return true;
    }
 
    // 寻找要插入的位置
    Node* cur = _root;
    Node* parent = _root;
    while (cur)
    {
        if (cur->_kv.first > kv.first)
        {
            parent = cur;
            cur = cur->_left;
        }
        else if (cur->_kv.first < kv.first)
        {
            parent = cur;
            cur = cur->_right;
        }
        else
        {
            return false;
        }
    }
 
    // 插入新节点并将新节点的颜色设为红色
    cur = new Node(kv);
    cur->_col = RED;
    if (parent->_kv.first > kv.first)
    {
        parent->_left = cur;
        cur->_parent = parent;
    }
    else
    {
        parent->_right = cur;
        cur->_parent = parent;
    }
 
    // 控制平衡
    while (parent && parent->_col == RED) // 当parent不存在或者parent的颜色为黑则不需要调整了
    {
        Node* grandparent = parent->_parent;
 
        // 判断一下parent的位置
        if (grandparent->_left == parent)
        {
            Node* uncle = grandparent->_right;
            if (uncle && uncle->_col == RED) // uncle存在且为红色的情况
            {
                // 调整颜色
                parent->_col = uncle->_col = BLOCK;
                grandparent->_col = RED;
 
                // 继续向上调整
                cur = grandparent;
                parent = cur->_parent;
            }
            else // uncle不存在或者为黑色的情况
            {
                // 根据cur与parent的位置判断要如何旋转
                if (parent->_left == cur)
                {
                    // 右单旋
                    RotateR(grandparent);
 
                    // 调整颜色
                    grandparent->_col = RED;
                    parent->_col = BLOCK;
                }
                else
                {
                    // 先左单旋，然后右单旋
                    RotateL(parent);
                    RotateR(grandparent);
 
                    // 调整颜色
                    cur->_col = BLOCK;
                    grandparent->_col = RED;
                }
                break; // 旋转完即可break
            }
        }
        else
        {
            Node* uncle = grandparent->_left;
            if (uncle && uncle->_col == RED) // uncle存在且为红色的情况
            {
                // 调整颜色
                parent->_col = uncle->_col = BLOCK;
                grandparent->_col = RED;
 
                // 继续向上调整
                cur = grandparent;
                parent = cur->_parent;
            }
            else // uncle不存在或者为黑色的情况
            {
                // 根据cur与parent的位置判断要如何旋转
                if (parent->_left == cur)
                {
                    // 先右单旋，然后左单旋
                    RotateR(parent);
                    RotateL(grandparent);
 
                    // 调整颜色
                    cur->_col = BLOCK;
                    grandparent->_col = RED;
                }
                else
                {
                    // 左单旋
                    RotateL(grandparent);
 
                    // 调整颜色
                    parent->_col = BLOCK;
                    grandparent->_col = RED;
                }
                break; // 旋转完即可break
            }
        }
    }
    // 最后记得将根节点的颜色调为黑色
    _root->_col = BLOCK;
 
    return true;
}
 
// 具体的左右单旋参考AVL树中的讲解
void RotateL(Node* parent);
void RotateR(Node* parent);

Ⅶ. 红黑树的删除Erase

这里先粘几篇比较不错的博客：

红黑树

红黑树删除节点——这一篇就够了

红黑树删除详细图解，巨详细

红黑树原理以及插入、删除算法附图例说明

红黑树的删除和二叉搜索树类似，只不过需要加上颜色，经过变色和旋转满足红黑树的性质。

只不过红黑树的删除涉及了多种组合情况，其实分类出来的话也就六大种组合，一定要先有思路再去看代码，这样子不至于把自己绕晕！

红黑树中删除一个节点，遇到的各种情形就是其子节点的状态和颜色的组合，子节点状态共有3种：无子节点、有一个子节点、有两个子节点，颜色有红色和黑色两种，所以共会有6种组合。接下来我们逐一分析：

无子节点，删除节点可能为红色或者黑色。
- 如果为红色，直接进行删除即可。
- 如果为黑色，直接删除之后需要进行红黑树的平衡操作。（最复杂，涉及旋转，这个我们放到最后说）
有一个子节点：
- 删除的节点一定为黑色，子节点一定是红色（联系红黑树性质推测一下），只需要将子节点替换删除节点的位置，变黑即可。
有两个子节点：
- 与二叉搜索树一样，找到其后继节点放到要删除的节点的位置，然后将后继节点作为删除节点处理。

组合1：被删节点无子节点，且被删结点为红色

这种情况是比较好处理的，因为我们删除红色节点并不违反红黑树的性质，所以直接删除即可。

组合2：被删结点无子结点，且被删结点为黑色

这种情况是最复杂的，我们会将其发生的各种情况都列出来，作为新的子函数专门处理，但是注意的是子函数只负责用来旋转以及修改颜色，不删除节点，所以出了子函数后记得要手动删除一下！

else if (cur->_left == nullptr && cur->_right == nullptr) // 无叶子节点
{
    // 组合1：若被删节点为红色，则直接删除
    if (cur->_col == RED)
    {
        // 直接删除节点即可
        if (cur->_parent->_left == cur)
        {
            cur->_parent->_left = nullptr;
        }
        else
        {
            cur->_parent->_right = nullptr;
        }
        
        delete cur;
    }
    else // 组合2：被删节点为黑色，调用子函数专门去处理组合2（后面会讲）
    {
        Erase_balanceTwo(cur);
        
        if (cur->_parent->_left == cur)
        {
            cur->_parent->_left = nullptr;
        }
        else
        {
            cur->_parent->_right = nullptr;
        }
        
        delete cur;
    }
}

组合3：被删结点有一个子结点，且被删结点为红色（不存在）

这种情况是不存在的，因为如果被删节点是红色的话，则违反性质四；如果被删节点是黑色的话，则违反性质五！

组合4：被删结点有一个子结点，且被删结点为黑色

这种组合下，被删结点的子结点必然为红色，此时直接将被删节点删掉，用子节点代替被删节点的位置，并将子节点着黑即可。

else if (cur->_left == nullptr && cur->_right != nullptr) //左为空，右不为空
{
    Node* right = cur->_right;
    Node* parent = cur->_parent;
 
    right->_parent = parent;
    if (parent->_left == cur)
    {
        parent->_left = right;
    }
    else
    {
        parent->_right = right;
    }
    delete cur;
 
    // 最后将right的颜色改为黑色
    right->_col = BLACK;
}
else if (cur->_left != nullptr && cur->_right == nullptr) //左不为空，右为空
{
    Node* left = cur->_left;
    Node* parent = cur->_parent;
 
    left->_parent = parent;
    if (parent->_left == cur)
    {
        parent->_left = left;
    }
    else
    {
        parent->_right = left;
    }
    delete cur;
 
    // 最后将left的颜色改为黑色
    left->_col = BLACK;
}

组合5&6：被删结点有两个子结点，且被删结点为黑色或红色

首先，红黑树有两个子节点的删除和二叉搜索树方法是一样的，通过寻找前驱节点或者后继节点来继续替换删除，这里选择的是后继节点 替换删除！

当被删结点 node 有两个子结点时，我们先找到这个被删结点的后继结点 successor，然后用 successor 替换 node 的值，不用改变颜色，此时转换为删除 node 的后继节点 successor。

图a情况：
- 若successor为红色，则变成了组合1
- 若successor为黑色，则变成了组合2
图b情况：
- 若successor为红色，则变成了组合1（组合3是不可能的）
- 若successor为黑色，则变成了组合2或组合4

// 左右子树都存在的情况
 
// 先找到后继节点minRight
Node* minRight = cur->_right;
Node* minParent = cur;
while (minRight->_left)
{
    minParent = minRight;
    minRight = minRight->_left;
}
 
cur->_kv = minRight->_kv;
 
// 图b情况
if (cur == minParent)
{
    // 若为红色，则可直接删除该节点
    if (minRight->_col == RED)
    {
        delete minRight;
        minParent->_right = nullptr;
    }
    else // 若为黑色，则转化为组合2和组合4的问题
    {
        // 若存在右子树说明是组合4
        if (minRight->_right != nullptr)
        {
            // 将右子树替换掉被删节点，删掉被删节点
            Node* right = minRight->_right;
 
            right->_parent = minParent;
            minParent->_right = right;
            delete minRight;
 
            // 最后变色 
            right->_col = BLACK;
        }
        else // 若不存在右子树说明是组合2
        {
            Erase_balanceTwo(minRight);
            minParent->_right = nullptr;
            delete minRight;
        }
    }
}
else // 图a情况
{
    // 若为红色，则可直接删除该节点
    if (minRight->_col == RED)
    {
        delete minRight;
        minParent->_left = nullptr;
    }
    else // 若为黑色，则转化为组合2或组合4的问题
    {
        // 若存在右子树说明是组合4
        if (minRight->_right != nullptr)
        { 
            // 将右子树替换掉被删节点，删掉被删节点
            Node* right = minRight->_right;
 
            right->_parent = minParent;
            minParent->_left = right;
            delete minRight;
 
            // 最后变色 
            right->_col = BLACK;
        }
        else // 若不存在右子树说明是组合2
        {
            Erase_balanceTwo(minRight);
            minParent->_left = nullptr;
            delete minRight;
        }
    }
}

综上所述：组合5 6被转换为前面几种组合，我们真正要进行删除的只有组合1 2 4，对于组合 1 和 4，删除操作相当简单，这里不再多讲，接下来再逐一分析组合2可能的几种情形。

🔺 注意： 记得还要处理一下如果被删节点是 _root 的情况！

// 被删节点是_root
if (cur == _root)
{
    if (cur->_left == nullptr && cur->_right != nullptr)
    {
        _root = _root->_right;
        _root->_col = BLACK;
    }
    else if (cur->_right == nullptr && cur->_left != nullptr)
    {
        _root = _root->_left;
        _root->_col = BLACK;
    }
    else
    {
        _root = nullptr;
    }
    delete cur;
}

细谈组合2：被删结点无子结点，且被删结点为黑色

我们先来约定一个结果，就是上面组合 2 中，我们把黑色的叶子节点删掉后，这里我们用一个黑色的 null 节点来代替那个位置，方便我们后续情况的理解：

注意这里这个 `null` 只是我们假想出来方便我们理解情况的！

情形一：brother/uncle 为黑色，且 brother/uncle 有一个与其方向一致的红色子结点 son

所谓方向一致，是指 uncle 为 parent 的左子结点，son 也为 uncle 的左子结点；或者 uncle 为 parent 的右子结点，son 也为 uncle 的右子结点。

这里以 brother 为右子树为例：

图(c)中，白色代表随便是黑或是红，方形结点存储的是一个游离的黑色权值。将 brother 和 father 旋转（是左旋还是右旋自己根据情景体会，下同），并重新上色后，变成了图(d)，将游离的黑色权值扔掉，此时不违背任何红黑树的性质，删除操作完成。

图(c)中的情形颠倒过来，也是一样的操作。

解决方法：

左旋 brother （若 brother 为左子树则右旋）
将 son 变成黑色、brother 变成 father 的颜色、father 变成黑色

删除节点

if (parent->_left == cur) // uncle为parent右子树
{
    if ((uncle->_left && uncle->_left->_col == RED) || (uncle->_right && uncle->_right->_col == RED))
    {
        if (uncle->_right != nullptr) // 情形一
        {
            // 变色 + 
            uncle->_right->_col = BLACK;
            uncle->_col = parent->_col;
            parent->_col = BLACK;
            RotateL(parent);
        }
        // .....
    }
    // .....
}
else // uncle为parent左子树
{
    if ((uncle->_left && uncle->_left->_col == RED) || (uncle->_right && uncle->_right->_col == RED))
    {
        if (uncle->_left != nullptr) // 情形一
        {
            // 变色 + 右旋
            uncle->_left ->_col = BLACK;
            uncle->_col = parent->_col;
            parent->_col = BLACK;
            RotateR(parent);
        }
        // .....
    }
    // .....
}

情形二：brother/uncle 为黑色，且 brother/uncle 有一个与其方向不一致的红色子结点 son

这里以 brother 为右子树为例：

图(e)中，将 son 和 brother 旋转，重新上色后，变成了图(f)，转化为情形一。

图(e)中的情形颠倒过来，也是一样的操作。

解决方法：

右旋 brother（若 brother 为左子树则左旋）
交换 brother 与 son 的颜色

回到情形一（重新调用子函数即可）

if (parent->_left == cur) // uncle为parent右子树
{
    if ((uncle->_left && uncle->_left->_col == RED) || (uncle->_right && uncle->_right->_col == RED))
    {
        //.....
        
        else //情形二
        {
            uncle->_left->_col = BLACK;
            uncle->_col = RED;
            RotateR(uncle);
 
            Erase_balanceTwo(cur);
        }
    }
    //.....
}
else // uncle为parent左子树
{
    if ((uncle->_left && uncle->_left->_col == RED) || (uncle->_right && uncle->_right->_col == RED))
    {
        //..... 
        
        else // 情形二
        {
            uncle->_right->_col = BLACK;
            uncle->_col = RED;
            RotateL(uncle);
 
            Erase_balanceTwo(cur);
        }
    }
    //..... 
}

情形三：brother/uncle 为黑色，且 brother/uncle 无红色子结点

1、此时若 father 为红，则重新着色即可，删除操作完成。如图下图(g)和(h)

解决方法：

将 father 颜色变成黑色
将 brother 颜色变成红色

2、此时若 father 为黑，则重新着色，将游离的黑色权值存到 father（此时 father 的黑色权重为 2），将 father 作为新的结点进行情形判断，遇到情形一、情形二，则进行相应的调整，完成删除操作；如果没有，则结点一直上溯，直到根结点存储额外的黑色，此时将该额外的黑色扔掉，即完成了删除操作。

注意： 这里第二种情况有点不好理解，之所以要加一个游离的黑色是因为删除 node 后造成 node 子树和 brother 子树的黑节点个数不平衡，这里的操作实际是将 brother 子树中黑节点个数减少一个，而将 father 黑色权重设为 2，这样 father 左右两边的子树不用加游离的权值都是平衡的了。接下来将问题转移到了 father、father 的 father、father 的 brother 三个之间，这样向上递归，如果一直是这种情况，最终必定转化为 root 的左子节点或者右子节点权重为 2，同样的将 root 黑色权重设为 2，将另外一边的黑色权重减小 1，再将 root 的黑色权重扔掉一个，此时整棵树重回平衡，只是 root 到叶节点路径的黑节点少了一个。

解决方法：

将 brother 的颜色变成红色

以 father 为新的节点，继续调用子函数往上调整，直到遇到根节点或者遇到其他情况

//......
if(cur == _root)
    return;
 
if (parent->_col == RED)
{
    parent->_col = BLACK;
    uncle->_col = RED;
}
else
{
    uncle->_col = RED;
    Erase_balanceTwo(parent);
}

情形四：brother/uncle 为红色，则 parent/father 必为黑色。

这里以 brother 为右子树为例：

图(i)中，将 brother 和 father 旋转，重新上色后，变成了图(j)，新的 brother（原来的 son）变成了黑色，这样就成了情形一、二、三中的一种。如果将 son和 brother 旋转，无论怎么重新上色，都会破坏红黑树的性质4或5，例如图(k)。

图(i)中的情形颠倒过来，也是一样的操作。

解决方法：

对 father 左旋（若brother为左子树则对father右旋）
将 father 的颜色变成红色
将 brother 的颜色变成黑色

转化为其他三种情况去解决（重新调用子函数）

if (parent->_left == cur) // uncle为parent右子树
{
    Node* uncle = parent->_right;
    if (uncle->_col == RED) // 情形四
    {
        RotateL(parent);
        parent->_col = RED;
        uncle->_col = BLACK;
 
        Erase_balanceTwo(cur); // 对x重新执行这个过程，此时一定是情形一 二 三中的一种
    }
    //......
}
else // uncle为parent左子树
{
    Node* uncle = parent->_left;
    if (uncle->_col == RED) // 情形四
    {
        RotateR(parent);
        parent->_col = RED;
        uncle->_col = BLACK;
 
        Erase_balanceTwo(cur); // 对x重新执行这个过程，此时一定是情形一 二 三中的一种 
    }
    //......
}

🐰 删除的完整代码：

bool Erase(const K& key)
{
    if (_root == nullptr)
        return false;
 
    // 先找到要删除的节点
    Node* cur = _root;
    while (cur)
    {
        if (cur->_kv.first > key)
        {
            cur = cur->_left;
        }
        else if (cur->_kv.first < key)
        {
            cur = cur->_right;
        }
        else
        {
            // 找到了节点就开始删除
            if (cur->_left == nullptr || cur->_right == nullptr)
            {
                if (cur == _root)
                {
                    if (cur->_left == nullptr && cur->_right != nullptr)
                    {
                        _root = _root->_right;
                        _root->_col = BLACK;
                    }
                    else if (cur->_right == nullptr && cur->_left != nullptr)
                    {
                        _root = _root->_left;
                        _root->_col = BLACK;
                    }
                    else
                    {
                        _root = nullptr;
                    }
                    delete cur;
                }
                else if (cur->_left == nullptr && cur->_right != nullptr)
                {
                    Node* right = cur->_right;
                    Node* parent = cur->_parent;
 
                    right->_parent = parent;
                    if (parent->_left == cur)
                    {
                        parent->_left = right;
                    }
                    else
                    {
                        parent->_right = right;
                    }
                    delete cur;
 
                    // 最后将left的颜色改为黑色
                    right->_col = BLACK;
                }
                else if (cur->_left != nullptr && cur->_right == nullptr)
                {
                    Node* left = cur->_left;
                    Node* parent = cur->_parent;
 
                    left->_parent = parent;
                    if (parent->_left == cur)
                    {
                        parent->_left = left;
                    }
                    else
                    {
                        parent->_right = left;
                    }
                    delete cur;
 
                    // 最后将left的颜色改为黑色
                    left->_col = BLACK;
                }
                else if (cur->_left == nullptr && cur->_right == nullptr) // 无叶子节点
                {
                    if (cur->_col == RED)
                    {
                        // 直接删除节点即可
                        if (cur->_parent->_left == cur)
                        {
                            cur->_parent->_left = nullptr;
                        }
                        else
                        {
                            cur->_parent->_right = nullptr;
                        }
                    }
                    else
                    {
                        Erase_balanceTwo(cur);
                        if (cur->_parent->_left == cur)
                        {
                            cur->_parent->_left = nullptr;
                        }
                        else
                        {
                            cur->_parent->_right = nullptr;
                        }
                    }
                    delete cur;
                }
            }
            else // 左右子树都存在的情况
            {
                Node* minRight = cur->_right;
                Node* minParent = cur;
                while (minRight->_left)
                {
                    minParent = minRight;
                    minRight = minRight->_left;
                }
 
                cur->_kv = minRight->_kv;
 
                if (cur == minParent)
                {
                    // 若为红色，则可直接删除该节点
                    if (minRight->_col == RED)
                    {
                        delete minRight;
                        minParent->_right = nullptr;
                    }
                    else // 若为黑色，则转化为组合2和组合4的问题
                    {
                        if (minRight->_right != nullptr)
                        {
                            Node* right = minRight->_right;
 
                            right->_parent = minParent;
                            minParent->_right = right;
                            delete minRight;
 
                            // 最后变色 
                            right->_col = BLACK;
                        }
                        else
                        {
                            Erase_balanceTwo(minRight);
                            minParent->_right = nullptr;
                            delete minRight;
                        }
                    }
                }
                else
                {
                    // 若为红色，则可直接删除该节点
                    if (minRight->_col == RED)
                    {
                        delete minRight;
                        minParent->_left = nullptr;
                    }
                    else // 若为黑色，则转化为组合2或组合4的问题
                    {
                        if (minRight->_right != nullptr)
                        {
                            Node* right = minRight->_right;
 
                            right->_parent = minParent;
                            minParent->_left = right;
                            delete minRight;
 
                            // 最后变色 
                            right->_col = BLACK;
                        }
                        else
                        {
                            Erase_balanceTwo(minRight);
                            minParent->_left = nullptr;
                            delete minRight;
                        }
                    }
                }
            }
            return true;
        }
    }
    return false;
}
 
// 处理情况二的函数
void Erase_balanceTwo(Node* cur)
{
    if (cur == _root)
        return;
 
    Node* parent = cur->_parent;
    if (parent->_left == cur) // uncle为parent右子树
    {
        Node* uncle = parent->_right;
        if (uncle->_col == RED)
        {
            RotateL(parent);
            parent->_col = RED;
            uncle->_col = BLACK;
 
            Erase_balanceTwo(cur); // 对x重新执行这个过程，此时一定是情形一 二 三中的一种
        }
        else
        {
            if ((uncle->_left && uncle->_left->_col == RED) || 
                (uncle->_right && uncle->_right->_col == RED))
            {
                if (uncle->_right != nullptr)
                {
                    uncle->_right->_col = BLACK;
                    uncle->_col = parent->_col;
                    parent->_col = BLACK;
                    RotateL(parent);
                }
                else
                {
                    uncle->_left->_col = BLACK;
                    uncle->_col = RED;
                    RotateR(uncle);
 
                    Erase_balanceTwo(cur);
                }
            }
            else
            {
                if (cur == _root)
                    return;
 
                if (parent->_col == RED)
                {
                    parent->_col = BLACK;
                    uncle->_col = RED;
                }
                else
                {
                    uncle->_col = RED;
                    Erase_balanceTwo(parent);
                }
            }
        }
    }
    else // uncle为parent左子树
    {
        Node* uncle = parent->_left;
        if (uncle->_col == RED)
        {
            RotateR(parent);
            parent->_col = RED;
            uncle->_col = BLACK;
 
            Erase_balanceTwo(cur); // 对x重新执行这个过程，此时一定是情形一 二 三中的一种 
        }
        else
        {
            if ((uncle->_left && uncle->_left->_col == RED) || 
                (uncle->_right && uncle->_right->_col == RED))
            {
                if (uncle->_left != nullptr)
                {
                    uncle->_left ->_col = BLACK;
                    uncle->_col = parent->_col;
                    parent->_col = BLACK;
                    RotateR(parent);
                }
                else
                {
                    uncle->_right->_col = BLACK;
                    uncle->_col = RED;
                    RotateL(uncle);
 
                    Erase_balanceTwo(cur);
                }
            }
            else
            {
                if (parent->_col == RED)
                {
                    parent->_col = BLACK;
                    uncle->_col = RED;
                }
                else
                {
                    uncle->_col = RED;
                    Erase_balanceTwo(parent);
                }
            }
        }
    }
}

Ⅷ. 红黑树的验证

红黑树的检测分为两步：

检测其是否满足二叉搜索树(中序遍历是否为有序序列)
检测其是否满足红黑树的性质

bool _CheckBlance(Node* root, int blackNum, int count)
{
    // 走到nullptr之后，判断count和blackNum是否相等
    if (root == nullptr)
    {
        if (count != blackNum)
        {
            cout << "黑色节点的数量不相等" << endl;
            return false;
        }
 
        return true;
    }
 
    // 检测当前节点与其双亲是否都为红色
    if (root->_col == RED && root->_parent->_col == RED)
    {
        cout << "存在连续的红色节点" << endl;
        return false;
    }
 
    // 统计黑色节点的个数
    if (root->_col == BLACK)
    {
        count++;
    }
 
    return _CheckBlance(root->_left, blackNum, count)
        && _CheckBlance(root->_right, blackNum, count);
}
 
bool CheckBlance()
{
    // 空树也是红黑树
    if (_root == nullptr)
    {
        return true;
    }
 
    // 检测根节点是否满足情况
    if (_root->_col == RED)
    {
        cout << "根节点是红色的" << endl;
        return false;
    }
 
    // 获取任意一条路径中黑色节点的个数
    int blackNum = 0;
    Node* left = _root;
    while (left)
    {
        if (left->_col == BLACK)
        {
            blackNum++;
        }
 
        left = left->_left;
    }
 
    // 检测是否满足红黑树的性质，count用来记录路径中黑色节点的个数
    int count = 0;
    return _CheckBlance(_root, blackNum, count);
}

Ⅸ. AVL树和红黑树的比较

红黑树和 AVL 树都是高效的平衡二叉树，增删改查的时间复杂度都是 O( $log_2 n$ ) ，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的 2 倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比 AVL 树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。

红黑树

Ⅱ. 红黑树的概念

Ⅲ. 红黑树的性质

Ⅳ. 红黑树的节点定义

Ⅴ. 红黑树的结构

Ⅵ. 红黑树的插入Insert

Ⅶ. 红黑树的删除Erase

组合1：被删节点无子节点，且被删结点为红色

组合2：被删结点无子结点，且被删结点为黑色

组合3：被删结点有一个子结点，且被删结点为红色（不存在）

组合4：被删结点有一个子结点，且被删结点为黑色

组合5&6：被删结点有两个子结点，且被删结点为黑色或红色

细谈组合2：被删结点无子结点，且被删结点为黑色

注意这里这个 `null` 只是我们假想出来方便我们理解情况的！

情形一：brother/uncle 为黑色，且 brother/uncle 有一个与其方向一致的红色子结点 son

情形二：brother/uncle 为黑色，且 brother/uncle 有一个与其方向不一致的红色子结点 son

情形三：brother/uncle 为黑色，且 brother/uncle 无红色子结点

情形四：brother/uncle 为红色，则 parent/father 必为黑色。

解决方法：

🐰 删除的完整代码：

Ⅷ. 红黑树的验证

Ⅸ. AVL树和红黑树的比较

相关文章

线性表

跳表

Ⅰ. 最小生成树

评论 (0)

红黑树

Ⅱ. 红黑树的概念

Ⅲ. 红黑树的性质

Ⅳ. 红黑树的节点定义

Ⅴ. 红黑树的结构

Ⅵ. 红黑树的插入Insert

Ⅶ. 红黑树的删除Erase

组合1：被删节点无子节点，且被删结点为红色

组合2：被删结点无子结点，且被删结点为黑色

组合3：被删结点有一个子结点，且被删结点为红色（不存在）

组合4：被删结点有一个子结点，且被删结点为黑色

组合5&6：被删结点有两个子结点，且被删结点为黑色或红色

细谈组合2：被删结点无子结点，且被删结点为黑色

注意这里这个 null 只是我们假想出来方便我们理解情况的！

情形一：brother/uncle 为黑色，且 brother/uncle 有一个与其方向一致的红色子结点 son

情形二：brother/uncle 为黑色，且 brother/uncle 有一个与其方向不一致的红色子结点 son

情形三：brother/uncle 为黑色，且 brother/uncle 无红色子结点

情形四：brother/uncle 为红色，则 parent/father 必为黑色。

解决方法：

🐰 删除的完整代码：

Ⅷ. 红黑树的验证

Ⅸ. AVL树和红黑树的比较

相关文章

线性表

跳表

Ⅰ. 最小生成树

评论 (0)

注意这里这个 `null` 只是我们假想出来方便我们理解情况的！