查看: 126|回复: 0

二叉树(4)红黑树

[复制链接]
发表于 2020-2-18 10:28:29 | 显示全部楼层 |阅读模式
封装基于 BinaryTreeOperations 的 红黑树(一种自平衡的二叉查找树)。
除了提供 BinaryTreeOperations 中的部门基础接口外,增加按键的插入 和 按键或节点指针的删除操作。
在阅读本文前,您应该先相识二叉树中的旋转是怎么回事(相干文章许多且简朴,笔者不再赘述)。

讲解红黑树的教程许多,但是许多讲解并不敷以让读者清楚的学会红黑树,尤其是删除操作,许多教程十分凌乱,因此本文将使用清晰的层次分类及必要的图进行讲解。

一、节点界说:
  1. enum class Color :bool { RED = 0, BLACK };struct Node{    _Ty key;    Node* left = nullptr;    Node* right = nullptr;    Node* parent = nullptr;    Color color = Color::RED;    Node(const _Ty& _key) :key(_key) {}};
复制代码

二、红黑树的规则:
  ① 每个节点是红色大概黑色。
  ② 根节点是黑色。
  ③ 每个叶子节点是黑色(注意:这里的叶子节点指 为空的叶子节点)。
  ④ 假如一个节点是红色,则它的孩子必须是黑色(大概说支路上不得出现连续的红节点)。
  ⑤ 从任意节点到其叶子节点的全部路径中,所包罗的黑色节点数类似(叶子节点同样指为空的节点)。
  请务必尽快纯熟的记住以上规则(尤其是 ②,④,⑤),尽管这看似复杂,但在应用中正是由于这些特性会使得红黑树没这么难。

  红黑树的增删操作分为两步:
    ① 按二叉查找树的规则将节点插入到相干位置或删除相干节点。
    ② 讨论各种环境,若红黑树失衡则采取相干方法进行调解使之重新恢复平衡。


三、插入操作(令插入的节点为 cur,cur 的父节点为 par,par 的兄弟节点为 uncle,par 的父节点为 gpa):
  如嵌套 if else 一样,我们将插入环境分为两类(称为外层分类),再根据这两类的 子环境 进行其他分类(称为内层分类)。
  注意,新插入节点 cur 肯定是红色(由于这不会违背规则 ⑤,只有可能违背规则 ① ④,违背 ① 时轻易处理,即插入空树时只需将其变为黑色即可)。
    为何宁愿违背 ① ④ 而不宁愿违只背 ⑤(即新插节点是黑色)?(你可以明确为这会更轻易实现自平衡,不用过于纠结)。
    插入空树环境比较简朴,后文不特地说明该环境。
  ① 外层分类分为:par 是黑色 或 par 是红色。
  ② 内层分类是在 par 是红色 的环境下分类的,这在稍后进行讲解。
  现在先解决 ①:
    1) par 是黑色时,直接插入即可(这不会冲破平衡)。
    2)par 是红色(冲破规则 ④),进入 ②。(注:此时 gpa 肯定是黑色,看规则 ④)。
  现在解决 ② (分为 uncle 是红色 或 uncle 是黑色):
    1)如图 uncle 是红色时(空的黑色节点没有画出):
    

      如图进行变色后将 cur 指向 gpa 的节点,继续实行 1)。
      直到 cur 是红色且为根节点时,直接将根节点变黑即可。大概出现 新的 uncle 是黑色 时进入背面的环境。
    2)uncle 是黑色时分为四类环境(不用担心,原理都一样,分为两类也可以的,这里也可以类似 AVL 树四种旋转环境)该环境调解后便已经平衡,可直接返回。
      ① 直接看图,图中给出 par 是左孩子的两种环境(仅看图你可能觉得为何右支多一个黑色?那假如 uncle 是空呢(所以请注意规则③)):
      

        图上P1,以 gpa 右旋(看!是不是类似 AVL 树的 左左_右旋!),并交换 par 和 gpa 的颜色(小的两类环境是:cur 是左孩子还是右孩子)。
        图下P2,先将 gpa 的左孩子左旋,在将 gpa 右旋(看!是不是类似 AVL 树的 左右_左右旋!),然后交换 cur 和 gpa 的颜色。
      ② 接下来,par 是右孩子的两种环境(小的两类环境同样看 cur 是左孩子还是右孩子)。
        由于 ② 与 ① 是左右对称的环境,因此交给读者自行思索(用 AVL 树的旋转方法类似的话是:右右_左旋 和 右左_右左旋),不需要笔者继续画图了吧!

   至此,插入操作竣事!总结......就不用了吧。接下去是删除操作,环境许多,坐稳扶好!!!(不用慌,笔者会以清晰的层次进行分类说明)。


