备案控制台
开发者社区 云计算 文章 正文

Rbtree的删除

2022-11-29 60
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 无

@[TOC]

前言：

  • 博主收集的资料New Young，连载中。
  • 博主收录的问题:New Young
  • 转载请标明出处：New Young
  • 本文的RBTree是有问题的，向祖先寻求帮助时，uncle为红色的情况代码不会实现，留给以后吧！

红黑树的构成规则

红黑是在二叉搜索树的基础上，添加一些规则的一种高效的数据结构

  1. 根节点是黑色
这里的根节点是整体这个树的根，不是左右子树的根
  1. 我们空节点是黑色的，称为NIL节点
  2. 如果一个节点是红色的，那么它的左右孩子必须是黑色的
特别的，左右孩子是2个NIL节点也可以
  1. 从根到每一个==NILL==节点的所有路径中，黑色节点个数必须一样
  • 记住路径最终的尽头是NIL节点，这个是解决红黑树删除的关键。
  • 该规则保证了，红黑树中最长路径不超过最短路径的2倍。

    证明:

    设所有路径中，相同的黑色节点个数为N。

    最短路径可能是：全部是黑色节点

    由规则3，一但路径中出现红色节点，那么它的下一个节点必然是黑色的。

    最坏的情况是：==一红一黑==交叉出现，那么N个黑色节点，最多这条路径上是2*N-1个节点。

    因此说：==红黑树中最长路径不超过最短路径的2倍==

红黑树的删除

虽然看到删除，你可能会认为删除后的修复情况非常多，其实可能是你对RBTree的规则未理解好的原因，RBTree的删除情况的修复其实不多，那么让我们开始学习它！

关键

  1. 直到NIL才算是路径，因此在每种情形中一定要保证到NIL的黑色节点数不变。这种保证，==可以通过不用的红色节点变成黑色节点辅助，也可以通过让树的2端同时减少相同的黑色节点，整体是缺失，就借助树的祖先==，重复上述黄色字体过程。
  2. **默认用替代法中的向左找最大值分析问题**
  3. 节点的释放时机要提前，否则通过祖先的帮助平衡RBTree的循环就会出问题如野指针问题，逻辑问题

思路

由删除使用的替代法可以知道，如果我们找到了那个替代节点X，那么X一定==至少有一个孩子是NIL节点==，如果不是这样，说明我们未正确找到替代节点。

接上面。

情形一：如果X是红色的，

由规则3,4它的左右孩子一定都为NIL节点。

处理方式：直接删除即可，红色节点不影响路径中黑色节点个数

在这里插入图片描述

情形二：X是黑色的

由规则3,4，它一定存在uncle，否则左右子树的NIL的黑色节点不平衡。至于uncle什么颜色，分析即可

（1）它如果X存在孩子，那一定是一个没有孩子的红色节点。

处理：删除X，让红色孩子变黑。
在这里插入图片描述

（2）X没有孩子，删除X后，左子树缺失一个黑色节点。那么我们可以尝试能否借助uncle中的红色节点，通过旋转，让左子树这边多一黑色节点，左右子树仍是平衡。

  1. uncle是红色的，那么它的父亲一定是黑色的，且一定存在2个黑色的左右孩子，且左右孩子没有孩子。

    处理：uncle在右边，uncle右旋后，父亲左旋，交换uncel和UR的颜色

    uncle在左边，uncle左旋后，父亲右旋，交换uncel和UL的颜色

在这里插入图片描述

  1. uncle是黑色时，由规则3,4，如果uncle存在孩子一定为红色。通过旋转让红色节点上来。

    • 存在红色孩子时

处理：

本质上是让红色节点代替父亲节点，让父亲节点变成黑色节点就可以达到左右树黑色节点平衡。

uncle在右边时

  1. 红色孩子在左边，uncle向右旋，parent左旋，UL着父亲颜色，父亲变黑。
  2. 红色孩子在右边，parent左旋，uncle着父亲颜色，父亲变黑，UR变黑

uncle在左边时

