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

文章目录

    • 🦖 红黑树概念
    • 🦖 红黑树节点的定义
    • 🦖 红黑树的插入
    • 🦖 数据插入后的调整
      • 🦕 情况一:ucnle存在且为红
      • 🦕 情况二:uncle不存在或uncle存在且为黑
      • 🦕 插入函数代码段(参考)
      • 🦕 旋转操作代码段(参考)
    • 🦖 判断红黑树是否符合规则
    • 🦖 红黑树的析构函数
    • 🦖 完整代码(供参考)

🦖 红黑树概念

请添加图片描述

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

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

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

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

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

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

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

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

其规则如下:

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

  • 根节点的颜色是黑色;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • 维护成本

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

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

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

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

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

  • 综合性能

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

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

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

🦖 红黑树节点的定义

请添加图片描述

从上文可知,红黑树的节点与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模型进行演示;

🦖 红黑树的插入

请添加图片描述

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

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

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

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

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

  • 代码段

    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表示一棵子树;

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

🦖 数据插入后的调整

请添加图片描述

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

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

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

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

  • cur节点

    新增节点

  • parent节点

    新增节点的父亲节点

  • grandfather节点

    新增节点的祖父节点

  • uncle节点

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

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

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

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

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

🦕 情况一:ucnle存在且为红

请添加图片描述

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

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

以该图为例;

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

  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存在且为黑

请添加图片描述

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

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

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

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

  • cur存在于parent节点的左边

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

  • cur存在于parent节点的右边

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

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

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

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

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

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

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

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

  • 代码段

    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退出循环;

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

请添加图片描述

    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;
    }

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

请添加图片描述

 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树那样关心对应的平衡因子;

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

请添加图片描述

与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)断言断死来排查问题所在;

🦖 红黑树的析构函数

请添加图片描述

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

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

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

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

        delete root;

        root = nullptr;
    }

🦖 完整代码(供参考)

请添加图片描述

该段代码中由于测试需要定义了一些非必要的函数;

#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;
};

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/332106.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【C++入门】C++ STL中string常用函数用法总结

【C++入门】C++ STL中string常用函数用法总结

目录 前言 1. string使用 2. string的常见构造 3. string类对象的访问及遍历 迭代器遍历&#xff1a; 访问&#xff1a; 4. string类对象的容量操作 4.1 size和length 4.2 clear、empty和capacity 4.3 reserve和resize reserve resize 5. string类对象的修改操作 push_back o…
阅读更多...
version-polling一款用于实时检测 web 应用更新的 JavaScript 库

version-polling一款用于实时检测 web 应用更新的 JavaScript 库

为了解决后端部署之后&#xff0c;如何通知用户系统有新版本&#xff0c;并引导用户刷新页面以加载最新资源的问题。 实现原理 1.使用 Web Worker API 在浏览器后台轮询请求页面&#xff0c;不会影响主线程运行。 2.命中协商缓存&#xff0c;对比本地和服务器请求响应头etag字…
阅读更多...
施耐德PLCTM200CE 如何实现远程上传下载程序？

施耐德PLCTM200CE 如何实现远程上传下载程序？

准备工作 一台可联网操作的电脑一台单网口的远程透传网关及博达远程透传配置工具网线一条&#xff0c;用于实现网络连接和连接PLC一台施耐德TM200CE PLC及其编程软件一张4G卡或WIFI天线实现通讯(使用4G联网则插入4G SIM卡&#xff0c;WIFI联网则将WIFI天线插入USB口&#xff0…
阅读更多...
Unity3D和three.js的比较

Unity3D和three.js的比较

一、Unity3D和three.js简介 Unity3D是一款跨平台的游戏引擎，可以用于开发2D和3D游戏。它提供了一个可视化的开发环境，包含了强大的编辑器和工具，使开发者可以方便地创建游戏场景、添加物体、设置物理效果、编写脚本等。Unity3D支持多种平台，包括PC、移动设备、主机等，可以…
阅读更多...
HBuilder 创建的 Uui-App项目 如何发布到微信小程序

HBuilder 创建的 Uui-App项目 如何发布到微信小程序

需提前准备的工具&#xff1a;HBuilder X &#xff0c;微信开发者工具 目录 一、微信小程序账号申请 二、在微信开发者工具中打开服务端口 三、 在HBuilder创建Uni-App项目&#xff0c;并与微信小程序开发工具进行交互预览测试 四、 发布Uni-App项目 五、 微信线上发布运行 …
阅读更多...
PXE和kickstart无人值守安装

PXE和kickstart无人值守安装

PXE高效批量网络装机 引言 1.系统装机的引导方式 启动 操作 系统 1.硬盘 2.光驱&#xff08;u盘&#xff09; 3.网络启动 pxe 重装系统&#xff1f; 在已有操作系统 新到货了一台服务器&#xff0c; 装操作系统 系统镜像 u盘 光盘 pe&#xff1a; 小型的 操作系统 在操…
阅读更多...
（一）SpringBoot3---尚硅谷总结

（一）SpringBoot3---尚硅谷总结

示例Demo&#xff1a; 1、我们先来创建一个空工程&#xff1a; 2、我们通过Maven来创建一个Module&#xff1a; JDK版本需要选择17以及以上&#xff0c;如果没有的话你就下载一个&#xff1a; 3、让此Maven项目继承父项目: 所有的Springboot项目都必须继承自spring-boot-start…
阅读更多...
【PS】PS设计图欣赏、学习、借鉴

【PS】PS设计图欣赏、学习、借鉴

【PS】PS设计图欣赏、学习、借鉴 bilibili萌新PS学习计划&#xff1a;PS教程全套零基础教学视频&#xff08;全套81节全新版本&#xff09;
阅读更多...
编译FFmpeg4.3.1 、x264并移植到Android

