【C++进阶5-红黑树】噩梦般的存在?手提AVLTree暴揍红黑树!

这篇具有很好参考价值的文章主要介绍了【C++进阶5-红黑树】噩梦般的存在?手提AVLTree暴揍红黑树!。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

今天,带来无数人的噩梦——红黑树的讲解。文中不足错漏之处望请斧正!

如果还没看过AVLTree讲解的一定要去看看,看完才能更好理解红黑树!


是什么

红黑树是自平衡的二叉搜索树。

红黑树的规则:

  1. 每个结点非黑即红
    1. 根结点为黑
    2. 叶子结点为黑(此处的叶子结点指空结点)
  2. 不能有连续的红结点,但可以有连续的黑结点
  3. 每条简单路径上的黑结点数量相同

满足以上规则,就能保证最长路径不超过最短路径的二倍,保持了一种相对宽松的平衡。


实现

*为了降低学习成本,部分细节先略过,等封装map和set再添上。

结构

enum Color
{
    RED, BLACK
};

template<class K, class V>
struct RBTreeNode
{
    pair<K, V> _kv;
    RBTreeNode<K, V>* _left;
    RBTreeNode<K, V>* _right;
    RBTreeNode<K, V>* _parent;
    Color _clr;
    
    RBTreeNode(const pair<K, V>& kv)
    :_left(nullptr),
    _right(nullptr),
    _parent(nullptr),
    _kv(kv),
    _clr(RED)
    {}
};

template<class K, class V>
class RBTree
{
    typedef RBTreeNode<K, V> Node;
public:
		...
private:
		Node* _root = nullptr;
};

结点默认红色?往后看。

Insert

实现思路

BST插入总是找位置+插入,插入后只要保持红黑树的规则不被打破就可以。

新插入的结点设为什么颜色?

设为黑色:必然打破“黑结点数量相同”的规则。

设为红色:可能打破“不能有连续的红节点”的规则。(如果父亲是黑,就不会打破规则)

那自然设为红色。

我们要维持的规则主要就是上面两条。

注:

  • 称新插入的结点为cur
  • 称cur的父结点为parent
  • 称parent除cur外的另一孩子为uncle
  • 称parent的父结点为grandParent

插入新结点cur后:

  1. parent为黑:不打破规则,插入结束
  2. parent为红:打破规则,调整
    1. uncle为红:直接着色
    2. uncle不存在/为黑:旋转+着色

为什么根据uncle就能判断?

若插入后需要调整:

  1. parent必然为红
  2. grandParent必然为黑(不能有连续的红结点)

既然cur、parent、grandParent都确定了,那我们只用根据u来分类即可。

  1. uncle为红
  2. uncle不存在
  3. uncle为黑

情况1:u为红(抽象图)

u为红,直接改色。

【C++进阶5-红黑树】噩梦般的存在?手提AVLTree暴揍红黑树!

  1. cur为红,parent为红打破了“不能有连续红节点”,所以p必须变黑
  2. parent变黑,到parent的简单路径上都增加了一个黑节点,因为“每条简单路径上黑节点数量相同”,所以到uncle的简单路径上也需要多一个黑节点
  3. 我们还需要考虑g是子树还是根
    1. 若是子树,变红没毛病,但g变红可能向上影响(如果g的parent是红,就打破“不能有连续红结点的规则”),所以我们需要把g当做新一轮的cur继续往后看是否需要调整
    2. 若是根,需要重新变黑(根结点必须是黑色)

【C++进阶5-红黑树】噩梦般的存在?手提AVLTree暴揍红黑树!

u为红直接变色:p变黑、u变黑、g变红

  1. 当g为根→g变黑
  2. 当g不为根→g作新cur往上走
  3. 当p为黑就停(最差走到默认为黑的根结点)

情况2:u不存在

u不存在,单旋+变色。

u不存在,则cur一定是新增。因为u不存在,就代表右边没有黑,那左边也没有黑:p为红,cur也为红,且没有其他黑,那么cur一定是新增。

【C++进阶5-红黑树】噩梦般的存在?手提AVLTree暴揍红黑树!

  • p是g的左孩子 = 左高 = 右单旋+变色(g变红,p变黑)
  • p是g的右孩子 = 右高 = 左单旋+变色(g变红,p变黑)
  • 旋转后不向上影响,调整结束

情况3:u为黑,整体过高