红色孩子在左边，parent右旋，uncke着父亲颜色，父亲变黑，UL变黑

  1. 红色孩子在右边，uncle左旋，uncle右旋，UR着父亲颜色，父亲变黑

在这里插入图片描述

  • 不存在孩子时---是最复杂的情形。
1. 此时无论什么方式，都不能通过uncle来让左右子树平衡，父亲也不行，因此我们==只能让uncle边红，让左右勉强达到平衡，但是整个树仍是缺失一个黑色节点==，因此我们要向祖先寻求帮助，通过祖先的红色节点边黑色节点，来辅助平衡。这种通过祖先帮助，最坏到root，但是因为我们让uncle变红了，我们让root这个树整体所有路径都少一个黑色节点，整体还是平衡的。

​

在这里插入图片描述

节点释放的时机！！！！

最后一种树整体缺失x个黑色节点的情形，如果父亲仍是黑色，我们仍按照上述情形处理就会出问题，因此我们在进入循环前就要释放节点X，这个释放只有一次，之后对X的孩子进行分析。

这样情形就如下：----可能描述的不是很清楚，需要自己看博主的代码逻辑才能很好理解。

情形一：如果孩子为红

孩子变黑即可

情形二：孩子为空且X为红

这个要在进入循环前就处理，因为可能通过祖先节点的方式，平衡RBTree。

情形三：孩子为空且X为黑或者孩子为黑

  1. uncle为黑且存在红色节点

    通过双旋或者单旋

  2. uncle为空或者uncel为黑且uncke没有节点

    uncle变红，进入下一层循环

  3. uncle为红，

    父亲进行单旋

X为红代码

if (cur->_color == RED)
            {
                //如果为红色，那么左右孩子一定为空
                Node* parent = cur->_parent;
                if (parent)
                {

                    if (parent->_left == cur)
                    {
                        parent->_left = nullptr;
                    }
                    else
                    {
                        parent->_right = nullptr;
                    }
                }
                else
                {
                    cout << "该树不是红黑树" << endl;
                    assert(false);
                }
                delete cur;
                return true;
            }

x为黑代码

