教你轻松理解红黑树的实现及原理

叁歲伎倆 2022-10-15 12:57 310阅读 0赞

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

### 轻松理解红黑树 ###

*  目录:
 *   *  一.红黑树的原理&性质
     *  二.红黑树的结构&节点封装
     *   *  1.结构理解
         *  2.节点封装
     *  三.红黑树的插入操作
     *   *  1.判断是否存在根节点
         *  2.将对应的节点挂到树上
         *  3.判断是否存在红色连续节点
         *   *  (1) 单链存在红色连续
             *  (2) 存在黑色uncle节点的红色连续
             *  (3) 左子树 和 左子树的右子树存在红色连续
             *  (4) 存在红色uncle节点的红色连续
     *  四.左旋&右旋
     *   *  1.左旋操作
         *  2.右旋操作
     *  五.获取\_header对应的最左最右节点
     *   *  1.获取最左节点
         *  2.获取最右节点
     *  六.中序遍历打印值
     *  七.判断是否是红黑树
     *  八.红黑树&AVL树的比较

# 目录: #

## 一.红黑树的原理&性质 ##

>  红黑树，是一种二叉搜索树,在每个对应的节点上面都存储着一种节点的颜色,可以是BLACK或者RED这两种,通过对于每个节点着色方式的限制,来接近平衡.   
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70]

**性质:**

>  1.每个节点不是红色就是黑色  
> ~  
> 2.根节点必须是黑色  
> ~  
> 3.如果一个节点是红色,其对应的两个子节点是黑色的  
> ~  
> 4.对于每个节点,从该节点到后代的叶子节点的**简单路径**,均包含相同的黑色节点  
> ~  
> 5.每一个叶子节点都是黑色的(这里是NIL空节点)

## 二.红黑树的结构&节点封装 ##

### 1.结构理解 ###

>  这就是红黑树底层的结构,在根节点上面有一个\_header节点,这个\_header节点和根节点互相指向,且指向最小的节点和最大的节点,这个节点的作用主要是后续能够简单的实现关联性容器,我们现在只要理解底层的结构是这样的,在创建节点的时候这样创建就可以了.   
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 1]

### 2.节点封装 ###

在要插入一个节点的时候,首先运用上面的构造函数对这个节点进行构建,将对应的值进行赋予,然后再将其链接在对应的叶子节点的位置.

enum COLOR{ 		//首先定义枚举储存对应的颜色
    
    	BLACK,
    	RED
    };
    
    template <class K, class V>
    struct RBNode{ 		//运用模板,在内部将每个节点所需要的数据进行初始化
    
    	RBNode<K, V>* _parent;	//对应的父节点指向
    	RBNode<K, V>* _left;	//左子树
    	RBNode<K, V>* _right;	//右子树
    
    	pair<K, V> _kv;		//对应的kv键值对
    
    	COLOR _color;		//枚举的颜色
    
    	RBNode(const pair<K, V>& kv = pair<K, V>())		//对于一个节点的构造函数
    		:_parent(nullptr)		//对应的节点置空
    		, _left(nullptr)
    		, _right(nullptr)
    		, _kv(kv)		//kv直接初始化成kv
    		, _color(RED)	//对于构造出的节点直接变成红色,这里是一个比较重要的知识点,在下面会讲到
    	{ }
    };

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

### 1.判断是否存在根节点 ###

>  在插入一个节点的时候,我们首先对于插入节点的位置进行判断,判断它是否不存在根节点,不存在则直接重新创建即可.