*有了AVLTree的积累,我们这就只讲一种单旋,另一种同理,反过来而已

【C++进阶5-红黑树】噩梦般的存在?手提AVLTree暴揍红黑树!

  • p是g的左孩子、cur是p的左孩子 = 整体左高 = 右单旋+变色(g变红,p变黑)
  • p是g的右孩子、cur是p的右孩子 = 整体右高 = 左单旋+变色(g变红,p变黑)
  • 旋转后不向上影响(不会导致和上面出现连续的红节点,被旋转的部分也没有徒增给节点),调整结束

情况4:u为黑,整体过高且局部过高

【C++进阶5-红黑树】噩梦般的存在?手提AVLTree暴揍红黑树!

  • p是g的左,cur是p的右 = 高左中右高 = 先对p左单旋,再对g右单旋,最后变色(cur变黑、g变红)
  • p是g的右,cur是p的左 = 高右中左高 = 先对p右单旋,再对g左单旋,最后变色(cur变黑、g变红)
  • 旋转后不向上影响,调整结束

旋转总结

到这里我们发现情况2、3、4有些相似之处,所以我们可以进一步分类:

  1. 种类1:
    1. u为红——直接变色并向上调整
  2. 种类2:
    1. u不存在/u为黑且规则高——单旋+变色解决
    2. u为黑且不规则高——双旋+变色解决

最后,我们要推理一个结论来圆满RBTree调平衡的合理性:种类2一定是由种类1变化而来的。

【C++进阶5-红黑树】噩梦般的存在?手提AVLTree暴揍红黑树!

依照这个结论:种类1通过变色后向上调整,要么直接解决问题,要么演变为种类2,而种类2旋转后必然能解决问题,那么红黑树的调整我们也就必然解决干净了。

调整参考代码

while (parent && parent->_clr == RED) {
    Node *grandParent = parent->_parent;

    if(parent == grandParent->_left) {
        Node *uncle = grandParent->_right;
        //种类1: 直接变色
        if (uncle && uncle->_clr == RED) {
            parent->_clr = uncle->_clr = BLACK;
            grandParent->_clr = RED;

            cur = grandParent;
            parent = cur->_parent;
        } else { //种类2: 旋转+变色
            if(cur == parent->_left) { //整体过高: 单旋
                rotateR(grandParent);
                parent->_clr = BLACK;
                grandParent->_clr = RED;
            } else { //整体过高+局部过高: 双旋
                rotateL(parent);
                rotateR(grandParent);
                cur->_clr = BLACK;
                grandParent->_clr = RED;
            }
            break; //旋转后不再向上影响,结束调整
        }
    } else { //相反而已
        Node *uncle = grandParent->_left;

        if (uncle && uncle->_clr == RED) {
            parent->_clr = uncle->_clr = BLACK;
            grandParent->_clr = RED;

            cur = grandParent;
            parent = cur->_parent;
        } else {
            if(cur == parent->_right) {
                rotateL(grandParent);
                parent->_clr = BLACK;
                grandParent->_clr = RED;
            } else {
                rotateR(parent);
                rotateL(grandParent);
                cur->_clr = BLACK;
                grandParent->_clr = RED;
            }
            break;
        }
    }
}

旋转参考代码

	void rotateL(Node *parent) {
        Node *subR = parent->_right;
        Node *subRL = subR->_left;
        Node *grandParent = parent->_parent;

        //1. subRL变成parent的右子树
        parent->_right = subRL;
        if (subRL) subRL->_parent = parent;

        //2. parent变成subR的左子树
        subR->_left = parent;
        parent->_parent = subR;

        //3. subR变成局部根或整体根
        if (grandParent == nullptr) { //整体根
            _root = subR;
            _root->_parent = nullptr;
        } else { //局部根
            subR->_parent = grandParent;
            if (parent == grandParent->_left) grandParent->_left = subR;
            if (parent == grandParent->_right) grandParent->_right = subR;
        }
    }

    void rotateR(Node *parent) {
        Node *subL = parent->_left;
        Node *subLR = subL->_right;
        Node *grandParent = parent->_parent;

        //1. subLR变成parent的左
        parent->_left = subLR;
        if (subLR) subLR->_parent = parent;

        //2. parent变成subL的右
        subL->_right = parent;
        parent->_parent = subL;

        //3. subL变成局部根或整体根
        if (grandParent == nullptr) { //整体根
            _root = subL;
            _root->_parent = nullptr;
        } else { //局部根
            subL->_parent = grandParent;
            if (parent == grandParent->_left) grandParent->_left = subL;
            if (parent == grandParent->_right) grandParent->_right = subL;
        }
    }

