『 C++ 』红黑树RBTree详解 ( 万字 )

这篇具有很好参考价值的文章主要介绍了『 C++ 』红黑树RBTree详解 ( 万字 )。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


🦖 红黑树概念

『 C++ 』红黑树RBTree详解 ( 万字 ),二叉树,数据结构,C++,c++,java,开发语言,数据结构

红黑树是一棵较为复杂的树;

其与AVL树相同,也为一棵平衡搜索二叉树;

其与AVL树不同的是,在AVL树中依靠平衡因子bf(Balance Factor)来保证树的结构始终保持为一个高度平衡的状态(每个节点的左右子树高度差不超过1);

而对于红黑树来说,其在节点当中存储了一个颜色,颜色不为红则为黑,根据颜色制定了一系列的规则;

其最终的结果为,在红黑树当中其的最长路径不会超过最短路径的两倍;

可以从这个最终的结果看出,对于红黑树来说其并不是一棵高度平衡的二叉树,相对其只是一棵较为平衡的二叉树;

『 C++ 』红黑树RBTree详解 ( 万字 ),二叉树,数据结构,C++,c++,java,开发语言,数据结构

以该图为例,该图即为一棵红黑树,其具有搜索二叉树的属性;

在上文中提到,红黑树中存在一系列的规则,通过一系列的规则来约束树的结构使其最终能够达到一棵树的最长路径长度不会超过最短路径的二倍;

其规则如下:

  • 红黑树的节点不是红色就是黑色;

  • 根节点的颜色是黑色;

  • 如果一个节点为红色,其两个孩子节点必定为黑色;

  • 对于每一个节点,从该节点到所有后代叶节点的简单路径上,都包含相同数目的黑色节点;

  • 每个叶子节点的颜色都是黑色;

    在该处的叶子节点所指的并不是平时在树的结构中所说的最后一个非空节点,在红黑树当中所谓的叶子节点即为空节点,在此处以NIL表示;

根据上面的规则来看,上图中的树都符合这几条规则,上图中的树为一棵红黑树;

  • 为什么当符合上面五条规则时,其树的结构的最终结果就能保证其最长路径中的节点个数不会超过最短路径节点个数的2倍?

    『 C++ 』红黑树RBTree详解 ( 万字 ),二叉树,数据结构,C++,c++,java,开发语言,数据结构

    以该图为例,该图为一棵红黑树,其符合上述的五条规则;

    在该树当中绘出了两条路径,其中最左侧的黄色路径为其中一条的最长路径;最右侧的蓝色路径为其中一条最短路径;

    对于5条规则中的第四条规则对于每一个节点,从该节点到所有后代叶节点的简单路径上,都包含相同数目的黑色节点,与最终的结果最长路径长度不会超过最短路径的二倍中的黑色节点都包含其中叶子节点的NIL节点;

    如此所见,最长路径的长度为5,最短路径的长度为3;

    可以得出问题中所提到的问题;

从上文可知,红黑树的平衡程度不比AVL树;

AVL树为高度平衡搜索二叉树,而红黑树只是近似平衡搜索二叉树,但在实际的使用场景当中,大多数情况都会使用红黑树而不是AVL树,原因如下:

  • 插入删除操作的难易程度

    当红黑树和AVL树都处于一种规则被破坏的情况下都要使用一些处理手段使其恢复平衡状态;

    对于红黑树来说,红黑树的整体结构与规则处于一种近似平衡的状态而不是高度平衡的状态,这使得红黑树能够允许树在一些情况中不是那么的平衡(最长路径不超过最短路径的2倍);

    而对于AVL树来说,其的平衡为高度平衡状态,虽然说在高度平衡的状态对于数据的读取效率要高于红黑树,但也暴露出来一些问题;

    由于AVL树中节点的平衡因子的绝对值不能大于1,即每当平衡因子的绝对值为2时表示这棵树破坏了AVL树的高度平衡状态,需要对树进行一定的旋转操作使得恢复其本身的高度平衡状态;

    但是就是因为每次在少次插入过后都要进行一次旋转从而降低了AVL树在插入数据情况中的效率;

  • 维护成本

    在维护成本当中,由于AVL树中存在平衡因子,所以每次插入的时候都需要判断新插入节点是否影响其祖先节点的平衡因子致使其不平衡;

    而对于红黑树而言,红黑树中判断是否符合规则的为节点的颜色;

    由于默认插入节点的颜色都为红色,只需要判断这个红色的节点是否影响破坏红黑树本身的规则,若是新插入的节点破坏了其整棵树(子树)的规则结构则对树(子树)的结构进行处理即可;

    两者相比较实际上AVL树的维护成本要高于红黑树,在特殊情况中AVL树的结构可能在实现过程中其可能因为平衡因子未正确更新从而可能导致整棵树的结构被破坏;

    故AVL树的维护成本高于红黑树;

  • 综合性能

    综上所述,红黑树的综合性能高于AVL树,其处于一种较为平衡的状态;

    在极端情况当中,AVL树可能会因为插入大量数据而引发大量的旋转操作导致效率的下降,但红黑树可以很好的避免这个问题;

    当然就算是查找一个数据的情况下红黑树只是略逊AVL树一点;


🦖 红黑树节点的定义

『 C++ 』红黑树RBTree详解 ( 万字 ),二叉树,数据结构,C++,c++,java,开发语言,数据结构