if (cur->_color == BLOCK)
                //如果cur存在孩子，那它一定为红，且红色孩子没有左右孩子
                //父亲可能存在，可能不存在
            {
                //要提前保证删除cur
                Node* parent = cur->_parent;
                Node* child = cur->_left;
                if(cur->_right)
                    child = cur->_right;
                if (parent)
                {
                    if (parent->_left == cur)
                    {
                        parent->_left = child;
                    }
                    else
                    {
                        parent->_right = child;
                    }
                }
                else//说明删除的是根
                {
                    if (child)//child存在就置黑
                    {
                        child->_color = BLOCK;
                    }
                    _root = child;
                    delete cur;
                    return true;
                }
                delete cur;//删除节点
                cur = nullptr;
                while (parent)
                {
                    //第一次的parent不可能为空,为空程序是不会走到这里
                    //因为可能出现借助祖先节点的情况，
                    //child可红或者黑
                    if (child&&child->_color==RED)
                        //存在为红,直接将child变为黑色，
                              //不影响路径黑色节点个数
                    {
                        child->_color = BLOCK;
                        break;
                    }
                    else  if(child==nullptr||(child && child->_color == BLOCK))
                        //child为nullptr或者child为黑，就看uncle了
                    {
                        //uncle一定存在，否则删除前就不是红黑树,因为如果不存在，
                        // 则删除那边的的路径上就多一个黑色节点
                        //1. uncle为红，uncle与父亲交换颜色，父亲变为黑色
                        //2. uncle为黑,
                        // 那么它要么没孩子节点，这时候直接将uncle变为黑色，通过祖先节点，再找一个黑色节点
                        // 要么它只能有一红色孩子节点，通过单旋/双旋将红色节点旋转到缺失的一边，变为黑色即可
                        //   
                        Node* uncle = parent->_right;
                        if (child== parent->_right)
                            uncle = parent->_left;
                        if (uncle)
                        {
                            Node* UL = uncle->_left;
                            Node* UR = uncle->_right;
                            if (uncle == parent->_right)
                            {
                                if (uncle->_color == BLOCK)
                                {
                                    if (UL && UL->_color == RED)
                                    {
                                        _reloveR(uncle);
                                        _reloveL(parent);
                                        UL->_color = parent->_color;
                                        parent->_color = BLOCK;
                                        break;
                                    }
                                    else if (UR && UR->_color == RED)
                                    {
                                        _reloveL(parent);
                                        uncle->_color = parent->_color;
                                        parent->_color = BLOCK;
                                        UR->_color = BLOCK;
                                        break;
                                    }
                                    else
                                    {
                                        uncle->_color = RED;
                                        child = parent;
                                        parent = parent->_parent;
                                    }
                                }
                                else
                                    //uncle为红色，父亲一定为黑，那么它必定有2个黑色孩子
                                    ///双旋，之后交换uncle和UL的颜色
                                {
                                    _reloveR(uncle);
                                    _reloveL(parent);
                                swap(uncle->_color, UR->_color);
                                    break;

                                }

                            }
                            else if (uncle == parent->_left)
                            {

                                if (uncle->_color == BLOCK)
                                {

                                    if (UL && UL->_color == RED)
                                    {
                                        _reloveR(parent);
                                        uncle->_color = parent->_color;
                                        parent->_color = BLOCK;
                                        UL->_color = BLOCK;
                                        break;
                                    }
                                    else if (UR && UR->_color == RED)
                                    {
                                        _reloveL(uncle);
                                        _reloveR(parent);
                                        UR->_color = parent->_color;
                                        parent->_color = BLOCK;
                                        break;
                                    }
                                    else
                                    {
                                        uncle->_color = RED;
                                        child = parent;
                                        parent = parent->_parent;
                                    }
                                }
                                else
                                    //uncle为红色，则父亲一定为黑色，那么它必定有2个黑色孩子
                                //双旋，之后交换uncle和UL的颜色
                                {
                                    _reloveL(uncle);
                                    _reloveR(parent);
                                swap(uncle->_color, UL->_color);
                                    break;

                                }
                            }
                        }
                        //uncle不可能不存在
                        //
                        else{
                            assert(false);
                        }
                    }
                    else
                    {
                    assert(false);
                    }

                }
            }

Swap代码

    void Swap(Node* root1, Node* root2)
    {
        assert(root1);
        assert(root2);
        //root1默认是要删除的节点，且root2的左右孩子必定为空
        Node* parent1 = root1->_parent;
        Node* parent2 = root2->_parent;
        if (parent1)
        {
            //先处理父亲节点
            if (root1 == parent1->_left)
            {
                parent1->_left = root2;
            }
            else
            {
                parent1->_right = root2;
            }
        }
        else
        {
            _root = root2;
        }

        if (root2 == parent2->_left)
        {
            parent2->_left = root1;
        }
        else
        {
            parent2->_right = root1;
        }
        std::swap(root1->_parent, root2->_parent);
        std::swap(root1->_left, root2->_left);
        //交换后root1的左孩子为空
        //调整左右孩子指向
        if (root2->_left)
            root2->_left->_parent = root2;
        std::swap(root1->_right, root2->_right);
        //交换后root1的右孩子为空
        //调整左右孩子指向
        if (root2->_right)
            root2->_right->_parent = root2;
        //交
        std::swap(root1->_color, root2->_color);
    }

全部代码