Insert参考代码

	bool insert(const pair <K, V> &kv) {
        if (_root == nullptr) {
            _root = new Node(kv, BLACK); //根节点必须是黑的
            return true;
        }

        //1. 找位置
        Node *cur = _root;
        Node *parent = nullptr;
        while (cur) {
            parent = cur;
            if (kv.first < cur->_kv.first) {
                cur = cur->_left;
            } else if (kv.first > cur->_kv.first) {
                cur = cur->_right;
            } else if (kv.first == cur->_kv.first) {
                return false;
            } else { assert(false);}
        }

        //2. 插入
        cur = new Node(kv); //默认红色
        cur->_parent = parent;
        if (kv.first < parent->_kv.first)
            parent->_left = cur;
        else
            parent->_right = cur;

        //3. parent的clr为红,向上影响了,需要调整
        while (parent && parent->_clr == RED) {
            Node *grandParent = parent->_parent;

            if(parent == grandParent->_left) {
                Node *uncle = grandParent->_right;
                //种类1: 直接变色
                if (uncle && uncle->_clr == RED) {
                    parent->_clr = uncle->_clr = BLACK;
                    grandParent->_clr = RED;

                    cur = grandParent;
                    parent = cur->_parent;
                } else { //种类2: 旋转+变色
                    if(cur == parent->_left) { //整体过高: 单旋
                        rotateR(grandParent);
                        parent->_clr = BLACK;
                        grandParent->_clr = RED;
                    } else { //整体过高+局部过高: 双旋
                        rotateL(parent);
                        rotateR(grandParent);
                        cur->_clr = BLACK;
                        grandParent->_clr = RED;
                    }
                    break; //旋转后不再向上影响,结束调整
                }
            } else { //相反而已
                Node *uncle = grandParent->_left;

                if (uncle && uncle->_clr == RED) {
                    parent->_clr = uncle->_clr = BLACK;
                    grandParent->_clr = RED;

                    cur = grandParent;
                    parent = cur->_parent;
                } else {
                    if(cur == parent->_right) {
                        rotateL(grandParent);
                        parent->_clr = BLACK;
                        grandParent->_clr = RED;
                    } else {
                        rotateR(parent);
                        rotateL(grandParent);
                        cur->_clr = BLACK;
                        grandParent->_clr = RED;
                    }
                    break;
                }
            }
        }

        _root->_clr = BLACK; //根节点始终为黑
        return true;
    }

其实红黑树还有multi版本,允许重复,有insert_unique和insert_equal,至于相同的插入在左边还是右边就无所谓了,因为高度过大后需要旋转,而不管是插入哪边旋转后的结果都一样。

测试

红黑树的测试不像以前那样打印点信息就能解决,而是要写个方法来确定我们的树100%没问题——颜色没问题、路径长度也没问题。


...
//测试
public:
    //测试RBTree:
    //颜色正确 == 路径长度正确
    //路径长度正确 != 颜色正确
    void inorder() { inorder(_root);}

    bool isBlance()
    {
        if(_root == nullptr) return true;

        if(_root->_clr == RED)
        {
            cout << "违反规则:根为红" << endl;
            return false;
        }

        int refVal = 0;
        Node* left = _root;
        while(left)
        {
            if(left->_clr == BLACK) ++refVal;
            left = left->_left;
        }

        return check(_root, 0, refVal);
    }

private:
    void inorder(Node* root)
    {
        if(root == nullptr) return;

        inorder(root->_left);
        cout << root->_kv.first << ":" << root->_kv.second << endl;
        inorder(root->_right);
    }

    bool check(Node* root, int blackCnt, const int& refVal)
    {
        if(root == nullptr)
        {
            if(blackCnt != refVal)
            {
                cout << "违反规则:黑色结点数量不同" << endl;
                return false;
            }
            return true;
        }

        if(root->_clr == RED && root->_parent->_clr == RED)
        {
            cout << "违反规则:出现了连续红色节点" << endl;
            return false;
        }

        if(root->_clr == BLACK) ++blackCnt;

        return check(root->_left, blackCnt, refVal)
               && check(root->_right, blackCnt, refVal);
    }
};