template<class K, class V>
    class RBTree{ 
    
    public:
    	typedef RBNode<K, V> Node;	//定义别名
    
    	RBTree()		//构造函数
    		:_header(new Node)	//调用上面的构造函数初始化一个新的树
    	{ 
    		//创建空树
    		_header->_left = _header->_right = _header;	//将其和_header节点进行相互指向
    	}
    
    	bool insert(const pair<K, V>& kv){ 		//插入函数
    
    		//1.搜索树的插入
    		if (_header->_parent == nullptr){ 		//如果不存在对应的根节点
    
    			//创建对应的根节点
    			Node* root = new Node(kv);
    			
    			//然后对_header和root所包含的节点进行相互的指向
    			_header->_parent = root;
    			root->_parent = _header;
    			_header->_left = _header->_right = root;
    
    			//改变根节点的颜色
    			root->_color = BLACK;
    			return true;	
    		}

### 2.将对应的节点挂到树上 ###

>  如果要插入的红黑树不为空的话,则要进行遍历,在红黑树最底层的叶子节点上将要进行插入的节点挂上. !! root节点和\_header节点互为父节点 !!

Node* cur = _header->_parent;	//创建cur节点指向对应的root节点
    		Node* parent = nullptr;		
    		while (cur){ 		//当对应的根节点存在的时候
    
    			parent = cur;		//让parent指向根节点
    
    			if (cur->_kv.first == kv.first){ 	//如果存在对应的值,直接错误
    
    				return false;
    			}
    			else if (cur->_kv.first > kv.first){   //如果大于对应的节点数值
    
    				cur = cur->_left;		//则向左边遍历
    			}
    			else{ 
    				cur = cur->_right;		//反之,则向右边进行遍历
    			}
    		}
    		//创建要插入的节点
    		cur = new Node(kv);	
    		//找到要存放的节点的位置后,进行大小判断看挂在左边还是挂在右边
    		if (parent->_kv.first > cur->_kv.first)	
    			parent->_left = cur;
    		else
    			parent->_right = cur;
    		cur->_parent = parent;	//让其节点和对应的父节点进行指向

### 3.判断是否存在红色连续节点 ###

>  当元素插入以后,我们就要对其中存在的节点颜色来进行判断了,存在四种情况的节点插入:我们下面一 一分析

#### (1) 单链存在红色连续 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 2]

#### (2) 存在黑色uncle节点的红色连续 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 3]

#### (3) 左子树 和 左子树的右子树存在红色连续 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 4]

#### (4) 存在红色uncle节点的红色连续 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 5]

>  上面的四种情况我们都发现是存在于左子树上面所发生的情况,右子树还有四种情况,当然其执行的过程是和左子树一样的,只不过是镜像的关系,大家理解理解就好了!

//2.修改颜色或者调整结构(看有无红色连续节点)
    		while (cur != _header->_parent && cur->_parent->_color == RED){ 
    
    			parent = cur->_parent;		//创建对应的节点表示
    			Node* gfather = parent->_parent;
    //========下面是存在于左子树的情况========
    			if (gfather->_left == parent){ 
    
    				Node* uncle = gfather->_right;
    //========情况4========
    				if (uncle&&uncle->_color == RED){ 
    
    					parent->_color = uncle->_color = BLACK;	//直接改色
    					gfather->_color = RED;
    					//继续更新
    					cur = gfather;
    				}
    				else{ 
    
    					//判断是否是双旋的场景
    					if (cur == parent->_right){ 
    //========情况3========
    						//左旋
    						RotateL(parent);
    						//交换cur,parent指向,退化成右旋的场景
    						swap(cur, parent);
    					}
    //========情况1========
    					//右旋
    					RotateR(gfather);
    					parent->_color = BLACK;
    					gfather->_color = RED;
    					break;
    				}
    			}
    //========下面的是存在于右子树上面的情况========具体过程和左子树类似
    			else{ 
    				//gfather->right=parent
    				Node* uncle = gfather->_left;
    				if (uncle&&uncle->_color == RED){ 
    
    					parent->_color = uncle->_color = BLACK;
    					gfather->_color = RED;
    					cur = gfather;
    				}
    				else{ 
    
    					if (cur == parent->_left){ 
    
    						RotateR(parent);
    						swap(cur, parent);
    					}
    					RotateL(gfather);
    
    					parent->_color = BLACK;
    					gfather->_color = RED;
    					break;
    				}
    			}
    		}
    		//!!!!!根节点颜色改为黑色!!!!!
    		_header->_parent->_color = BLACK;
    		
    		//更新header的左右指向
    //因为_header节点指向的是最小节点和最大节点,所以我们在这里要利用函数来找到最小节点和最大节点
    		_header->_left = leftMost();	
    		_header->_right = rightMost();
    	}

## 四.左旋&右旋 ##

>  对于左旋和右旋的理解就比较简单了,我们可以参考之前的[AVL数左右旋][AVL]来理解.

### 1.左旋操作 ###

void RotateL(Node* parent){ 
    
    		Node* subR = parent->_right;
    		Node* subRL = subR->_left;
    
    		subR->_left = parent;
    		parent->_right = subRL;
    		if (subRL)
    			subRL->_parent = parent;
    		//判断根节点
    		if (parent == _header->_parent){ 
    
    			_header->_parent = subR;
    			subR->_parent = _header;
    		}
    		else{ 
    
    			Node* pparent = parent->_parent;
    			if (pparent->_left == parent)
    				pparent->_left = subR;
    			else
    				pparent->_right = subR;
    			subR->_parent = pparent;
    		}
    		parent->_parent = subR;
    	}

### 2.右旋操作 ###

void RotateR(Node* parent){ 
    
    		Node* subL = parent->_left;
    		Node* subLR = subL->_right;
    
    		subL->_right = parent;
    		parent->_left = subLR;
    		if (subLR)
    			subLR->_parent = parent;
    
    		//判断根
    		if (parent == _header->_parent){ 
    
    			_header->_parent = subL;
    			subL->_parent = _header;
    		}
    		else{ 
    
    			Node* pparent = parent->_parent;
    			if (pparent->_left == parent)
    				pparent->_left = subL;
    			else
    				pparent->_right = subL;
    			subL->_parent = pparent;
    		}
    		parent->_parent = subL;
    	}

## 五.获取\_header对应的最左最右节点 ##

### 1.获取最左节点 ###

Node* leftMost(){ 
    
    		Node* cur = _header->_parent;	//定义根节点
    		while (cur&&cur->_left){ 		//根节点存在且存在左子树的情况下
    
    			cur = cur->_left;	//向左遍历
    		}
    		return cur;	//返回最终最左边的
    	}

### 2.获取最右节点 ###

Node* rightMost(){ 
    
    		Node* cur = _header->_parent;	//定义根节点
    		while (cur&&cur->_right){ 	//根节点存在且存在右子树
    
    			cur = cur->_right;		//向右遍历
    		}
    		return cur;	//返回最右边的节点
    	}

## 六.中序遍历打印值 ##

void inorder(){ 
    
    		_inorder(_header->_parent);		//调用函数
    		cout << endl;
    	}
    
    	void _inorder(Node* root){ 	//获取根节点
    
    		if (root){ 	//存在时
    
    			_inorder(root->_left);		//递归
    			cout << root->_kv.first << " ";	//输出对应的Key值
    			_inorder(root->_right);		//递归
    		}
    	}

## 七.判断是否是红黑树 ##

> 要判断是否是红黑树,我们就要按照下面这三个条件来进行判断  
>  1.根: 黑色  
> 2.每条路径的给色数目相同  
> 3.红色的不能连续

**解决问题步骤:**  
\----1.首先判断根节点是否是黑色的  
\----2.统计最左的路径的黑色节点的个数  
\----3.对每个路径进行遍历,看是否满足条件  
\----4.判断是否有连续的红色节点存在

bool isBalance(){ 
    
    		if (_header->_parent == nullptr)	//判断根节点是否存在
    			return true;
    
    		Node* root = _header->_parent;
    		if (root->_color == RED)	//1.根是否是黑色的
    			return false;
    		//统计一条路径上黑色节点的个数
    		int bCount = 0;
    		Node* cur = root;
    		while (cur){ 
    
    			if (cur->_color == BLACK)
    				++bCount;
    			cur = cur->_left;
    		}
    
    		//遍历每一条路径
    		int curBCount = 0;
    		return _isBalance(root, bCount, curBCount);		//调用下面的函数
    	}
    
    	bool _isBalance(Node* root, int& bCount, int curBCount){ 	//调用函数的时候,将上面统计的值传入
    
    		//当root为空,则一条路径遍历结束
    		if (root == nullptr){ 
    
    			//判断黑色节点个数是否相同
    			if (curBCount != bCount)
    				return false;
    			else
    				return true;
    		}
    
    		//判断节点是否为黑色
    		if (root->_color == BLACK)
    			++curBCount;
    
    		//判断是否存在红色连续的节点
    		if (root->_parent&&root->_color == RED
    			&&root->_parent->_color == RED)
    		{ 
    			cout << "data: " << root->_kv.first << endl;
    			return false;
    		}
    
    		return _isBalance(root->_left, bCount, curBCount)	//递归遍历
    			&& _isBalance(root->_right, bCount, curBCount);
    	}
    	
    private:
    	Node* _header;	
    };