四、删除操作(令待删除节点为 cur,cur 的父亲为 par,cur 的兄弟为 bro,bro 的左孩子为 LC,右孩子为 RC):

  在进行分类解决前,根据红黑树的规则,我们需要知道一些隐藏的特性,正如前文所说,正是由于这些隐藏特性,会使得红黑树变得稍微简朴。
  以下以 隐藏特性 命名:
    ① 红节点要么没有孩子,要么有两个孩子,不存在只有一个孩子的环境。
    ② 黑节点只有一个孩子时,该孩子肯定是红色,且该孩子无孩子。
    说明:①:若红节点只有一个孩子,孩子为红则违背规则 ④,孩子为黑则违背规则 ⑤(无需图也能明确吧)。

  现在对删除环境进行分类:
    一、cur 是红色。
    二、cur 是黑色。
    三、子环境是在 ② 的条件下分类的,这在稍后进行讲解。

  现在解决 一(此时 cur 不可能是根,看规则 ②):
    ① 根据隐藏规则 cur 要么无孩子,要么只有一个孩子。
    ② cur 无孩子时直接删除即可,这不会冲破平衡。
    ③ cur 有两个孩子时,用后继节点(或前驱)节点,然后调用函数自身删除后继(或前驱)节点。

    注:③ 时,函数自身只会额外调用一次,由于 后继(或前驱)节点不可能有两个孩子。
      另外,后继(或前驱)代替 cur 时,只代替 cur 的键,而不改变它们的颜色。

  现在解决 二(cur 是黑色):
    ① cur 有两个孩子:同 一中的 ③ 环境,找后继(或前驱)代替。
    ② cur 只有一个孩子:根据隐藏规则 ②,只需将红孩子的键替换 cur 的键,然后删除红孩子即可(同样不更改它们的颜色)。
    

    ③ cur 没有孩子:删除 cur,则 par 在 cur 的支路会少一个黑节点,因此需要通过调解使得红黑树重归于平衡,这是重点讨论的。

    现在,红黑树的删除只剩下 ③,即 cur 是黑色 且 cur 无孩子,在分类进步行简朴分析。
    已经知道,删除了 cur,则 par 在 cur 的支路会少一个黑节点,因此我们需要向 bro 所在的支路 “借” 一个红节点一补充 par 在 cur 支路缺少的黑节点。
    如何 “借”?若无法 “借” 又该怎么办?“借” 到了又该怎么处理?这就是接下来分类讨论的环境。

    因此 对于 cur 是黑色且无孩子的环境分为以下几类:
      ① bro 是红色。
      ② bro 是黑色但 bro 的孩子有红色(分为左孩子是红色或右孩子是红色,实际上都为红)。
      ③ bro 是黑色但 par 是红色。
      ④ bro 是黑色,par 也是黑色(可知 bro 肯定无孩子,看规则 ⑤)。

    现在解决这些环境即可(现在假设 cur 是左孩子,若是右孩子,则于此左右对称,交予读者自行思索(笔者代码中用 bool 变量 isLeft 来进行统一处理))。

    解决 ①:直接看图:
    

     cur 是被删除的节点,因此 cur 不参与调解。
     将 par 左旋(若 cur 是右孩子则是 右旋,后序不特地夸大 cur 是右孩子的环境),然后将 bro 重新指向 LC 即可。
     这时 你可能发现 par 左子树黑节点任然少一个,并未平衡,怎么办?这个时候 满意环境 ③,因此交给背面的环境处理即可。


    解决 ②:LC 大概 RC 是红色的环境在下图统一给出(注意 cur 是左孩子,右孩子时应该怎么做自行观察):
    

    紫色代表节点任意色。
    看 P1:RC 是红色,则左旋 bro,然后将 bro 变为 par 的颜色,然后将 par 和 RC 变黑色即可。
    看 P2:LC 是红色,按图中方法将 LC 上提,将 LC 变为 par 的颜色,再将 par 变黑色即可。图示调解已经平衡可直接退出。

    注:bro 孩子有一个红色,则另一个肯定是红色大概空(黑色)(看规则 ⑤)。

    解决 ③:par 是红色时:
    

    由于排除了 ② 环境,则 bro 的孩子肯定为黑色(而且肯定是空,看规则 ⑤),因此交换 par 和 bro 的颜色即可平衡。

    解决 ④:par 是黑,且 bro 是黑(bro 肯定无孩子,由于排除了 ② 环境,且看规则 ⑤):
    

    由于此时无法借到红孩子,因此让 bro 变红,此时 par 左右子树平衡,但是!!!!
    但是 par 的 父亲在 par 支路上的黑节点少了!因此借红孩儿的事情交给 par 处理,即 cur 指向 par,bro 指向 par 的兄弟,par 指向 par 得父亲,继续回溯即可。
    注意:若 par 没有父亲了怎么办(即 par 是根节点)? 那不就太好了吗,省得回溯了,直接退出就可以了呀(所以写代码注意此环境!)!!!

  至此,红黑树插入、删除环境讲解完,最后给出 c++ 代码。