bool Erase(const T&data)
    {
        //定位节点
        Node* cur = _root;
        while (cur)
        {
            if (kot()(cur->_data) > kot()(data))
            {
                cur = cur->_left;
            }
            else if (kot()(cur->_data) < kot()(data))
            {
                cur = cur->_right;
            }
            else
            {
                break;
            }
        }
        if (cur == nullptr)
        {
            cout << "RBT中不存在以" << kot()(data) << "为key的节点" << endl;
            return false;
        }
        else
        {
            Node* del = cur;
            //替代法
            //那边存在，就向那边替代
            if (cur->_right)
            {
                //向右找最小
                Node* min = cur->_right;//max一定存在且不为空
                while (min->_left)
                {
                    min = min->_left;
                }
                this->Swap(cur, min);
            }
            else if (cur->_left)
            {
                //向左找最大
                Node* max = cur->_left;//max一定存在且不为空
                while (max->_right)
                {
                    max = max->_right;
                }
                this->Swap(cur, max);
            }
            else//当成无孩子的节点，正常走流程
            {
                ;
                
            }
            //定位的节点，至少有一边为nullptr
            //走到这里说明，cur一定存在孩子节点且一定存在父亲节点

            //情形一：
            //红色，一定有父亲节点，否则就不为红色，
            //父亲节点一定为黑，因此只需要链接好与父亲节点即可
            if (cur->_color == RED)
            {
                //如果为红色，那么左右孩子一定为空
                Node* parent = cur->_parent;
                if (parent)
                {

                    if (parent->_left == cur)
                    {
                        parent->_left = nullptr;
                    }
                    else
                    {
                        parent->_right = nullptr;
                    }
                }
                else
                {
                    cout << "该树不是红黑树" << endl;
                    assert(false);
                }
                delete cur;
                return true;
            }
            else if (cur->_color == BLOCK)
                //如果cur存在孩子，那它一定为红，且红色孩子没有左右孩子
                //父亲可能存在，可能不存在
            {
                //要提前保证删除cur
                Node* parent = cur->_parent;
                Node* child = cur->_left;
                if(cur->_right)
                    child = cur->_right;
                if (parent)
                {
                    if (parent->_left == cur)
                    {
                        parent->_left = child;
                    }
                    else
                    {
                        parent->_right = child;
                    }
                }
                else//说明删除的是根
                {
                    if (child)//child存在就置黑
                    {
                        child->_color = BLOCK;
                    }
                    _root = child;
                    delete cur;
                    return true;
                }
                delete cur;//删除节点
                cur = nullptr;
                while (parent)
                {
                    //第一次的parent不可能为空,为空程序是不会走到这里
                    //因为可能出现借助祖先节点的情况，
                    //child可红或者黑
                    if (child&&child->_color==RED)
                        //存在为红,直接将child变为黑色，
                              //不影响路径黑色节点个数
                    {
                        child->_color = BLOCK;
                        break;
                    }
                    else  if(child==nullptr||(child && child->_color == BLOCK))
                        //child为nullptr或者child为黑，就看uncle了
                    {
                        //uncle一定存在，否则删除前就不是红黑树,因为如果不存在，
                        // 则删除那边的的路径上就多一个黑色节点
                        //1. uncle为红，uncle与父亲交换颜色，父亲变为黑色
                        //2. uncle为黑,
                        // 那么它要么没孩子节点，这时候直接将uncle变为黑色，通过祖先节点，再找一个黑色节点
                        // 要么它只能有一红色孩子节点，通过单旋/双旋将红色节点旋转到缺失的一边，变为黑色即可
                        //   
                        Node* uncle = parent->_right;
                        if (child== parent->_right)
                            uncle = parent->_left;
                        if (uncle)
                        {
                            Node* UL = uncle->_left;
                            Node* UR = uncle->_right;
                            if (uncle == parent->_right)
                            {
                                if (uncle->_color == BLOCK)
                                {
                                    if (UL && UL->_color == RED)
                                    {
                                        _reloveR(uncle);
                                        _reloveL(parent);
                                        UL->_color = parent->_color;
                                        parent->_color = BLOCK;
                                        break;
                                    }
                                    else if (UR && UR->_color == RED)
                                    {
                                        _reloveL(parent);
                                        uncle->_color = parent->_color;
                                        parent->_color = BLOCK;
                                        UR->_color = BLOCK;
                                        break;
                                    }
                                    else
                                    {
                                        uncle->_color = RED;
                                        child = parent;
                                        parent = parent->_parent;
                                    }
                                }
                                else
                                    //uncle为红色，父亲一定为黑，那么它必定有2个黑色孩子
                                    ///双旋，之后交换uncle和UL的颜色
                                {
                                    _reloveR(uncle);
                                    _reloveL(parent);
                                swap(uncle->_color, UR->_color);
                                    break;

                                }

                            }
                            else if (uncle == parent->_left)
                            {

                                if (uncle->_color == BLOCK)
                                {

                                    if (UL && UL->_color == RED)
                                    {
                                        _reloveR(parent);
                                        uncle->_color = parent->_color;
                                        parent->_color = BLOCK;
                                        UL->_color = BLOCK;
                                        break;
                                    }
                                    else if (UR && UR->_color == RED)
                                    {
                                        _reloveL(uncle);
                                        _reloveR(parent);
                                        UR->_color = parent->_color;
                                        parent->_color = BLOCK;
                                        break;
                                    }
                                    else
                                    {
                                        uncle->_color = RED;
                                        child = parent;
                                        parent = parent->_parent;
                                    }
                                }
                                else
                                    //uncle为红色，则父亲一定为黑色，那么它必定有2个黑色孩子
                                //双旋，之后交换uncle和UL的颜色
                                {
                                    _reloveL(uncle);
                                    _reloveR(parent);
                                swap(uncle->_color, UL->_color);
                                    break;

                                }
                            }
                        }
                        //uncle不可能不存在
                        //
                        else{
                            assert(false);
                        }
                    }
                    else
                    {
                    assert(false);
                    }

                }
            }    
            return true;
        }    
    }