## 八.红黑树&AVL树的比较 ##

<table> 
 <thead> 
  <tr> 
   <th>功能</th> 
   <th>RBTree</th> 
   <th>AVL</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>查找节点</td> 
   <td>效率较低</td> 
   <td>因为更平衡,所以效率较高</td> 
  </tr> 
  <tr> 
   <td>插入节点</td> 
   <td><strong>O(1)</strong></td> 
   <td><strong>O(1)</strong></td> 
  </tr> 
  <tr> 
   <td>删除节点</td> 
   <td>最多需要三次旋转来满足条件,故为:<strong>O(1)</strong></td> 
   <td>需要从根节点来遍历,维持所有的平衡,故为:<strong>O(logN)</strong></td> 
  </tr> 
 </tbody> 
</table>

这就是对于红黑树的简单理解,后续还有红黑树实现map&set和迭代器的相关知识.

[20210525170051281.png]: /images/20221014/5b095f18cdb04a16bffc93356dabdb05.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70]: /images/20221014/5f50ed94d04f4f6abaf67b45a0627668.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 1]: /images/20221014/bfcbc9799a5f44529eccd462e2f53c4e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 2]: /images/20221014/f033f3c09ec949d3b98c08991dbe9d1a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 3]: /images/20221014/08ffea88c1b646ce91eef6e8a2abf27c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 4]: /images/20221014/90088dd8e9d24efda6aae58f942a25c4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 5]: /images/20221014/8fcaa77b8e87464e9d355aa1b32b814d.png
[AVL]: https://blog.csdn.net/weixin_46554582/article/details/116799522