测试代码 main.cpp:
  1. #include #include "RBTree.h"using std::cout;using std::endl;int main(){    RBTree rbt;    auto il = { 12,1,9,2,0,11,7,19,4,15,18,5,14,13,10,16,6,3,8,17 };    cout parent->parent->left : cur->parent->parent->right;        if (uncle != nullptr && uncle->color == Color::RED)        {            cur->parent->color = Color::BLACK;            uncle->color = Color::BLACK;            cur->parent->parent->color = Color::RED;            cur = cur->parent->parent;        }        else        {            if (parIsRight)            {                if (cur == cur->parent->left) cur = BTO::rightRotate(cur->parent)->right;                cur = BTO::leftRotate(cur->parent->parent);                cur->left->color = Color::RED;                cur->color = Color::BLACK;            }            else            {                if (cur == cur->parent->right) cur = BTO::leftRotate(cur->parent)->left;                cur = BTO::rightRotate(cur->parent->parent);                cur->right->color = Color::RED;                cur->color = Color::BLACK;            }            if (cur->parent == nullptr) root = cur;            return;        }    }    root->color = Color::BLACK;}templatebool RBTree::erase(const _Ty& _key){    bool succeed = false;    Node* del = BTO::find(root, _key);    if (del != nullptr)    {        erase(del);        succeed = true;    }    return succeed;}templatevoid RBTree::erase(Node* _node){    if (_node == nullptr) return;    --size_n;    if (_node->color == Color::RED)    {        if (_node->left == nullptr && _node->right == nullptr)        {            if (_node == _node->parent->left) _node->parent->left = nullptr;            else _node->parent->right = nullptr;            delete _node;        }        else        {            auto del = BTO::findMinimum(_node->right);            _node->key = del->key;            ++size_n;            erase(del);        }    }    else    {        if (_node->right == nullptr && _node->left == nullptr)        {            Node* par = _node->parent;            if (par == nullptr)            {                delete root;                root = nullptr;                return;            }            bool isLeft = _node == par->left ? true : false;            isLeft ? par->left = nullptr : par->right = nullptr;            delete _node;            while (true)            {                Node* bro = isLeft ? par->right : par->left;                if (bro->color == Color::RED)                {                    isLeft ? BTO::leftRotate(par) : BTO::rightRotate(par);                    par->color = Color::RED;                    bro->color = Color::BLACK;                    if (bro->parent == nullptr) root = bro;                    bro = isLeft ? par->right : par->left;                }                if (bro->color == Color::BLACK)                {                    if ((isLeft ? bro->left : bro->right) != nullptr && (isLeft ? bro->left : bro->right)->color == Color::RED)                    {                        Node* temp = isLeft ? bro->left : bro->right;                        isLeft ? bro->left = nullptr : bro->right = nullptr;                        isLeft ? par->right = nullptr : par->left = nullptr;                        isLeft ? temp->right = bro : temp->left = bro;                        bro->parent = temp;                        if (par == par->parent->left) par->parent->left = temp;                        else par->parent->right = temp;                        temp->parent = par->parent;                        isLeft ? temp->left = par : temp->right = par;                        par->parent = temp;                        temp->color = par->color;                        par->color = Color::BLACK;                        return;                    }                    else if ((isLeft ? bro->right : bro->left) != nullptr && (isLeft ? bro->right : bro->left)->color == Color::RED)                    {                        Node* temp = isLeft ? bro->right : bro->left;                        isLeft ? BTO::leftRotate(par) : BTO::rightRotate(par);                        bro->color = par->color;                        par->color = Color::BLACK;                        temp->color = Color::BLACK;                        return;                    }                    else if (par->color == Color::RED)                    {                        par->color = Color::BLACK;                        bro->color = Color::RED;                        return;                    }                    else                    {                        bro->color = Color::RED;                        if (par->parent != nullptr) isLeft = par == par->parent->left ? true : false;                        else return;                        par = par->parent;                    }                }            }        }        else if (!(_node->right != nullptr && _node->left != nullptr))        {            if (_node->right != nullptr)            {                Node* del = _node->right;                _node->key = del->key;                _node->right = nullptr;                delete del;            }            else            {                Node* del = _node->left;                _node->key = del->key;                _node->left = nullptr;                delete del;            }        }        else        {            auto del = BTO::findMinimum(_node->right);            _node->key = del->key;            ++size_n;            erase(del);        }    }}#endif // !__RBTREE_H__
复制代码

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?用户注册

x

天涯海角也要找到Ni:二叉树(4)红黑树

中发现Ni: 二叉树(4)红黑树
中发现Ni: 二叉树(4)红黑树
中发现Ni: 二叉树(4)红黑树
中发现Ni: 二叉树(4)红黑树
中发现Ni: 二叉树(4)红黑树
中发现Ni: 二叉树(4)红黑树
相关技术服务需求,请联系管理员和客服QQ:2753533861或QQ:619920289
您需要登录后才可以回帖 登录 | 用户注册

本版积分规则

帖子推荐:
客服咨询

QQ:2753533861

服务时间 9:00-22:00

快速回复 返回顶部 返回列表