从上文可知,红黑树的节点与AVL树的节点设置的不同点为:

  • AVL树

    AVL树采用的是利用平衡因子来控制;

  • 红黑树

    红黑树采用的是以颜色来判断树的结构;

由上文概念中几个规则可能引出一个问题:

  • 红黑树中的新节点应该是什么颜色?

    黑色?

    红色?

从上文中的规则关于节点的颜色中有这么两条规则:

  1. 如果一个节点为红色,其两个孩子节点必定为黑色;
  2. 对于每一个节点,从该节点到所有后代叶节点的简单路径上,都包含相同数目的黑色节点;

根据这两个规则进行引入,权衡利弊可以发现新节点无论是黑色还是红色都有可能违反两条规则中的其中一条规则;

但是对于两条规则的违反代价来说,新节点为黑色的代价要高于新节点为红色的代价;

当新节点为黑色的时候由于每条简单路径的黑色节点数量要相同,所以当插入新节点为黑色节点时其他的简单路径上必须也插入同样的新黑色节点;

而若是新节点为红色时则只需要对树的结构进行处理即可;

故新节点的颜色应该为红色;

  • 插入过程中宁可违反规则3,也不违反规则4;

代码段:

enum COLOR{
    //红黑树的颜色控制,采用枚举确保颜色只能是红或黑
    RED,
    BLACK
};

/*
    红黑树是搜索二叉树;
    同时红黑树利用颜色控制二叉树的平衡;
    
    红黑树确保没有一条路径会比其他路径长出二倍;
    不为高度平衡 而为近似平衡;
*/

/* 
    红黑树的规则:
    1.每个节点不是红色就是黑色;
    2.根节点是黑色;
    3.如果一个节点是红色的,则它的两个孩子节点是黑色;
    4.对于每个节点,从该节点到其所有后代节点的简单路径上,均包含相同数目的黑色节点
    5.每个叶子节点都是黑色的(这里的叶子节点指的是空节点NIL)

    为什么满足上面的性质红黑树就能保证:其最长路径中节点个数不会超过最短路径节点个数的两倍?
        最短路径即为全黑路径
        最长路径可以指的是红黑相接的路径
        假设存在N个黑色节点的话(包括NIL空节点),则红黑相间的红色节点个数为N-1,则最终的节点个数为2N-1;

*/
template<class K,class V>
struct RBTreeNode{

    RBTreeNode<K, V> *_left;
    RBTreeNode<K, V> *_right;
    RBTreeNode<K, V> *_parent;
    std::pair<K,V> _kv; 
    COLOR _col;

    RBTreeNode(const std::pair<K,V>& kv)
    :_left(nullptr)
    ,_right(nullptr)
    ,_parent(nullptr)
    ,_kv(kv)
    ,_col(RED)//给定缺省值默认为红色
    {}
    /*
        节点颜色默认值为新增的节点为红色还是黑色的问题
        这是选择违反红黑树规则中规则3和规则4的问题,权衡利弊宁可违反规则3也不违反规则4;
    */
};

template<class K,class V>
class RBTree{
    //红黑树整体模型
    typedef RBTreeNode<K,V> Node;
public:

    ~RBTree();

    Node *Find(const K &key);

    bool Insert(const std::pair<K,V>& kv);

    bool IsBalance();

protected:

    void RotateL(Node *parent);

    void RotateR(Node *parent);

    void _Destory(Node* &root);

private:
    Node* _root = nullptr;
    }

本文中的红黑树实现一样采用key value模型进行演示;


🦖 红黑树的插入

『 C++ 』红黑树RBTree详解 ( 万字 ),二叉树,数据结构,C++,c++,java,开发语言,数据结构

红黑树也是基于搜索二叉树后控制其平衡条件的一种二叉树;

其插入模式与逻辑与搜索二叉树相同;

与之不同的是由于红黑树的新节点插入为红色节点,所以插入过程当中可能违反红黑树五条规则中的第三条规则;

  • 如果一个节点为红色,其两个孩子节点必定为黑色;

即可能发生红色节点的孩子节点也为红色节点,在这种情况当中就要对树的结构进行对应的调整更新使其恢复原来的近似平衡状态;

  • 代码段

    bool Insert(const std::pair<K,V>& kv){
            if(_root == nullptr){
                _root = new Node(kv);
                _root->_col = BLACK;
                return true;
            }
            
            Node *cur = _root;
            Node *parent = nullptr;
    
            while(cur){
                if(cur->_kv.first < kv.first){
                    parent = cur;
                    cur = cur->_right;
                }
                else if(cur->_kv.first > kv.first){
                    parent = cur;
                    cur = cur->_left;
                }
                else{
                    return false;
                }
            }
    
            cur = new Node(kv);
            if(parent->_kv.first < kv.first){
                parent->_right = cur;
                cur->_parent = parent;
            }
            else{
                parent->_left = cur;
                cur->_parent = parent;
            }
    
        	//......
           /*
           		判断与处理
           */
    
            return true;
    
        }
    

当插入的动作结束后应该及时判断新增节点是否影响整棵红黑树的结构;

由于新增节点为红色节点,所以只需判断节点是否破坏红黑树规则中的规则3即可;