随机插入测试

void MapT()
    {
        srand(time(0));
        int N = 15;//截图有限
        vector<int> v;
        for (int i = 0; i < N; ++i)
        {
            v.push_back(rand() % 20);
        }
        NY::Map<int, int > map;
        for (auto e : v)
        {
            map.Insert(make_pair(e,e));
        }
        if (map.IsRBTree())
            cout << "True" << endl;
        else
            cout << "False" << endl;
        for (int i = 0; i < N; ++i)
        {
            cout << "删除 ("<<v[i]<<v[i]<<")前:" ;

            map.Inorder();
            cout << endl;
            map.Erase(v[i]);
            cout << "删除后:";
            map.Inorder();
            cout << endl;
            cout << "##################################" << endl;
        }
    }

在这里插入图片描述

总结

如果熟悉了红黑树的规则，细致分析就不用担心红黑色的删除的情形。AVl的删除也是。
工作中一般更多的是关注RBTree的删除思想

游客myapyvipxlqt4
目录
相关文章
行十万里人生
|
2天前
红黑树（RBTree）认识总结
红黑树（RBTree）认识总结
行十万里人生
6 0
草帽lufei
|
1月前
Node 使用递归实现遍历所有文件
Node 使用递归实现遍历所有文件
草帽lufei
47 0
高彬滔
双链表全部知识总结（初始化、插入、删除、遍历）
双链表知识总结包括思路分析、代码实现
高彬滔
196 0
程序媛三妹ya
LeetCode 237. 删除链表中的节点 Delete Node in a Linked List
LeetCode 237. 删除链表中的节点 Delete Node in a Linked List
程序媛三妹ya
73 0
羽林君
|
安全 容器
别被vector最后一个元素erase错误
别被vector最后一个元素erase错误
羽林君
137 0
别被vector最后一个元素erase错误
程序媛三妹ya
|
算法
LeetCode 19. 删除链表的倒数第N个节点 Remove Nth Node From End of List
LeetCode 19. 删除链表的倒数第N个节点 Remove Nth Node From End of List
程序媛三妹ya
62 0
把苹果咬哭的测试笔记
|
存储 算法 Java
【小白学算法】6.单链表的修改、删除
【小白学算法】6.单链表的修改、删除
把苹果咬哭的测试笔记
132 0
【小白学算法】6.单链表的修改、删除
AI浩
|
C++ 容器
C++ 如何正确使用erase删除list中的元素。
C++ 如何正确使用erase删除list中的元素。
AI浩
261 0
爱写Bug
|
Java Python
LeetCode 19：删除链表的倒数第N个节点 Remove Nth Node From End of List
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。 Given a linked list, remove the n-th node from the end of list and return its head. 示例： 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后，链表变为 1->2->3->5. 说明： 给定的 n 保证是有效的。
爱写Bug
856 0
soul.stone
红黑树rbtree
红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。
soul.stone
1106 0