编译FFmpeg4.3.1 、x264并移植到Android

1、前言 FFmpeg 既是一款音视频编解码工具&#xff0c;同时也是一组音视频编解码开发套件。 2、准备工作 系统&#xff1a;LinuxNDK&#xff1a;android-ndk-r21b-linux-x86_64.zipFFmpeg&#xff1a;ffmpeg-snapshot.tar.bz2x264&#xff1a;x264 3、下载NDK 在linux环境中…
阅读更多...
window11环境安装jdk17并配置环境变量

window11环境安装jdk17并配置环境变量

目录 一、下载地址二、安装步骤三、环境变量配置四、环境变量配置是否成功的测试 一、下载地址 https://www.oracle.com/java/technologies/downloads/#jdk17-windows 二、安装步骤 双击已下载的 jdk-17_windows-x64_bin.exe 安装包&#xff0c;点击【下一步】&#xff0c;…
阅读更多...
Python-基础篇-类与对象/面向对象程序设计-py脚本

Python-基础篇-类与对象/面向对象程序设计-py脚本

面向对象基础 第一个面向对象 class Cat:def eat(self):print("小猫爱吃鱼")def drink(self):print("小猫要喝水")# 创建猫对象 tom Cat()tom.eat() tom.drink()print(tom)addr id(tom) print("%x" % addr)新建两个猫对象 class Cat:def ea…
阅读更多...
Docker安装与启动

Docker安装与启动

Docker概述 Docker是一个快速交付应用、运行应用的技术&#xff1a; 可以将程序及其依赖、运行环境一起打包为一个镜像&#xff0c;可以迁移到任意Linux操作系统运行时利用沙箱机制形成隔离容器&#xff0c;各个应用互不干扰启动、移除都可以通过一行命令完成&#xff0c;方便…
阅读更多...
力扣精选算法100题——找到字符串中所有字母异位词(滑动窗口专题）

力扣精选算法100题——找到字符串中所有字母异位词(滑动窗口专题）

本题链接&#x1f449;找到字符串中所有字母异位词 第一步&#xff1a;了解题意 给定2个字符串s和p&#xff0c;找到s中所有p的变位词的字串&#xff0c;就是p是"abc",在s串中找到与p串相等的字串&#xff0c;可以位置不同&#xff0c;但是字母必须相同&#xff0c;比…
阅读更多...
ChatGPT 未来学习手册

ChatGPT 未来学习手册

原文&#xff1a;Learn ChatGPT: The Future of Learning 译者&#xff1a;飞龙 协议&#xff1a;CC BY-NC-SA 4.0 “学习 ChatGPT”是任何对人工智能在教育中的作用感兴趣的人必读的书。这本开创性的书探讨了 ChatGPT 的潜力&#xff0c;这是一个强大的人工智能平台&#xff0…
阅读更多...
macOS向ntfs格式的移动硬盘写数据

macOS向ntfs格式的移动硬盘写数据

最近想把日常拍摄的照片从SD存储卡中转存到闲置的移动硬盘中&#xff0c;但是转存的时候发现&#xff0c;mac只能读我硬盘里的东西&#xff0c;无法将数据写入到移动硬盘中&#xff0c;也无法删除移动硬盘的数据。后来在网上查了许久资料&#xff0c;终于可实现mac对移动硬盘写…
阅读更多...
EasyX图形化学习（三）

EasyX图形化学习（三）

1.帧率&#xff1a; 即每秒钟界面刷新次数&#xff0c;下面以60帧为例&#xff1a; 1.数据类型 clock_t&#xff1a; 用来保存时间的数据类型。 2.clock( ) 函数&#xff1a; 用于返回程序运行的时间,无需参数。 3.例子&#xff1a; 先定义所需帧率&#xff1a; const …
阅读更多...
[linux]使用libqrencode库生成二维码数据

[linux]使用libqrencode库生成二维码数据

一、需求 要将一段数据生成为二维码&#xff0c; 二、方案 使用linux标准库&#xff0c;通过libqrencode将需要写入的信息转为二维码图片数据。 三、实现 3.1编写c文件 #include <stdio.h> #include <stdlib.h> #include <qrencode.h> int main() {QRc…
阅读更多...
GO基础进阶篇 (十四)、Http编程

GO基础进阶篇 (十四)、Http编程

Web基础概念 web应用程序 web程序可以提供浏览器访问的程序。Web应用程序通常采用客户端-服务器模型。客户端是用户使用的Web浏览器或其他Web客户端&#xff0c;而服务器是存储和处理数据的远程计算机。 我们能访问到的任何一个页面或资源&#xff0c;都存在于世界的某一个角落…
阅读更多...
C++大学教程（第九版）5.18进制表

C++大学教程（第九版）5.18进制表

目录 题目 代码 运行截图 题目 &#xff08;进制表&#xff09;编写一个程序要求打印一张表&#xff0c;内容是1~256范围内每个十进制数对应的二进制、八进制和十六进制形式。如果还不熟悉这些计数系统&#xff0c;可先阅读附录 D。提示:可以使用流操纵符dec、oct 和 hex来…
阅读更多...
Linux操作系统----gdb调试工具（配实操图）

Linux操作系统----gdb调试工具（配实操图）

绪论​ “不用滞留采花保存&#xff0c;只管往前走去&#xff0c;一路上百花自会盛开。 ——泰戈尔”。本章是Linux工具篇的最后一章。gdb调试工具是我们日常工作中需要掌握的一项重要技能我们需要基本的掌握release和debug的区别以及gdb的调试方法的指令。下一章我们将进入真正…
阅读更多...
最新文章

Copyright @ 2022~2023