即判断新增节点的父亲节点是否为红色:

  • 不为红色

    若是新增节点的父亲节点不为红色,则说明该次插入并不影响红黑树的规则,算是一次正常插入;

  • 为红色

    若是新增节点的父亲节点为红色节点,说明该次插入违反了红黑树规则中的第三条规则,需要对树(子树)进行调整使其恢复原来的红黑树;

当红黑树的第三条规则被违反时将会出现几种情况;

下图为一张抽象图,其中uncle表示一棵子树;

『 C++ 』红黑树RBTree详解 ( 万字 ),二叉树,数据结构,C++,c++,java,开发语言,数据结构

以单边为例,该图即为单边(左边)可能出现的违反第三条规则的情况;


🦖 数据插入后的调整

『 C++ 』红黑树RBTree详解 ( 万字 ),二叉树,数据结构,C++,c++,java,开发语言,数据结构

在上文中提到了当数据插入结束后需要对插入的新节点进行判断,由于插入方式的问题(节点的颜色),所以需要对新节点的位置判断其是否存在违反第三条规则的情况;

『 C++ 』红黑树RBTree详解 ( 万字 ),二叉树,数据结构,C++,c++,java,开发语言,数据结构

从该图中可以看到,对于红黑树的处理方式与AVL的调整方式不同,因为对于红黑树而言主要是需要对节点进行重新着色;

同时在此基础上对树(子树)在需要的情况下对其进行旋转操作;

从图中可以发现在红黑树中重点看几个节点:

  • cur节点

    新增节点

  • parent节点

    新增节点的父亲节点

  • grandfather节点

    新增节点的祖父节点

  • uncle节点

    新增节点的父亲节点的兄弟节点

而在红黑树当中,重点所看的节点就算所谓的uncle节点叔叔节点;

这个节点决定了红黑树在违反了规则之后需要使用哪种方式对树(子树)进行调整;

而红黑树的调整方法中uncle节点扮演着重要的作用,若是没有使用或者关注uncle节点,则可能使用错误的调整方案使得红黑树的结构变得更加的混乱;

下面的例子主要以单边为例,对于红黑树的调整来说不重点对节点的位置进行处理而是对于uncle节点来进行处理;


🦕 情况一:ucnle存在且为红

『 C++ 』红黑树RBTree详解 ( 万字 ),二叉树,数据结构,C++,c++,java,开发语言,数据结构

当出现这种情况时即cur新增节点与其父亲节点parent节点的颜色为红色;

且在这种情况当中uncle节点存在且该节点的颜色为红色;

『 C++ 』红黑树RBTree详解 ( 万字 ),二叉树,数据结构,C++,c++,java,开发语言,数据结构

以该图为例;

其中这种情况下对于树(子树)的处理情况是最简单的,只需要对节点进行重新着色即可,即:

  1. parent节点变黑

  2. uncle节点变黑

  3. cur节点变红

根据上面三步的操作即可完成该情况的解决方式;

  • 为什么说这个方式是最容易处理的情况?

    出现这种情况时由于解决的方式只需要对节点进行重新着色即可,并不需要对节点的方向进行判断;

    cur节点在parent节点的左右方向,出现这种情况都可以使用该方式进行解决,可以对其进行单独的if条件语句判断;

  • 代码段

    while(parent && parent->_col == RED){
                //由于默认插入的节点为红色 所以当parent节点存在且为红色时表示需要进行调整
                Node *grandfather = parent->_parent;//根节点必须为黑色 所以说明该节点上还有节点
                if(grandfather->_left == parent){
                    Node *uncle = grandfather->_right;
                    
                    //插入时颜色的变化分三种情况
                    if(uncle && uncle->_col == RED){
                        /*
                            uncle存在且为红
                            当uncle存在且为红的时候,说明cur节点为新增节点
                            这时候的处理方式只需要对节点进行变色处理即可
                            将parent节点与uncle节点变黑 uncle节点变红
                        */
                        parent->_col = BLACK;
                        uncle->_col = BLACK;
                        grandfather->_col = RED;
    
                        cur = grandfather;
                        parent = cur->_parent;
                    }
    
                    else{//uncle节点不存在或者uncle节点为黑色
                         //......
                        }
                        break;
                    }
                }
    
                else{ 
                    // if(grandfather->_right == parent){
                    Node *uncle = grandfather->_left;
                    if (uncle && uncle->_col == RED){
                        parent->_col = BLACK;
                        uncle->_col = BLACK;
                        grandfather->_col = RED;
                        
                        cur = grandfather;
                        parent = cur->_parent;
                    }
                    else{//uncle节点不存在或者uncle节点为黑色
                         //......
                         break;
                    }
                }
            }
            _root->_col = BLACK;
    
            return true;
    
        }
    

当处理完之后应继续向上更新节点位置:

  • cur节点更新为当前的grandfather节点;
  • parent节点更新为新的cur节点的_parent节点;

并按照循环来判断该处解决之后是否需要再向上进行解决

  • 若是parent节点不为空且parent节点为红色时则继续向上更新;
  • 若是parent节点为空或是parent节点存在且为黑色时说明该树(子树)不存在问题,插入环节结束;

🦕 情况二:uncle不存在或uncle存在且为黑

『 C++ 』红黑树RBTree详解 ( 万字 ),二叉树,数据结构,C++,c++,java,开发语言,数据结构

当出现这种情况时,简单的对节点进行重新着色的方案就不予推荐;

