红黑树详解--实现插入

矫情吗；* 2024-04-01 14:52 24阅读 0赞

### 红黑树的概念 ###

**红黑树，是一种二叉搜索树**，但在每个结点上增加一个存储位表示结点的颜色，**可以是Red或Black**。 通过 对任何一条从根到叶子的路径上各个结点着色方式的限制，**红黑树确保没有一条路径会比其他路径长出俩 倍**，因而是**近似平衡**的。  
![在这里插入图片描述][097900e5311f41b39a2d06e2cafd73b6.png]

### 红黑树的性质 ###

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

> 推出结论：红黑树的**最短路径**为全是黑色结点，**最长路径为一红一黑交替的路径**。如此即可**保证红黑树的最长路径不超过最短路径的两倍**。

### 红黑树节点的定义 ###

//与AVL树差不多，多了节点的颜色，用枚举定义;
    enum Color
    {
        
    	BLACK,
    	RED
    };
    
    template <class K, class V>
    struct RBTreeNode
    {
        
    	typedef RBTreeNode<K, V> Node;//K-V
    
    	Node* _left;
    	Node* _right;
    	Node* _parent;//方便插入时调整;
    	pair<K, V> _kv;
    	Color _color;
    
    
    	RBTreeNode(const pair<K, V> kv)
    		:_left(nullptr)
    		,_right(nullptr)
    		,_parent(nullptr)
    		//,_data(data)
    		,_kv(kv)
    		,_color(RED)
    	{
        }
    };

> 在这里**结点颜色默认设置为红色**，是为了**方便后续插入**，在保证红黑树性质的情况下，通过插**入红色结点可以更好的保证性质四不被破坏**，而如果插入黑色结点，那么保证每条路径的黑色结点数量相等操作将非常繁琐。

### 红黑树的结构 ###

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

> STL中的红黑树其实还有个头结点，左连min，右连max;我们简单学习，不引入了:
> 
> ![在这里插入图片描述][323a5dc4703246bf8ada43a99c57bd2d.png]

### 红黑树的插入操作 ###

*  黑树是在**二叉搜索树的基础上加上其平衡限制条件(RB)**，因此红黑树的插入可分为两步:

1.  **按照二叉搜索的树规则插入**新节点;
2.  **按照红黑树规则调整**节点;

#### 情况1 ####

![在这里插入图片描述][61ff305f138249eb8fa7aa1f35a6cc7f.png]

**将p,u改为黑，g改为红，然后把g当成cur**，**继续向上调整**。

#### 情况2 ####

![在这里插入图片描述][eb9bae7d93514b80bfd9fe35098e109f.png]

此时如果cur在p左侧（**如上图**），那就对g**右单旋**转+swap p和g的颜色

此时如果cur在p右侧(**想象cur和c交换了位置**),那就是先对p左单旋（就转换为了上一种需要单旋的情况），再对g右单旋的 **左右双旋**，再调整旋转后的颜色即完成，break;

> 以上情况是p再g的左侧情况，p再g的右侧情况同理，只是uncle和parent的位置左右变换+旋转方向的变换，一个道理！
> 
> 这两个情况满足了红黑树的所有特点，不信的可以仔细画图分析，注意，情况2可能是情况1发生以后，向上调整得到的，需要两次结合判断黑色节点数相不相同;

#### 插入代码 ####