void testRBTree()
{
//    int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};
    int a[] = {16, 3, 7, 11, 9, 26, 18, 14, 15};
//    int a[] = {4, 2, 6, 1, 3, 5, 15, 7, 16, 14};

    RBTree<int, int> t;
    for(auto e : a) {
        t.insert(make_pair(e, e));
    }
    t.inorder();
    cout << t.isBlance() << endl;
}
#include <iostream>
using namespace std;
#include "RBTree.h"

int main() {
    testRBTree();
    return 0;
}
3:3
7:7
9:9
11:11
14:14
15:15
16:16
18:18
26:26
1

为什么Inorder要弄成子函数或者函数重载?

因为类外调用Inorder时得传参,_root是私有成员,想传也没办法访问到私有成员。


对比AVLTree

对平衡的要求没那么严格,插入删除的时候就会少很多旋转。虽然单次查找效率效率是2logN,但对于CPU来说logN和2logN区别很小,红黑树总体来说效率是更高的。


性能分析

红黑树是近似平衡的树,没有什么最坏情况,插入的时间复杂度为O(log(N)),查找也是。


应用场景

  1. C++的STL
  2. Java的库
  3. Linux内核
  4. 其他库

今天的分享就到这里了,感谢您能看到这里。

这里是培根的blog,期待与你共同进步!文章来源地址https://www.toymoban.com/news/detail-467735.html

到了这里,关于【C++进阶5-红黑树】噩梦般的存在?手提AVLTree暴揍红黑树!的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【C++】手撕红黑树

    作者简介:დ旧言~,目前大二,现在学习Java,c,c++,Python等 座右铭:松树千年终是朽,槿花一日自为荣。 目标:能直接手撕红黑树。 毒鸡汤:行到水穷处,坐看云起时。。 望小伙伴们点赞👍收藏✨加关注哟💕💕  相信大家肯定听过在C++大名鼎鼎的两颗树,这两颗树分别

    2024年03月23日
    浏览(36)
  • C++ 实现红黑树

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

    2024年02月05日
    浏览(40)
  • 【C++】实现红黑树

    红黑树是一个二叉搜索树,与AVL树相比,红黑树不再使用平衡因子来控制树的左右子树高度差,而是用颜色来控制平衡,颜色为红色或者黑色。控制任意一条从根到叶子节点的路径的节点颜色,就可以确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。 红黑树的规

    2024年03月25日
    浏览(40)
  • C++红黑树

    前置说明: 需要学习AVL树的旋转之后再来看红黑树的旋转 因为红黑树的旋转是复用的AVL树的旋转的: 大家可以看我的这篇博客,里面详细介绍了AVL树的四种旋转 C++ AVL树(四种旋转,插入) 对于颜色我们采用枚举类型定义 对于红黑树节点,依旧采用Key-Value模型存储pair 1.共识 首先我们

    2024年02月04日
    浏览(38)
  • C++之红黑树

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

    2024年02月09日
    浏览(41)
  • 【C++】:红黑树

    朋友们、伙计们,我们又见面了,本期来给大家解读一下有关多态的知识点,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成! C 语 言 专 栏: C语言:从入门到精通 数据结构专栏: 数据结构 个  人  主  页 : stackY、 C + + 专 栏   : C++ Linux 专 栏

    2024年02月04日
    浏览(38)
  • C++中的红黑树

    搜索二叉树的概念:二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树: 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值 它的左右子树也分别为二叉搜索树 简单

    2024年02月09日
    浏览(43)
  • C++【红黑树】

    ✨个人主页: 北 海 🎉所属专栏: C++修行之路 🎃操作环境: Visual Studio 2019 版本 16.11.17 红黑树是平衡二叉搜索树中的一种,红黑树性能优异,广泛用于实践中,比如 Linux 内核中的 CFS 调度器就用到了红黑树,由此可见红黑树的重要性。红黑树在实现时仅仅依靠 红 与 黑 两

    2024年02月10日
    浏览(33)
  • C++手撕红黑树

    概念 和AVL树一样,红黑树也是一种二叉搜索树,是解决二叉搜索树不平衡的另一种方案,他在每个节点上增加一个存储位,用于表示节点的颜色,是Red或者Black 红黑树的核心思想是通过一些着色的条件限制,达到一种最长路径不超过最短路径的两倍的状态 所以说红黑树并不

    2024年04月12日
    浏览(43)
  • C++数据结构--红黑树

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

    2024年02月09日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包