因为出现这种情况时无论如何对节点进行重新着色都将不可能将树(子树)的结构恢复为原来的红黑树结构;

当出现这种情况时则说明树的结构已经趋于不平衡,需要借助到在AVL树种所提到的旋转方案;

且出现该情况后需要进行判断cur节点存在于parent节点的左边还是右边:

  • cur存在于parent节点的左边

    cur节点存在于parent节点的左侧时则需要进行单旋操作;

  • cur存在于parent节点的右边

    cur节点存在于parent节点的右侧时则需要进行双旋操作;

根据cur节点所处的位置来判断需要进行单旋还是双旋操作;

当然若是需要进行双旋时双旋的顺序判断取决于是grandfather的左子树出现问题还是该节点的右子树出现问题;

  • 为什么uncle不存在和uncle存在且为黑两种情况可以用同一种方案进行解决?

    实际上在操作中uncle不存在 与 uncle存在且为黑的情况可以用同一种方式进行解决是因为其构造是相同的,只不过一个具有节点一个没有节点;

    uncle节点不存在的情况下cur节点可能是新增节点;

    uncle节点存在且为黑的情况其一定是由情况一变化而来,即情况一解决后向上更新所发现的新情况;

『 C++ 』红黑树RBTree详解 ( 万字 ),二叉树,数据结构,C++,c++,java,开发语言,数据结构

该图即为单边情况下子树出现问题的解决办法的图例(具象图);

  • 代码段

    while(parent && parent->_col == RED){
                //由于默认插入的节点为红色 所以当parent节点存在且为红色时表示需要进行调整
                Node *grandfather = parent->_parent;//根节点必须为黑色 所以说明该节点上还有节点
                if(grandfather->_left == parent){
                    Node *uncle = grandfather->_right;
                    
                    //插入时颜色的变化分三种情况
                    if(uncle && uncle->_col == RED){
                        /*
                            uncle存在且为红
                        */
                    }
    
                    else{// (uncle == nullptr || uncle->_col == BLACK)
                         /*
                            另一种情况即为uncle节点不存在或者uncle节点存在且为黑色节点
                                当uncle节点不存在时说明cur节点为新增节点
                                当uncle节点存在但是节点颜色为黑色时说明cur节点不为新增节点
                            而是由情况1变化而来;
                            这两种情况虽然cur节点的状态不同但是真正意义上来说两者在处理方式可以以相同的方式进行处理
                            
    
                            但是uncle节点不存在或是uncle存在且为黑的情况虽然统一采取同一种方式进行处理
                            但是还将这种处理方式进行两种情况的划分 分别为cur节点处于parent节点的左子树还是右子树
                            通过左子树或者是右子树取决于使用的措施是采用单选操作还是双旋操作
                         */
                        if(cur == parent->_left){
                            RotateR(grandfather);
    
                            parent->_col = BLACK;
                            grandfather->_col = RED;
                        }
                        else{ // cur == parent->_left
                            RotateL(parent);
                            RotateR(grandfather);
                            
                           cur->_col = BLACK;
                           grandfather->_col = RED;
                        }
                        break;
                    }
                }
    
                else{ 
                    // if(grandfather->_right == parent){
                    Node *uncle = grandfather->_left;
                    if (uncle && uncle->_col == RED){
                        /*
                            uncle存在且为红
                        */
                    }
                    else{// (uncle == nullptr || uncle->_col == BLACK)
                         if(cur == parent->_right){
                            RotateL(grandfather);
    
                      
                            grandfather->_col = RED;
                            parent->_col = BLACK;
    
                         }
    
                         
                         else{
                             RotateR(parent);
                             RotateL(grandfather);
    
                            cur->_col = BLACK;
                            grandfather->_col = RED;
                         }
                         break;
                    }
                }
            }
            _root->_col = BLACK;
    
            return true;
    
        }
    

uncle不存在 或 是uncle存在且为黑 的两种情况处理后则可以直接break退出循环;


🦕 插入函数代码段(参考)