bool Insert(pair<K,V>& kv)
        {
        
            if (!_root) {
        
                _root = new Node(kv);
                _root->_color = BLACK;
                return true;
            }
    
            Node* cur = _root;
            Node* parent = cur;
    
            while (cur)
            {
        
                if (cur->_kv.first > kv.first) {
        
                    parent = cur;
                    cur = cur->_left;
                }
                else if (cur->_kv.first < kv.first) {
        
                    parent = cur;
                    cur = cur->_right;
                }
                else return false; //数据冗余;
            }
    
            cur = new Node(kv);
            cur->_parent = parent;
    
            if (parent->_kv.first<kv.first) {
        
                parent->_right = cur;
            }
            else {
        
                parent->_left = cur;
            }
    
            //调整
            while (parent && parent->_color == RED)//父节点为红才需要调整;
            {
        
                //由于parent存在且颜色为红，故panret一定不为根 --》那么grandfather一定存在
                
                Node* grandparent = parent->_parent; 
                Node* uncle;
                if (grandparent->_left == parent) {
        //牵扯旋转方向
                   uncle = grandparent->_right;
                   //只变色:1.p u存在且为红，g为黑;--> p u变黑g变红，向上调整;
                   if (uncle&&uncle->_color == RED) {
        
                       parent->_color = BLACK;
                       uncle->_color = BLACK;
                       grandparent->_color = RED;
    
                       //向上调整;
                       cur = grandparent;//红的子root
                       parent = cur->_parent;//用于while进一步判断
    
                   }
                   else {
        //2单旋+变色  uncle不存在or为黑
                       if (parent->_left == cur) {
        
                           RotateR(grandparent);
                           grandparent->_color = RED;
                           parent->_color = BLACK;
                           cur->_color = RED;
                       }
                       else {
        //3双旋+变色
                           RotateL(parent);
                           RotateR(grandparent);
                           grandparent->_color = RED;
                           parent->_color = RED;
                           cur->_color = BLACK;                   
                       }
    
                       break;//直接满足性质了 break；
                   }
    
                }
                else{
        
                   uncle = grandparent->_left;
                   if (uncle && uncle->_color == RED)//case 1
                   {
        
                       parent->_color = BLACK;
                       uncle->_color = BLACK;
                       grandparent->_color = RED;
                       //向上调整;
                       cur = grandparent;
                       parent = cur->_parent;
                       
                   }
                   else {
        
                       if (parent->_right == cur) {
        //case2 单xuan
                           RotateL(grandparent);
                           parent->_color = BLACK;
                           cur->_color = RED;
                           grandparent->_color = RED;
                       }
                       else {
        //case2 双xuan
                           RotateR(parent);
                           RotateL(grandparent);
    
                           grandparent->_color = RED;
                           parent->_color = RED;
                           cur->_color = BLACK;
                       }
                       break;
                   }
                    
                }
    
            
            }
    
            _root->_color = BLACK;//不论如何，直接将根节点颜色置为黑色 因为有种跳的过程中 根会变红!
            return true;
        }

### 红黑树的验证 ###

//验证根节点是黑色
    	bool IsRBTree()
    	{
        
    		if (_root == nullptr)//空树也是红黑树
    			return true;
    		//检测性质二：根节点是黑色
    		if (_root->_color != BLACK)
    		{
        
    			cout << "违反规则二，根结点为红色" << endl;
    			return false;
    		}
    		
    	}
    	
    	//验证两个红色节点不能挨着
    	bool Check_RED_RED(Node* root)
    	{
        
    		//由于在调用函数中已经检测了根节点的合法性
    		//故此处的root结点必不为红色
    		if (root == nullptr)
    			return true;
    		if (root->_color == RED && root->_parent->_color == RED)
    		{
        
    			cout << "违反规则三，有连续的红色结点" << endl;
    			return false;
    		}
    		return Check_RED_RED(root->_left) && Check_RED_RED(root->_right);
    	}
    
    	
    	//验证每条路径黑色节点数相同;
    	bool Check_BlackNum(Node* root, int benchMark, int blacknum)
    	{
        
    		if (root == nullptr)//到空结点，此时blacknum为该条路径的黑色结点数量
    		{
        
    			if (blacknum == benchMark)
    				return true;
    			else
    				return false;
    		}
    		if (root->_color == BLACK)
    			blacknum++;
    		return Check_BlackNum(root->_left, benchMark, blacknum)&&Check_BlackNum(root->_right, benchMark, blacknum);
    	}
    	
    	//前几个函数的综合;
    	bool IsRBTree()
    	{
        
    		if (_root == nullptr)//空树也是红黑树
    			return true;
    		//检测性质二：根节点是黑色
    		if (_root->_color != BLACK)
    		{
        
    			cout << "违反规则二，根结点为红色" << endl;
    			return false;
    		}
    		//计算最左路径上黑色结点的数量作为基准值
    		int benchMark = 0;
    		Node* cur = _root;
    		while (cur)
    		{
        
    			if (cur->_color == BLACK)
    				benchMark++;
    			cur = cur->_left;
    		}
    		int blacknum = 0;
    		return Check_RED_RED(_root) && Check_BlackNum(_root, benchMark, blacknum);
    	}

### 红黑树和AVL树比较 ###

红黑树与AVL树都是平衡的二叉树（一个相对平衡不超过2倍，一个绝对平衡）：

*  AVL树是严格平衡的，而红黑树是近似平衡的\\
 *  AVL树和红黑树的查找时间复杂度都是O(log2N)
 *  但是:由于**红黑树的设计使得旋转次数更少，因此在增删过程中性能较优**

这也是stl中的map和set底层封装红黑树的原因，同事操作系统内核中的很多设计也都是封装红黑树;eg:epoll的fd红黑树节点，就绪以后快速找到，回调去就绪链表；

[097900e5311f41b39a2d06e2cafd73b6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/19f9e6dd5da54c60b63b32b11aac0e50.png
[323a5dc4703246bf8ada43a99c57bd2d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/979c3120270b4fbc905f14df1b4d98a7.png
[61ff305f138249eb8fa7aa1f35a6cc7f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/e433159f25924dbd971bc42133227767.png
[eb9bae7d93514b80bfd9fe35098e109f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/c5a9985273844b3e8d07431ba0b8b273.png