『 C++ 』红黑树RBTree详解 ( 万字 ),二叉树,数据结构,C++,c++,java,开发语言,数据结构

    bool Insert(const std::pair<K,V>& kv){
        if(_root == nullptr){
            _root = new Node(kv);
            _root->_col = BLACK;
            return true;
        }
        
        Node *cur = _root;
        Node *parent = nullptr;

        while(cur){
            if(cur->_kv.first < kv.first){
                parent = cur;
                cur = cur->_right;
            }
            else if(cur->_kv.first > kv.first){
                parent = cur;
                cur = cur->_left;
            }
            else{
                return false;
            }
        }

        cur = new Node(kv);
        if(parent->_kv.first < kv.first){
            parent->_right = cur;
            cur->_parent = parent;
        }
        else{
            parent->_left = cur;
            cur->_parent = parent;
        }

        while(parent && parent->_col == RED){
            //由于默认插入的节点为红色 所以当parent节点存在且为红色时表示需要进行调整
            Node *grandfather = parent->_parent;//根节点必须为黑色 所以说明该节点上还有节点
            if(grandfather->_left == parent){
                Node *uncle = grandfather->_right;
                
                //插入时颜色的变化分三种情况
                if(uncle && uncle->_col == RED){
                    /*
                        uncle存在且为红
                        当uncle存在且为红的时候,说明cur节点为新增节点
                        这时候的处理方式只需要对节点进行变色处理即可
                        将parent节点与uncle节点变黑 uncle节点变红
                    */
                    parent->_col = BLACK;
                    uncle->_col = BLACK;
                    grandfather->_col = RED;

                    cur = grandfather;
                    parent = cur->_parent;
                }

                else{
                     // if(uncle == nullptr || uncle->_col == BLACK)
                     /*
                        另一种情况即为uncle节点不存在或者uncle节点存在且为黑色节点
                            当uncle节点不存在时说明cur节点为新增节点
                            当uncle节点存在但是节点颜色为黑色时说明cur节点不为新增节点
                        而是由情况1变化而来;
                        这两种情况虽然cur节点的状态不同但是真正意义上来说两者在处理方式可以以相同的方式进行处理
                        

                        但是uncle节点不存在或是uncle存在且为黑的情况虽然统一采取同一种方式进行处理
                        但是还将这种处理方式进行两种情况的划分 分别为cur节点处于parent节点的左子树还是右子树
                        通过左子树或者是右子树取决于使用的措施是采用单选操作还是双旋操作
                     */
                    if(cur == parent->_left){
                        RotateR(grandfather);
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    else{ // cur == parent->_left
                        RotateL(parent);
                        RotateR(grandfather);
                        
                       cur->_col = BLACK;
                       grandfather->_col = RED;
                    }
                    break;
                }
            }

            else{ 
                // if(grandfather->_right == parent){
                Node *uncle = grandfather->_left;
                if (uncle && uncle->_col == RED){
                    parent->_col = BLACK;
                    uncle->_col = BLACK;
                    grandfather->_col = RED;
                    
                    cur = grandfather;
                    parent = cur->_parent;
                }
                else{
                     // if(uncle == nullptr || uncle->_col == BLACK)
                     if(cur == parent->_right){
                        RotateL(grandfather);
                         
                        grandfather->_col = RED;
                        parent->_col = BLACK;

                     }

                     
                     else{
                         RotateR(parent);
                         RotateL(grandfather);

                        cur->_col = BLACK;
                        grandfather->_col = RED;
                     }
                     break;
                }
            }
        }
        _root->_col = BLACK;

        return true;
    }

🦕 旋转操作代码段(参考)

『 C++ 』红黑树RBTree详解 ( 万字 ),二叉树,数据结构,C++,c++,java,开发语言,数据结构

 void RotateL(Node *parent){


        Node *cur = parent->_right;
        Node *curleft = cur->_left;

        parent->_right = curleft;
        if (curleft)
        {
            curleft->_parent = parent;
        }

        cur->_left = parent;

        Node *ppnode = parent->_parent;

        parent->_parent = cur;

        if (parent == _root)
        {
            _root = cur;
            cur->_parent = nullptr;
        }
        else
        {
            if (ppnode->_left == parent)
            {
                ppnode->_left = cur;
            }
            else
            {
                ppnode->_right = cur;
            }

            cur->_parent = ppnode;
        }
    }

    void RotateR(Node *parent){
        

        Node *cur = parent->_left;
        Node *curright = cur->_right;

        parent->_left = curright;
        if (curright)
            curright->_parent = parent;

        Node *ppnode = parent->_parent;
        cur->_right = parent;
        parent->_parent = cur;

        if (ppnode == nullptr)
        {
            _root = cur;
            cur->_parent = nullptr;
        }
        else
        {
            if (ppnode->_left == parent)
            {
                ppnode->_left = cur;
            }
            else
            {
                ppnode->_right = cur;
            }

            cur->_parent = ppnode;
        }
    }

旋转操作中无需像AVL树那样关心对应的平衡因子;


🦖 判断红黑树是否符合规则

『 C++ 』红黑树RBTree详解 ( 万字 ),二叉树,数据结构,C++,c++,java,开发语言,数据结构

与AVL树相同,当一棵红黑树被创建完毕之后若是只用中序遍历来判断的话只能判断出该树是否为搜索二叉树,但是不能保证出所创建出的树是一棵红黑树;

对于红黑树是否平衡的判断一样可以利用一个接口去是先解决;

当然判断红黑树是否平衡的方法多种多样;

其中在本文章的方法即为: 利用一个pair<bool,vector<int>>对象来存储结果,最终返回pair中的bool结果,当然该中方式也需要用到子函数来完成其他的判断:

bool IsBalance(){
        //...
    }
  1. 判断根节点_root节点的颜色是否为黑色:

    若是该节点的颜色为红色则直接返回false;

  2. 判断是否存在连续的红色节点与每条简单路径当中是否存在相同个数的黑色节点:

    定义一个Check()子函数用来判断是否出现连续的红色节点;

    传递一个blackNum变量用来记录每条简单路径的黑色节点个数;

    Check()函数传递了一个pair<bool,vector<int>>对象的引用,为了能在函数之中利用其中的vector<int>来判断每条简单路径上是否存在相同的黑色节点数量;

    bool则是用来判断是否存在连续相同的红色节点;

    利用递归的思路,当节点为nullptr空时vector<int>部分添加对应的blackNum黑色节点个数;

     void _Check(std::pair<bool,std::vector<int>> &ret,Node *root,size_t blackNum = 0){
            
            if(root == nullptr){
                ret.first = ret.first && true;
                ret.second.push_back(blackNum);
                return;
            }
    
            if(root->_col == RED && root->_parent->_col == RED){
                ret.first = ret.first && false;
                return ;
            }
    
            if(root->_col == BLACK){
                blackNum++;
            }
    
            _Check(ret, root->_left, blackNum);
            _Check(ret, root->_right, blackNum);
        }
    
  3. 最终对该pair对象进行判断即可;

  • 代码段

     bool IsBalance(){
            if(_root == nullptr){
                return true;
            }
    
            if(_root && _root->_col == RED){
                //头节点为红色节点说明树的插入或者某次旋转后的颜色变化出现问题
                return false;
            }
            
            std::pair<bool,std::vector<int>> ret ;
            ret.first = true;
            _Check(ret,_root,0);
    
            if(!ret.first){
                std::cout << "某一路径出现连续红色节点" << std::endl;
            }
    
            bool to_comp = true;
            size_t _comp = ret.second[0];
            for(auto &it : ret.second){
                if(it != _comp){
                    to_comp = false;
                    break;
                }
    
                std::cout << it << std::endl;
            }
            
            return to_comp && ret.first;
        }
    
    

当然可以使用其他方法,并在对应的出现错误的位置根据条件使用assert(false)断言断死来排查问题所在;


🦖 红黑树的析构函数

『 C++ 』红黑树RBTree详解 ( 万字 ),二叉树,数据结构,C++,c++,java,开发语言,数据结构

红黑树的析构函数只需要写一个_Destroy()函数并在析构函数中进行调用即可;

当然_Destroy()函数采用后序遍历的方式对节点逐个进行释放;

    void _Destory(Node* &root){
        if(root == nullptr){
            return ;
        }

        _Destory(root->_left);
        _Destory(root->_right);

        delete root;

        root = nullptr;
    }

🦖 完整代码(供参考)

『 C++ 』红黑树RBTree详解 ( 万字 ),二叉树,数据结构,C++,c++,java,开发语言,数据结构

该段代码中由于测试需要定义了一些非必要的函数;文章来源地址https://www.toymoban.com/news/detail-800441.html

#include<iostream>

#include<vector>

enum COLOR{
    //红黑树的颜色控制,采用枚举确保颜色只能是红或黑
    RED,
    BLACK
};

/*

    红黑树是搜索二叉树;
    同时红黑树利用颜色控制二叉树的平衡;
    
    红黑树确保没有一条路径会比其他路径长出二倍;
    不为高度平衡 而为近似平衡;

*/


/* 
    红黑树的规则:
    1.每个节点不是红色就是黑色;
    2.根节点是黑色;
    3.如果一个节点是红色的,则它的两个孩子节点是黑色;
    4.对于每个节点,从该节点到其所有后代节点的简单路径上,均包含相同数目的黑色节点
    5.每个叶子节点都是黑色的(这里的叶子节点指的是空节点NIL)

    为什么满足上面的性质红黑树就能保证:其最长路径中节点个数不会超过最短路径节点个数的两倍?
        最短路径即为全黑路径
        最长路径可以指的是红黑相接的路径
        假设存在N个黑色节点的话(包括NIL空节点),则红黑相间的红色节点个数为N-1,则最终的节点个数为2N-1;

*/
template<class K,class V>
struct RBTreeNode{

    RBTreeNode<K, V> *_left;
    RBTreeNode<K, V> *_right;
    RBTreeNode<K, V> *_parent;
    std::pair<K,V> _kv; 
    COLOR _col;

    RBTreeNode(const std::pair<K,V>& kv)
    :_left(nullptr)
    ,_right(nullptr)
    ,_parent(nullptr)
    ,_kv(kv)
    ,_col(RED)//给定缺省值默认为红色
    {}
    /*
        节点颜色默认值为新增的节点为红色还是黑色的问题
        这是选择违反红黑树规则中规则3和规则4的问题,权衡利弊宁可违反规则3也不违反规则4;
    */
};

template<class K,class V>
class RBTree{
    typedef RBTreeNode<K,V> Node;
public:

    ~RBTree(){
        _Destory(_root);
    }

    void InOrder(){
        _InOrder(_root);
    }

    Node *Find(const K &key){
        Node* cur = _root;
        while(cur){
            if(key>cur->_kv.first){
                cur = cur->_right;
            }
            else if(key<cur->_kv.first){
                cur = cur->_left;
            }
            else{
                return cur;
            }
        }
        return nullptr;
    }

    bool Insert(const std::pair<K,V>& kv){
        if(_root == nullptr){
            _root = new Node(kv);
            _root->_col = BLACK;
            return true;
        }
        
        Node *cur = _root;
        Node *parent = nullptr;

        while(cur){
            if(cur->_kv.first < kv.first){
                parent = cur;
                cur = cur->_right;
            }
            else if(cur->_kv.first > kv.first){
                parent = cur;
                cur = cur->_left;
            }
            else{
                return false;
            }
        }

        cur = new Node(kv);
        if(parent->_kv.first < kv.first){
            parent->_right = cur;
            cur->_parent = parent;
        }
        else{
            parent->_left = cur;
            cur->_parent = parent;
        }

        while(parent && parent->_col == RED){
            //由于默认插入的节点为红色 所以当parent节点存在且为红色时表示需要进行调整
            Node *grandfather = parent->_parent;//根节点必须为黑色 所以说明该节点上还有节点
            if(grandfather->_left == parent){
                Node *uncle = grandfather->_right;
                
                //插入时颜色的变化分三种情况
                if(uncle && uncle->_col == RED){
                    /*
                        uncle存在且为红
                        当uncle存在且为红的时候,说明cur节点为新增节点
                        这时候的处理方式只需要对节点进行变色处理即可
                        将parent节点与uncle节点变黑 uncle节点变红
                    */
                    parent->_col = BLACK;
                    uncle->_col = BLACK;
                    grandfather->_col = RED;

                    cur = grandfather;
                    parent = cur->_parent;
                }

                else{
                     // if(uncle == nullptr || uncle->_col == BLACK)
                     /*
                        另一种情况即为uncle节点不存在或者uncle节点存在且为黑色节点
                            当uncle节点不存在时说明cur节点为新增节点
                            当uncle节点存在但是节点颜色为黑色时说明cur节点不为新增节点
                        而是由情况1变化而来;
                        这两种情况虽然cur节点的状态不同但是真正意义上来说两者在处理方式可以以相同的方式进行处理
                        

                        但是uncle节点不存在或是uncle存在且为黑的情况虽然统一采取同一种方式进行处理
                        但是还将这种处理方式进行两种情况的划分 分别为cur节点处于parent节点的左子树还是右子树
                        通过左子树或者是右子树取决于使用的措施是采用单选操作还是双旋操作
                     */
                    if(cur == parent->_left){
                        RotateR(grandfather);

                        
                            // parent->_col = RED;
                            // grandfather->_col = cur->_col = BLACK;
                        

                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    else{ // cur == parent->_left
                        RotateL(parent);
                        RotateR(grandfather);
                        
                            // cur->_col = RED;
                            // grandfather->_col = BLACK;
                            // parent->_col = BLACK;
                        
                       cur->_col = BLACK;
                       grandfather->_col = RED;
                    }
                    break;
                }
            }

            else{ 
                // if(grandfather->_right == parent){
                Node *uncle = grandfather->_left;
                if (uncle && uncle->_col == RED){
                    parent->_col = BLACK;
                    uncle->_col = BLACK;
                    grandfather->_col = RED;
                    
                    cur = grandfather;
                    parent = cur->_parent;
                }
                else{
                     // if(uncle == nullptr || uncle->_col == BLACK)
                     if(cur == parent->_right){
                        RotateL(grandfather);

                  
                        grandfather->_col = RED;
                        
                        parent->_col = BLACK;

                     }

                     
                     else{
                         RotateR(parent);
                         RotateL(grandfather);

                        cur->_col = BLACK;
                        grandfather->_col = RED;
                     }
                     break;
                }
            }
        }
        _root->_col = BLACK;

        return true;

    }

    bool IsBalance(){
        if(_root == nullptr){
            return true;
        }

        if(_root && _root->_col == RED){
            //头节点为红色节点说明树的插入或者某次旋转后的颜色变化出现问题
            return false;
        }
        
        std::pair<bool,std::vector<int>> ret ;
        ret.first = true;
        _Check(ret,_root,0);

        if(!ret.first){
            std::cout << "某一路径出现连续红色节点" << std::endl;
        }

        bool to_comp = true;
        size_t _comp = ret.second[0];
        for(auto &it : ret.second){
            if(it != _comp){
                to_comp = false;
                break;
            }

            std::cout << it << std::endl;
        }

        

        return to_comp && ret.first;
    }

    int getHeight()
    {
        return getHeight(_root);
    }

protected:


    void RotateL(Node *parent){


        Node *cur = parent->_right;
        Node *curleft = cur->_left;

        parent->_right = curleft;
        if (curleft)
        {
            curleft->_parent = parent;
        }

        cur->_left = parent;

        Node *ppnode = parent->_parent;

        parent->_parent = cur;

        if (parent == _root)
        {
            _root = cur;
            cur->_parent = nullptr;
        }
        else
        {
            if (ppnode->_left == parent)
            {
                ppnode->_left = cur;
            }
            else
            {
                ppnode->_right = cur;
            }

            cur->_parent = ppnode;
        }
    }

    void RotateR(Node *parent){
        

        Node *cur = parent->_left;
        Node *curright = cur->_right;

        parent->_left = curright;
        if (curright)
            curright->_parent = parent;

        Node *ppnode = parent->_parent;
        cur->_right = parent;
        parent->_parent = cur;

        if (ppnode == nullptr)
        {
            _root = cur;
            cur->_parent = nullptr;
        }
        else
        {
            if (ppnode->_left == parent)
            {
                ppnode->_left = cur;
            }
            else
            {
                ppnode->_right = cur;
            }

            cur->_parent = ppnode;
        }
    }

    void _InOrder(Node *root){
        if(root == nullptr) return ;
        _InOrder(root->_left);
        std::cout << root->_kv.first << " : " << root->_kv.second << " col : " << root->_col << std::endl;
        _InOrder(root->_right);
    }

    void _Check(std::pair<bool,std::vector<int>> &ret,Node *root,size_t blackNum = 0){
        
        if(root == nullptr){
            ret.first = ret.first && true;
            ret.second.push_back(blackNum);
            return;
        }

        if(root->_col == RED && root->_parent->_col == RED){
            ret.first = ret.first && false;
            return ;
        }

        if(root->_col == BLACK){
            blackNum++;
        }

        _Check(ret, root->_left, blackNum);
        _Check(ret, root->_right, blackNum);
    }
    
    int getHeight(Node *root)
    {
        if (root == nullptr)
        {
            return 0;
        }
        int left = getHeight(root->_left);
        int right = getHeight(root->_right);

        return left > right ? left + 1 : right + 1;
    }

    void _Destory(Node* &root){
        if(root == nullptr){
            return ;
        }

        _Destory(root->_left);
        _Destory(root->_right);

        delete root;

        root = nullptr;
    }

private:
    Node* _root = nullptr;
};

到了这里,关于『 C++ 』红黑树RBTree详解 ( 万字 )的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 数据结构-各种树(二叉树、二叉查找树、平衡二叉树、红黑树、B树、B+树)

    概念:二叉树(binary tree)是指树中节点的度不大于2的有序树,它是一种最简单且最重要的树。二叉树的递归定义为:二叉树是一棵空树,或者是一棵由一个根节点和两棵互不相交的,分别称作根的左子树和右子树组成的非空树;左子树和右子树又同样都是二叉树 特点:每个

    2024年02月09日
    浏览(47)
  • 【数据结构大全】你想要的都有,数组、链表、堆栈、二叉树、红黑树、B树、图......

    作者简介: 目录 1.概述 2.线性结构 3.时间复杂度 4.查找算法 5.树 6.图 博主之前写过一个完整的关于数据结构的系列文章,一共十三篇,内容包含,数组、链表、堆栈、队列、时间复杂度、顺序查找、二分查找、二叉树、二叉搜索树、平衡二叉树、红黑树、B树、B+树、大顶堆

    2024年02月10日
    浏览(46)
  • 数据结构与算法(三):树论(树形结构、二叉树、二叉搜索树、红黑树、Btree&B+Tree、赫夫曼树、堆树)

    树论(树形结构、二叉树、二叉搜索树、红黑树、Btree、B+Tree、赫夫曼树、堆树) 在树形结构里面重要的术语: 结点:树里面的元素。 父子关系:结点之间相连的边 子树:当结点大于1时,其余的结点分为的互不相交的集合称为子树 度:一个结点拥有的子树数量称为结点的

    2024年02月01日
    浏览(93)
  • 数据结构之进阶二叉树(二叉搜索树和AVL树、红黑树的实现)超详细解析,附实操图和搜索二叉树的实现过程图

    绪论​ “生命有如铁砧,愈被敲打,愈能发出火花。——伽利略”;本章主要是数据结构 二叉树的进阶知识,若之前没学过二叉树建议看看这篇文章一篇掌握二叉树,本章的知识从浅到深的 对搜索二叉树的使用进行了介绍和对其底层逻辑的实现进行了讲解 ,希望能对你有所

    2024年02月04日
    浏览(46)
  • 搜索二叉树 | 红黑树 | 验证是否为红黑树 | 代码实现

    黑红树是一颗特殊的搜索二叉树,本文在前文的基础上,图解红黑树插入:前文 链接,完整对部分关键代码展示,完整的代码在gitee仓库中: 链接 文章中有错误的地方,欢迎大家指正!如果有帮助到你,也请多多点赞支持! 1.红黑树的概述 平衡二叉树要求左右子树的高度差

    2024年02月21日
    浏览(39)
  • 【链式二叉树】数据结构链式二叉树的(万字详解)

    前言: 在上一篇博客中,我们已经详解学习了堆的基本知识,今天带大家进入的是二叉树的另外一种存储方式----“链式二叉树”的学习,主要用到的就是“递归思想”!! 前情回顾: 再看二叉树基本操作前,再回顾下二叉树的概念,二叉树是: 空树 非空:根节点,根节点

    2024年01月20日
    浏览(49)
  • 红黑树(RBTree)

    红黑树的基本性质 (1)红黑树是每个结点都带有颜色属性的二叉查找树,颜色或红色或黑色。在二叉搜索树强制一般要求以外,对于任何有效的红黑树我们增加了如下的额外要求: 性质1. 结点是红色或黑色。  性质2. 根结点是黑色。  性质3. 所有叶子都是黑色。(叶子是NI

    2024年02月05日
    浏览(36)
  • 红黑树(RBTree)

    红黑树是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型用途是实现关联数组。它在1972年由鲁道夫·贝尔发明,被称为「对称二叉B树」,它现代的名字源于Leo J. Guibas和罗伯特·塞奇威克于1978年写的一篇论文。红黑树的结构复杂,但它的操作有着良好的

    2024年02月12日
    浏览(34)
  • 二叉树、红黑树、B树、B+树

    一棵二叉树是结点的一个有限集合,该集合或者为空,或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。 二叉树的 特点 : 每个结点最多有两棵子树,即二叉树不存在度大于2的结点。 二叉树的子树有左右之分,其子树的次序不能颠倒。 满二叉树:二叉树的

    2024年02月11日
    浏览(39)
  • 二叉树、二叉查找树、平衡树和红黑树概念及其性质

      在所有的树结构,基本上都遵循左小右大的原则。本文分享二叉树、二叉查找树、平衡树和红黑树概念及其性质。   二叉树(Binary Tree)是指每个节点最多只有两个分支的树结构(即不存在分支大于 2 的节点),如下图所示:   这是一棵拥有 6 个节点深度为 2(深度

    2024年02月08日
    浏览(37)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包