【C++】AVL树和红黑树的插入

拼搏现实的明天。 2024-04-21 19:14 6阅读 0赞

时间过的好快，我也修炼到红黑树了……

![在这里插入图片描述][c872c5ab24f44a6096f661c1155b8a8b.jpeg_pic_center]

#### 文章目录 ####

*  一、AVL树
 *   *  1.AVL树的介绍
     *  2.AVL树插入的思路
     *  3.AVL树插入的代码（死亡三部曲）
     *  4.AVL树的验证
 *  二、红黑树
 *   *  1.红黑树的介绍
     *  2.红黑树插入的思路
     *  3.红黑树插入的代码（关键是uncle）
     *  4.红黑树的验证

--------------------

## 一、AVL树 ##

### 1.AVL树的介绍 ###

1.  
虽然二叉搜索树的搜索效率很高，当搜索树接近满二叉树时，搜索效率可以达到logN，但是如果数据是有序的，则二叉搜索树会退化为单支树，搜索效率和普通的序列式容器相同了就，所以在搜索树的基础上，两位俄罗斯数学家研究出了平衡搜索树。

2.  
平衡搜索树要求任一结点的左右子树的高度差不超过|1|，这个高度差简称为平衡因子，balance factor，计算方式为右子树高度减左子树的高度，所以在平衡搜索树里面任意的一个结点的平衡因子都是0或1或-1，不会出现2或-2的情况，因为平衡搜索树要求左右子树高度差不超过|1|。

![在这里插入图片描述][cfb653e565f14fdfaf8e35a52ed96bab.png]  
3.  
如果我们保证了一棵搜索树是平衡搜索树，那他的价值将会无限放大，因为他的左右子树高度极其接近于平衡，他的效率我们可以看作是以2为低的N的对数，所以假设有10亿个数，用vector或list查找的次数最坏就是10亿次，但如果我们用平衡搜索树查找最坏仅仅只是30次，效率之差天壤地别。但该如何将一棵普通的搜索树调整为平衡搜索树呢？实际上需要不断连续的旋转进行调平衡，调整过程正是今天的主题，也就是搜索树**旋转调平衡**为平衡搜索树的过程。

### 2.AVL树插入的思路 ###

1.  
在研究AVL树结点插入之前，我们先来看看AVL树结点的定义，在AVL树中结点不再是二叉链结构了，而是变为三叉链结构，这里需要解释一下为什么，因为在某棵子树插入结点之后，如果这棵子树的高度发生了变化，那么子树的上面的根节点的平衡因子是需要进行调整的，而且得一路向上进行调整，如果不用三叉链结构，我们就只能通过parent和cur迭代的方式进行向上调整，过于繁琐，所以在这个地方AVL树结点引入了三叉链结构，三叉链结构天生就可以打通子树和根结点之间的关联，在处理平衡因子上带来很大的优势。

![在这里插入图片描述][54c5d317e2b645bba56b56b5ea23de2f.png]  
2.  
每一个结点都应该有平衡因子，当新增结点之后平衡因子变为2或-2时，就已经出问题了，平衡因子为2或-2的结点所在子树已经不满足AVL树的性质了，此时就需要进行旋转调平衡，那么这时候平衡因子也就不必继续向上进行调整了，我们需要处理这棵子树将其重新调整为AVL树。

template <class K, class V>
    struct AVLTreeNode
    {
        
    	pair<K, V> _kv;
    	AVLTreeNode<K, V>* _left;
    	AVLTreeNode<K, V>* _right;
    	AVLTreeNode<K, V>* _parent;
    
    	int _bf;// balance factor
    	AVLTreeNode(const pair<K, V>& kv)
    		:_kv(kv)
    		,_left(nullptr)
    		,_right(nullptr)
    		,_parent(nullptr)
    		,_bf(0)
    	{
        }
    };

3.  
AVL树插入的步骤共分为3步，**第一步和搜索树规则相同**，还是迭代找到插入结点的位置，进行结点的插入。**第二步更新平衡因子**，如果平衡因子出现2或-2时更新结束，我们需要对异常平衡因子对应结点所在的子树进行旋转调平衡，也有可能平衡因子始终并未出现异常，仅仅只是一直向上更新平衡因子到根节点为止，更新的过程中整条路径的结点的平衡因子均未出现异常，我们就无须进行旋转调平衡处理。**第三步对异常平衡因子所在结点子树进行旋转调平衡处理**，调平衡的同时我们也要调平衡因子，让平衡因子不再异常。当然，如果平衡因子并未异常，那么插入结点就成功，否则就必须得进行旋转调平衡处理，旋转调平衡这里共分为左单旋，右单旋，左右双旋，右左双旋四种情况，下面我会对各种情况进行详细的讲解。

4.  
迭代找插入结点位置进行插入我就不讲解了，如果有不懂的，可以去看前面二叉搜索树那一节的文章，在这里先来讲一讲**更新平衡因子**的过程。  
其实更新的过程也比较简单，能出现的情况也就三种，一种是在向上更新的过程中平衡因子异常了，我们结束更新，对异常的这棵子树进行旋转调平衡处理（如左图所示）。另一种就是在向上更新的过程中平衡因子一直没有出现异常，那么我们更新到根节点就停止，此时也不需要旋转调平衡处理，直接在AVL树的insert函数里return true即可。最后一种就是不用向上更新，为啥不用向上更新呢？比如原来某棵树结点的平衡因子是1或-1，在新增结点过后，平衡因子变为了0，此时还需要向上更新吗？当然不用了，因为这棵子树的高度没有变化呀！向上更新啥嘛，子树高度不变，上面树的高度肯定也不变啊，只要高度不变，我们就无需向上更新平衡因子。

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

5.  
下面我们来谈谈AVL树的重头戏，也就是旋转调平衡的过程，先来看看左单旋和右单旋。  
在新增结点之前，这棵树必须得是AVL树或AVL子树，在插入构建AVL树的过程中我们处理的就是非AVL树的情况，所以在新增结点之前，子树一定是AVL树，所以如果9是新增结点的话，那么8的左边就一定是空，这样才会引发平衡因子异常。但如果8的左边不是空，而是一棵子树，那么9就不可能是新增结点，因为如果是子树8的右边肯定也是一棵子树，9应该是右子树下边新增的结点，如果你要真画出来所有具体的图，那这里的情况会非常的多，但其实无论你的8左边是否为空，或者8的右子树根新增结点还是右子树的下面新增了一个结点，最后的情况都是一样的，你的新增结点引发了parent7的平衡因子异常，7的平衡因子变为2了，那就说明7的右子树太高了，所以我们旋转将7的右边连接到subRL上，subR的左链接到parent上，subR的parent链接到原来parent的parent上面去，这样我们就把高度降下来了，789的平衡因子都重新调整为0，这棵子树就重新调整为AVL树，所有的平衡因子都正常了。

![在这里插入图片描述][dc056daa935a4445b3362a2ace532e4b.png]  
右单旋的情况和左单旋类似，是由于新增结点插入到parent的左边，然后在向上迭代更新平衡因子的过程中parent的平衡因子变为了-2，那就是parent的左子树太高了，我们需要降低这棵子树的高度，那就进行右单旋，将parent的左链接到subLR上subL的右链接到parent上，subL的parent链接到parent的parent上面去。  
这里我在多说一句，下面我们画的图是逻辑抽象图，而不是具体的情况对应的图，因为具体的情况的图画不完的，就拿第一张图来说，7的左边可能挂了结点或子树，8的左右两边都有可能挂着结点或子树，但无论你挂了多少结点或子树，在新增结点之前你这棵整体的子树一定一定一定是AVL树，那么只要在新增结点之后，更新平衡因子过程中parent的平衡因子变为2，那就需要进行左单旋来降高度，只要降了高度，789的平衡因子就都会变成0，这一点通过9为新增结点，8和7的左边为空这样的情况就可以说明。  
![在这里插入图片描述][4db5570d9ee1440abe7f16cb9a316d5b.png]  
6.  
左右双旋和右左双旋有点麻烦，因为他们的调平衡因子过程较为复杂，而左单旋和右单旋的调平衡因子过程非常简单，只需要将parent，subL/subR的平衡因子调为0就可以，但每个双旋的平衡因子都有3种情况，所以比较繁琐。

下面第一张图片代表的场景是右左双旋的场景，三种情况虽然都是右左双旋，但是每种情况的平衡因子的处理是不一样的，如果是第一行的场景，则只需要把parent和subR的平衡因子都置为0即可，但第如果是第二行的情况，我们在3的左子树新增结点时出现了折线型的平衡因子为2的问题，此时依旧是右左双旋，但是平衡因子的调节就有些不一样了，subRL的平衡因子变为0，因为subRL做根，parent在左旋时链接了新增在3左子树的结点，所以parent的平衡因子变为0，subR链接到3的右边也就是空，那么subR的平衡因子就被调整为1.当情况是第三行时，调节平衡因子如图所示，这里不再过多赘述，双旋的平衡因子调节主要还是跟着图走。

补充一点：右左双旋时，先以subR为轴进行左单旋，然后再以parent为轴进行右单旋。在调节平衡因子时，我们需要判断subRL是自己新增还是左子树新增或是右子树新增，这里的判断方式通过subRL的平衡因子就可以分辨出来，如果是0，那就是自己新增，如果是1那就是右子树新增，如果是-1那就是左子树新增。通过这三种情况，分别对子树的平衡因子进行调整处理。  
![在这里插入图片描述][1e2fee45dc3043cfa829243eab70ecb5.png]

当情况变为左折线式的平衡因子异常问题，我们就需要采用左右双旋的方式进行解决，先以subL为轴点进行左单旋，再以parent为轴进行右单旋，这样就完成了旋转调平衡的过程。与右左双旋相同的是对于平衡因子的调节同样要分为三种情况，这里不再继续赘述，下面图片阐述的很清楚。

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

### 3.AVL树插入的代码（死亡三部曲） ###

1.  
**第一步：插入结点并完成结点的链接过程**  
这个步骤的实现和二叉搜索树一样，如果\_root是空，我们就new一个结点，把结点地址给到\_root，让\_root指向这个结点，这个结点就是AVL树的根节点，然后直接返回true。如果\_root不是空，那就根据搜索树结构特征，用while循环向下迭代找插入结点的位置，注意向下迭代找插入结点的过程中，不仅仅只需要一个cur指针，如果仅有cur一个指针，我们是无法将new出来的结点链接到树上面的，因为cur只是一个局部变量，无法改变函数外面树的结点的链接关系，所以我们还需要一个局部变量parent，在cur向下迭代之前把其地址给到parent，那么等到cur迭代到正确插入结点的位置时，我们通过局部指针parent，就能操纵外面树对应根节点的左右指针，但外面的根节点还是一样，我们无法通过parent操纵，然后把new出来的结点地址给到cur，再把cur链接到parent上，此时不能通过parent的左右哪个为空，我们就把cur链接到哪个上面去，因为parent的左右都有可能为空，所以还需要进行cur里面的kv键值对和parent里面的kv键值对的first之间再进行一次比较，这样才能判断出cur究竟要插入到parent的左右哪个位置上去。插入结点之后，还有一件事需要去做，因为我们的AVL树结点是三叉链结构，所以cur结点里的\_parent指针还需要指定它的指向，否则cur结点没有父亲了，所以处理完parent的左右指针过后，还需要再处理一次cur的\_parent指针。

2.  
**第二步：更新平衡因子**  
更新平衡因子的过程，在上面思路部分我也做了详细的说明，下面就是将思路转换为代码的具体实现。首先需要解决的问题是如何更新平衡因子？如果插入的结点是parent的左，那就是parent的左树高了，parent的平衡因子就应该- -，如果插入的结点是parent的右，parent的平衡因子就应该++，此时就需要看parent平衡因子的值了，如果是1或-1，则继续向上让cur和parent迭代更新平衡因子，如果是0则说明parent子树的高度没有改变无须向上更新，就该停下来了。其他情况就是如果平衡因子出现2或-2则也该停下来了，因为我们要对其进行"治疗"，也就是旋转调平衡的过程，通过parent和cur的平衡因子的不同，又可以细分为4种"治疗手段"。最后如果cur更新到\_root的位置就需要跳出循环了，parent此时为nullptr结束循环。

template <class K, class V>
    class AVLTree
    {
        
    	typedef AVLTreeNode<K, V> Node;
    public:
    	bool Insert(const pair<K, V>& kv)
    	{
        
    		//两步:1.找插入结点位置进行结点插入 2.更新平衡因子
    		if (_root == nullptr)
    		{
        
    			_root = new Node(kv);
    		}
    		//1.找插入结点位置进行结点的插入
    		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 > cur->_kv.first)
    		{
        
    			parent->_left = cur;
    			cur->_parent = parent;
    		}
    		else
    		{
        
    			parent->_right = cur;
    			cur->_parent = parent;
    		}
    
    		//2.更新平衡因子
    		while (parent)//最极端场景就是更新到根节点位置
    		{
        
    			if (cur == parent->_left)
    				parent->_bf--;
    			else
    				parent->_bf++;
    
    			if (parent->_bf == 0)
    				break;
    
    			if (parent->_bf == 1 || parent->_bf == -1)
    			{
        
    				cur = parent;
    				parent = cur->_parent;
    			}
    			else if (parent->_bf == 2 || parent->_bf == -2)
    			{
        
    				//旋转调平衡
    				if (parent->_bf == 2 && cur->_bf == 1)
    				{
        
    					//左单旋
    					RotateL(parent);
    				}
    				else if (parent->_bf == -2 && cur->_bf == -1)
    				{
        
    					//右单旋
    					RotateR(parent);
    				}
    				else if (parent->_bf == 2 && cur->_bf == -1)
    				{
        
    					//右左双旋
    					RotateRL(parent);
    				}
    				else if (parent->_bf == -2 && cur->_bf == 1)
    				{
        
    					//左右双旋
    					RotateLR(parent);
    				}
    				else
    				{
        
    					//若出现不可预料的情况，直接断死
    					assert(false);
    				}
    				break;//旋转结束，跳出循环
    			}
    			else//若出现不可预料的情况，直接断死
    			{
        
    				assert(false);
    			}
    		}
    	}

3.  
**第三步：旋转调平衡**  
在调平衡这个地方，一定要注意对着图来进行操作，否则很容易出问题。  
**如果是单旋的代码：** 需要注意的就是三叉链这种特殊结构的处理，他就像是双向循环链表一样，你新链接结点时，不仅要处理新节点的左和右指针指向，新节点左右结点的一个指针指向你也要处理呀，所以代码对数就应该是两对儿：新节点的左指针指向，左指针指向结点的右指针指向。新节点的右指针指向，右指针指向结点的左指针指向。  
在AVL树这里那最多代码对儿数就应该是三对儿（这里只拿左单旋举例子，右单旋类似，反过来即可），parent的\_right指针和subRL的\_parent指针，当然这里需要判断subRL是否存在，如果存在那就需要更改subRL的\_parent指针，不存在就不需要管了。parent的\_parent指针和subR的\_left指针。subR的\_parent指针，和上面那个结点的左或右指针，当然上面可能不存在，那subR就变成了根节点，我们需要更新一下\_root的指向，从原来指向parent更新到现在指向subR结点，如果上面存在那就需要更改上面结点的左或右指针，从原来的指向parent结点到现在指向的subR结点。最后调整一下平衡因子，单旋的平衡因子最好调了，将parent和parent的左或右结点的平衡因子都调成0就OK了。

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

//3.左单旋，右单旋，左右双旋，右左双旋
    	void RotateL(Node* parent)
    	{
        
    		Node* subR = parent->_right;
    		Node* subRL = subR->_left;
    		Node* pParent = parent->_parent;
    
    		//AVL树这样的三叉链结构，调整一个结点对另一个结点的指向，另外一个结点的指向也需要调整指向对面的结点上去，他是双向的。
    
    		parent->_right = subRL;//调整parent向下的指向，下面是有可能调整subRL向上的指向
    		if (subRL)
    			subRL->_parent = parent;
    
    		parent->_parent = subR;//调整parent向上的指向，下面就得调整subR向下的指向
    		subR->_left = parent;
    
    		subR->_parent = pParent;//调整了subR向上的指向，下面就得调整上面对subR的指向。
    		if (pParent == nullptr)
    			_root = subR;//如果parent恰好指向根节点，并且parent指向结点的bf为2或-2，则此时就需要换根结点指针的地址了
    		else
    		{
        
    			if (parent == pParent->_left)
    				pParent->_left = subR;
    			else
    				pParent->_right = subR;
    		}
    
    		//重新调整平衡因子
    		parent->_bf = subR->_bf = 0;
    	}
    	void RotateR(Node* parent)
    	{
        
    		Node* subL = parent->_left;
    		Node* subLR = subL->_right;
    		Node* pParent = parent->_parent;
    
    		parent->_left = subLR;
    		if (subLR)
    			subLR->_parent = parent;
    
    		parent->_parent = subL;
    		subL->_right = parent;
    
    		subL->_parent = pParent;
    		if (pParent == nullptr)
    			_root = subL;
    		else 
    		{
        
    			if (pParent->_left == parent)
    				pParent->_left = subL;
    			else
    				pParent->_right = subL;
    		}
    		
    		//调整平衡因子
    		parent->_bf = subL->_bf = 0;
    	}

**如果是双旋的代码：** 旋转的代码其实并不需要我们怎么写，我们直接复用左右单旋的代码即可，但在传参时要注意轴点的位置变化，拿右左双旋来举例，轴点先为subR后为parent。其实双旋代码的关键在于平衡因子的调整，但只要有图，害，平衡因子的调整算个啥嘛！那不轻轻松松就调节好了？所以在单旋之前先记录一下subRL的平衡因子，否则单旋过后subRL的平衡因子都被处理成0了，我们无法区分调节平衡因子的三种情形了。记录平衡因子之后，我们就可以分三种情况对parent subR subRL的平衡因子进行处理了，处理过后双旋的代码也就结束了。  
**所以在双旋代码这里可以看到，它主要的难点不是旋转，因为旋转我们调用单旋复用代码就可以处理了，真正的难点是在平衡因子的调节这块儿，他又分了三种情况**。

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

void RotateLR(Node* parent)
    	{
        
    		//这里比较难的一个点实际上是双旋之后的平衡因子的调整
    		Node* subL = parent->_left;
    		Node* subLR = subL->_right;
    
    		int bf = subLR->_bf;// 单旋过后，subLR的平衡因子会被改变，提前记录一下平衡因子
    		RotateL(parent->_left);
    		RotateR(parent);
    		if (bf == 0)// subLR本身就是新增
    		{
        
    			subL->_bf = subLR->_bf = parent->_bf = 0;
    		}
    		else if(bf == 1)// subLR的右子树进行新增
    		{
        
    			subL->_bf = -1;
    			subLR->_bf = parent->_bf = 0;
    		}
    		else if (bf == -1)// subLR的左子树进行新增
    		{
        
    			parent->_bf = 1;
    			subLR->_bf = subL->_bf = 0;
    		}
    		else
    		{
        
    			//若出现不可预料的情况，直接断死
    			assert(false);
    		}
    	}
    	void RotateRL(Node* parent)
    	{
        
    		Node* subR = parent->_right;
    		Node* subRL = subR->_left;
    		int bf = subRL->_bf;
    
    		RotateR(parent->_right);
    		RotateL(parent);
    		if (bf == 0)
    		{
        
    			parent->_bf = subR->_bf = subRL->_bf = 0;
    		}
    		else if (bf == 1)
    		{
        
    			parent->_bf = -1;
    			subR->_bf = subRL->_bf = 0;
    		}
    		else if (bf == -1)
    		{
        
    			subR->_bf = 1;
    			parent->_bf = subRL->_bf = 0;
    		}
    		else
    		{
        
    			assert(false);
    		}
    	}

### 4.AVL树的验证 ###

1.  
写完AVL树之后，我们还需要写一个程序对AVL树进行验证，要不然你说你的树是AVL树他就是AVL树啊！万一你写错了呢？所以写完AVL树的插入之后，还需要再对其进行验证，看是否满足AVL树的条件。

2.  
虽然AVL树的插入比较棘手，插入结点后又得更新平衡因子，平衡因子出问题之后，又得旋转调平衡把树的高度降下来，除降高度外，又得把异常的平衡因子重新调为正常。  
对于单旋虽然在旋转代码处理上细节比较多，但平衡因子的重新调整还不算麻烦，比较简单。而对于双旋那简直就恶心死了，光调节平衡因子还分为三种情况，调来调去头疼死了。  
但有一说一，AVL树的验证是真的简单，这总算能平衡一下受伤的心灵了，红黑树那里是插入不简单，验证还挺难，哈哈哈，更加棘手。

3.  
在验证这里，我们分两个方向对其进行验证，通过中序遍历的结果看其是否先满足搜索树，如果遍历结果不是升序，那就别说AVL树了，连搜索树他都够呛。  
然后通过AVL树的规则对其验证，每一个结点的右子树 - 左子树的高度差的绝对值不超过1。这里我们就需要写一个递归，先递归根，再分别递归左子树和右子树，保证任意一棵子树的左右高度差不超过1，所以还需要多写一个求高度的递归算法，这个算法也简单，左右子树高度较大的那个再+1就是树的高度。  
中序和测试左右高度差的代码通过后，就可以说明当前树的确是一棵AVL树。

void InOrder()
    	{
        
    		_InOrder(_root);
    	}
    	int Height(Node* root)
    	{
        
    		if (root == nullptr)
    			return 0;
    
    		return Height(root->_left) > Height(root->_right) ? Height(root->_left) + 1 : Height(root->_right) + 1;
    	}
    
    	bool IsBalance()
    	{
        
    		return _IsBalance(_root);
    	}
    private:
    	bool _IsBalance(Node* root)
    	{
        
    		if (root == nullptr)// 空树也算作平衡树
    			return true;
    
    		int leftHeight = Height(root->_left);
    		int rightHeight = Height(root->_right);
    
    		if (rightHeight - leftHeight != root->_bf)//顺便做的一件事
    		{
        
    			cout << root->_kv.first << ":" << "平衡因子异常" << endl;
    			return false;
    		}
    
    		return abs(leftHeight - rightHeight) < 2 && _IsBalance(root->_left) && _IsBalance(root->_right);
    	}
    	void _InOrder(Node* _root)
    	{
        
    		if (_root == nullptr)
    			return;
    		_InOrder(_root->_left);
    		cout << _root->_kv.first << ":" << _root->_kv.second << endl;
    		_InOrder(_root->_right);
    	}
    	Node* _root = nullptr;
    };

## 二、红黑树 ##

### 1.红黑树的介绍 ###

1.  
在实际应用中，AVL树用的很少，反而红黑树却名声在外，声明远扬，被用的最多。其实就是因为AVL树的规则过于严苛，导致稍微插入一些结点就有可能违反了AVL树的规则，我们就需要通过旋转调平衡进行处理，但旋转调平衡是有代价的啊，如果插入结点就调平衡，插入节点就调平衡，自然AVL树的效率就下来了，所以为了减少AVL树多次的旋转导致的效率降低问题，重新设定规则进而产生了红黑树。

2.  
红黑树有5条重要的性质，但最有用的就是其中的第c和d条。  
a.红黑树的节点不是红色就是黑色  
b.红黑树的根节点必须是黑色  
c.红黑树从当前根节点到每条路径上的黑色节点数量都相同。  
d.红色节点的左右孩子必须是黑色  
e.每个叶子节点的颜色都是黑色的（此处的叶子节点是指空节点，这可以帮助我们更好的分辨出每一条路径）

![在这里插入图片描述][351c9c33714c48f3ae2829cb58817d91.png]  
3.  
在上面的5条规则控制下，红黑树的最长路径不超过最短路径的2倍，因而红黑树是近似于平衡的，即使红黑树的最长路径是二倍，他的搜索效率也非常的高，如果说AVL树的搜索时间复杂度最坏是logN，那么红黑树最坏的搜索时间复杂度也仅仅是2倍的logN而已，比如查找10亿个数，AVL树最坏需要查找30次，而红黑树最坏需要查找60次，但30次和60次对于CPU来说那可以直接忽略，CPU每秒计算50亿次呢，你这30或60次简直太小了。所以红黑树的搜索效率和AVL树可以近似看作相等，但是红黑树不需要那么多的旋转来调平衡，因为红黑树可以允许最长路径是最短路径的2倍，他的要求并没有AVL树那么严格，所以红黑树的旋转次数要比AVL树少很多，效率自然就提升了，故而实际应用中红黑树要比AVL树用的更多一些。  
反过头来我们再思考一下，为什么保证红黑树的那几条规则以后，红黑树的最长路径可以是最短路径的二倍呢？他要求根节点的每条路径的黑色节点的数量必须相同，并且不允许出现连续的红色节点，所以最长路径的情形就是黑色节点和红色节点交替出现，最短路径就只有黑色结点，此时最长路径就恰好是最短路径的二倍。

### 2.红黑树插入的思路 ###

1.  
先来看一眼红黑树结点的定义，其实红黑树结点和AVL树结点很相似，唯一不同的就是红黑树把AVL树结点的平衡因子换做了枚举常量，枚举常量就是enum color定义的，颜色只包括RED和BLACK。  
new结点调用RBTreeNode的构造函数时，我们默认结点的颜色为红色，这里要解释一下为什么结点的默认颜色为红色。首先插入结点是有可能违反红黑树的规则的，如果违反了规则，我们就需要对红黑树进行"治疗"，首先如果插入结点是黑色，则一定会违反红黑树的第4条规则，因为你平白无故在某条路径上多加了一个黑色结点，其他路径就应该都多加一个黑色结点才能治疗红黑树，这样解决的成本太大了。但如果你插入的是红色结点，如果红色结点的父亲是红色，那红黑树也出问题了，也需要治疗，但如果红色节点的父亲是黑色，那红黑树就没有出问题，我们就不需要治疗，而且就算治疗，成本也不大，只要修改红色节点附近的路径就可以了，而插入黑色结点修改的可是整棵树的所有路径。所以综合分析来看，默认构造的结点颜色为红色对我们最有优势。

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;
    	enum color _col;
    	RBTreeNode(const pair<K,V> kv)
    		:_kv(kv)
    		,_left(nullptr)
    		,_right(nullptr)
    		,_parent(nullptr)
    		,_col(RED)
    		// 1.默认构造结点的颜色为红色，如果是黑色肯定会出事，因为要求根节点到所有叶子结点路径上的黑色结点数量都相同，违反规则了
    		// 影响了所有的路径，非常不好处理。
    		// 2.但如果是红色就好多了，有可能出事，出事我们调整就好了，如果不出事那更好了。
    	{
        }
    };

2.  
红黑树的插入整体思路其实就两步，比AVL树的思路简洁一些，第一步还是和二叉搜索树一样，这里不再赘述，第二步主要就是看parent的颜色，**如果parent的颜色为红色，我们才需要进行治疗**，或者parent为空，代表我们插入的结点是根节点，那就需要强制将结点颜色改为黑色，因为红黑树要求根节点必须为黑色。

3.  
治疗的情形有三种，处理关键在于uncle的颜色是红色还是黑色。  
**情况1：** cur是新增的红色结点，其parent为红色则需要治疗这棵红黑树，如果uncle存在且为红色则只需要让parent和uncle颜色改为黑色，grandparent颜色先改为红色，如果你不改为红色，那么这两条路径就平白无故的多加了两个黑色结点，势必违反了红黑树的第四条规则，所以需要继续判断grandparent的parent颜色，如果grandparent的parent颜色为黑，则无须继续治疗，因为已经治疗完毕，相当于把根节点的黑色平坦到两条路径下面，让根节点颜色变为了红色，但如果randparent的parent颜色为红，那还需要继续对红黑树继续治疗，再次治疗有可能出现下面三种情况的任意一种，可能是情况1，如果是情况1，则上一层的uncle左右不可能为空，因为如果为空，在新增红色结点之前这棵树就不是红黑树。除我们所说的上面这两大种情况之外，还有第三种情况，那就是grandparent是根节点，此时我们就不需要判断他的parent结点颜色了，直接强制将grandparent的颜色改为黑色即可。  
**情况2：** 情况2一定是由情况1变上来的，否则如果cur是新增红色，那原来的树就不是红黑树了，违反了第四条规则，所以情况2一定是由情况1变上来的。治疗情况2的问题也比较简单，只需要以grandparent为轴进行右单旋并且交换grandparent和parent的颜色即可，这样就可以治疗红黑树。具体右单旋的细节和AVL树一样，只是红黑树不需要调节平衡因子，仅仅只需要旋转+变色就可以，这里不再多说右单旋的细节。  
**情况3：** 情况3就是我们之前AVL树所说的双旋情况，这种情况也一定是由情况1变过来的，道理相同，如果不是情况1变过来的，那cur就是新增，如果是新增，原来的树就不是红黑树了，那就出问题了，所以情况3也一定是由情况1变过来的。  
在治疗这种问题上，可以先以parent为轴进行左单旋，只要左单旋过后，情况3就转变为了情况2，此时我们只需要以grandparent为轴进行右单旋+交换grandparent和cur的颜色即可治疗完成红黑树。  
**情况23的uncle不存在：** 有心的老铁肯定发现了我在情况23的后面写了uncle不存在，通过上面所说的情况23的处理大家就可以发现，uncle存在或者不存在对情况23有影响吗？无论你存不存在，该右单旋+变色还得右单旋+变色，该先左后右单旋+变色还得先左后右单旋+变色，而且变色的结点和uncle有关系吗？当然没有关系！所以直接把这种情况归到23里面了就，所以整体的情况就是单旋+变色和双旋+变色以及第一种情况，uncle存不存在都不重要。

![在这里插入图片描述][d9aeb39830bf41e9b7b1ec65cb721dac.png]  
4.  
为了给大家解释一下，情况2和3一定是由情况1变上来的，我下面画了两种图的情况，分别对应了右单旋+变色和先左后右单旋+变色的情况，并且在旋转+变色处理之后红黑树一定治疗成功了。下面的图解释的很清楚，我也就不废话了，老铁们可以看一下这两个图。

![在这里插入图片描述][f4f4da24471145588259c8710bb81f88.png]  
5.  
其实上面所说的情况只是红黑树的一半的情况，但只要会这一半，另一半就是反过来的，比如parent不是grandparent的左，而是grandparent的右，如果此时cur是parent的右，那就是左单旋+变色，如果是parent的左，那就是先右单旋后左单旋+变色，思路仅仅只是上面那三种情况的反面，由于在AVL树的部分左右单旋和双旋的情况我已经画的非常通透了，在红黑树这里我只画一面的情况，剩下的另一面兄弟们照猫画虎肯定也能画出来，所以在红黑树思路这个部分，我们只拿一面进行思路的讲解，另一面交给大家了。

### 3.红黑树插入的代码（关键是uncle） ###

1.  
红黑树插入代码的第一部分还是和二叉搜索树一样，不再细说。  
第二步就是针对cur的parent颜色为红色搞一个while循环，因为我们有可能会迭代向上进行红黑树的治疗，但while循环除这个条件外，还有一个容易忽略的点，就是治疗到根位置就结束治疗了，**也就是parent == nullptr的时候，while循环也该结束了，或者parent颜色为黑色时while循环也该结束了**，我们想的是循环结束的条件，写的是循环继续的条件，所以要用逻辑与而不是逻辑或。  
跳出while循环可能是因为情况1想上变到根结点了，然后迭代之后cur到了root的位置，parent到了nullptr的位置，此时我们需要强制将root指向结点的颜色改为黑色，**所以在while循环的外面，我们直接断死根节点颜色为黑色，不去判断while循环是由于什么条件而结束的，直接断死根节点颜色是黑色即可**。

2.  
while循环内部，总体也是分两面，一面是parent为grandparent的左，另一面是parent为grandparent的右，这两面的内部同样都分为三种情况，cur和parent位置的迭代是要放在第一种情况的，因为第一次新增红色结点是不可能出现23种情况的，只可能出现uncle存在且为红的情况，在第一种情况处理过后，我们才需要进行cur和parent位置的迭代，下一步进行判断是否有可能为23种情况或者是再次为第一种情况，如果是23种情况的任意一种，在处理之后我们直接break即可，因为此时红黑树治疗工作已经完成了。至于红黑树结点颜色的调节，大家可以对照上面我画的图进行颜色的改变，这个很简单，这里也不再多说了。

template <class K, class V>
    class RBTree
    {
        
    	typedef RBTreeNode<K, V> Node;
    public:
    	bool Insert(const pair<K, V>& kv)
    	{
        
    		Node* parent = nullptr;
    		Node* cur = _root;
    		if (_root == nullptr)
    		{
        
    			_root = new Node(kv);
    			_root->_col = BLACK;
    			return true;
    		}
    
    		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->_left = cur;
    			cur->_parent = parent;//这种三叉链的结构一定要小心，在链接的时候，时刻注意双向的性质，我链接你，你链接我
    		}
    		else
    		{
        
    			parent->_right = cur;
    			cur->_parent = parent;
    		}
    
    		// 只要插入结点之后，parent为红，此时违反红黑树规则，那我们就要对其进行调整，parent有可能为root的parent->nullptr
    		while (parent && parent->_col == RED)
    		{
        
    			Node* grandparent = parent->_parent;
    			if (parent == grandparent->_left)
    			{
        
    				Node* uncle = grandparent->_right;
    				
    				//情况1.uncle存在且为红
    				if (uncle && uncle->_col == RED)
    				{
        
    					parent->_col = uncle->_col = BLACK;
    					grandparent->_col = RED;
    
    					cur = grandparent;
    					parent = cur->_parent;// 如果grandparent是根，则parent是空
    				}
    				//情况2.uncle不存在或uncle为黑 -- 右单旋+变色
    				else if (cur == parent->_left)
    				{
        
    					//    g
    					//       p
    					//          c
    					RotateR(grandparent);
    					grandparent->_col = RED;
    					parent->_col = BLACK;
    					break;
    				}
    				//情况3.uncle不存在或uncle为黑 -- 左右双旋+变色
    				else if (cur == parent->_right)
    				{
        
    					//    g
    					//       p
    					//    c
    					RotateL(parent);
    					RotateR(grandparent);
    					cur->_col = BLACK;
    					grandparent->_col = RED;
    					break;
    				}
    				else
    				{
        
    					assert(false);
    				}
    			}
    			else// parent == grandparent->_right;
    			{
        
    				Node* uncle = grandparent->_left;
    				if (uncle && uncle->_col == RED)
    				{
        
    					grandparent->_col = RED;
    					uncle->_col = parent->_col = BLACK;
    
    					cur = grandparent;
    					parent = cur->_parent;
    				}
    				//uncle存在或为黑色的处理情况都是下面两种处理方式，通过cur在parent的左还是右，看处理方式是单旋还是双旋即可，
    				//uncle存在或者不存在都是不重要的
    				//情况2.进行左单旋+变色
    				else if (cur == parent->_right)
    				{
        
    					//    g
    					//       p
    					//          c
    					RotateL(grandparent);
    					parent->_col = BLACK;
    					grandparent->_col = RED;
    					break;
    				}
    				//情况3.右左双旋+变色
    				else if (cur == parent->_left)
    				{
        
    					//    g 黑
    					//       p 红
    					//    c 红
    					RotateR(parent);
    					RotateL(grandparent);
    					cur->_col = BLACK;
    					grandparent->_col = RED;
    					break;
    				}
    				else
    				{
        
    					assert(false);
    				}
    			}
    		}
    		_root->_col = BLACK;
    		// 有可能parent为root的parent也就是nullptr时，跳出循环之后root可能颜色为红色，所以我们在while外面直接断死根节点为黑色
    		
    		return true;
    	}

3.  
下面放的是AVL树的左右单旋代码，唯一做出的修改就是将调节平衡因子的代码进行了删除，所以红黑树这里的旋转和AVL树并无差别，在有了AVL树旋转的基础之后，红黑树的旋转+变色就好理解多了。

void RotateL(Node * parent)
    	{
        
    		Node* subR = parent->_right;
    		Node* subRL = subR->_left;
    		Node* pParent = parent->_parent;
    
    		//AVL树这样的三叉链结构，调整一个结点对另一个结点的指向，另外一个结点的指向也需要调整指向对面的结点上去，他是双向的。
    
    		parent->_right = subRL;//调整parent向下的指向，下面是有可能调整subRL向上的指向
    		if (subRL)
    			subRL->_parent = parent;
    
    		parent->_parent = subR;//调整parent向上的指向，下面就得调整subR向下的指向
    		subR->_left = parent;
    
    		subR->_parent = pParent;//调整了subR向上的指向，下面就得调整上面对subR的指向。
    		if (pParent == nullptr)
    			_root = subR;//如果parent恰好指向根节点，并且parent指向结点的bf为2或-2，则此时就需要换根结点指针的地址了
    		else
    		{
        
    			if (parent == pParent->_left)
    				pParent->_left = subR;
    			else
    				pParent->_right = subR;
    		}
    
    	}
    	void RotateR(Node * parent)
    	{
        
    		Node* subL = parent->_left;
    		Node* subLR = subL->_right;
    		Node* pParent = parent->_parent;
    
    		parent->_left = subLR;
    		if (subLR)
    			subLR->_parent = parent;
    
    		parent->_parent = subL;
    		subL->_right = parent;
    
    		subL->_parent = pParent;
    		if (pParent == nullptr)
    			_root = subL;
    		else
    		{
        
    			if (pParent->_left == parent)
    				pParent->_left = subL;
    			else
    				pParent->_right = subL;
    		}
    
    	}

### 4.红黑树的验证 ###

1.  
红黑树的验证相比AVL树就复杂的多了，我们需要对红黑树的三个部分进行验证，首先利用中序遍历观察是否满足搜索树，还需要验证红黑树中不能出现连续的红色结点，最后还需要保证每条路径的黑色结点数量都相同。  
对于满足搜索树条件，我们只需要看中序遍历的结果是否为升序就可以了，这个不难。  
想要判断红黑树中是否出现连续的红色结点，最容易的方式就是判断当前结点和他的parent颜色是否均为红色，如果你拿当前结点和他的孩子比较，那就麻烦了，还得和左右两个孩子进行比较，左右还有可能为空，非常麻烦。我们直接比对当前结点和其父节点，访问父节点就很简单了，因为平衡搜索树天然的三叉链结构可以很轻松的帮助我们访问父节点，所以我们只需要写一个递归，前序遍历整颗红黑树的所有结点，遇到空就返回，如果某个结点和其父节点的颜色均为红色，直接返回false即可。

2.  
比较有意思的其实是第4条性质的验证，对于每一个结点，以此结点为父节点向下所有的路径的黑色结点数量均相同，这个性质可不好验证啊，而且还是对于每个结点的所有向下的路径，这该怎么搞啊？  
这里面隐含了一个细微的点，我也是思考过后才发现到的，我们无须验证所有结点的向下每条路径上的黑色结点数量，只需要验证根节点root的向下所有路径的黑色结点数量相同即可完成所有结点的验证。其实道理很简单，只要根结点向下的每条路径相等了，那么左右子树的向下路径一定是相等的，因为根节点是所有路径的公共祖先，左右子树的每条路径的黑色结点数量都减1就好了，那对于左右子树各自来说，两棵子红黑树都不违反红黑树的第4条规则，假设其中一棵子红黑树的根节点颜色为红色，那他的左右子树路径的黑色结点数量就都不变，因为公共祖先是红色的，如果公共祖先是黑色的，那左右子树路径的黑色结点数量也是同时减1的，所以左右子树还是不会违反红黑树第4条规则的。  
**综上所述，只要满足root根结点的红黑树第4条规则，其余所有结点作根时均可满足第四条规则**。  
**代码实现上**，在递归之前，我们可以迭代先统计一下红黑树最左路径的黑色结点数量，以此来作为reference value，然后利用判断不能出现连续红色结点的递归算法，顺便统计出每条路径的黑色结点数量blackNum，当递归到nullptr的时候也就是递归到完整的一条路径了，此时进行blackNum和reference value比对，如果不相等直接返回false即可。（注意blackNum用的是传值而不是引用，因为我们希望的是每一个递归到nullptr函数栈帧都有自己独立的blackNum变量，而不是所有的栈帧共用一个局部blackNum变量，共用一个的话，统计出来的黑色结点数量就不是单条路径的了，而是整棵红黑树的所有黑色结点数量了，**所以不能用引用，应该用传值**）

void InOrder()
    	{
        
    		_InOrder(_root);
    	}
    	bool Check(Node* root, int blackNum, const int ref)
    	// blackNum用的就是传值传递，遇到空返回的时候，每条路径尾结点所在栈帧的blackNum都是独立的，传值就是用来干这个的，
    	//如果用引用传参，那就废了，每条路径的黑色结点数量类和到int& blackNum上面去了。
    	{
        
    		if (root == nullptr)
    		{
        
    			//cout << "每条路径的黑色结点数量:"<<blackNum << endl;
    			if (blackNum != ref)
    			{
        
    				cout << "违反规则: 本条路径的黑色结点的数量和最左路径不相等" << endl;
    				return false;
    			}
    			return true;
    		}
    		if (root->_col == RED && root->_parent->_col == RED)
    		{
        
    			cout << "违反规则: 出现了连续的红色结点" << endl;
    			//root的parent颜色为黑色能说明这棵树就是红黑树吗？当然确定不了，只有parent颜色为红色我们倒是能够确定违反了红黑树的规则
    			return false;
    		}
    
    		if (root->_col == BLACK)
    			++blackNum;
    
    		return Check(root->_left, blackNum, ref) && Check(root->_right, blackNum, ref);
    	}
    	bool IsBalance()
    	{
        
    		//求最长路径和最短路径的差不能保证树就是红黑树，因为树结点的颜色有可能是不正确的，万一出现连续的两个红色结点呢？
    		if (_root == nullptr)
    			return true;
    
    		//每个结点的颜色不是红色就是黑色，这点枚举类型就帮我们保证了，无须确定
    		//检查的两条原则，不能出现连续的两个红色结点，结点的每条路径上的黑色结点数量都相同
    		
    		if (_root->_col == RED)//root的颜色为黑色能确定这棵树就一定是红黑树吗？当然确定不了，但只要root颜色为红色，就可以确定违反红黑树规则
    			return false;
    
    		//遍历这棵树，找红色结点，判断红色结点的父亲是否为红色
    
    		int ref = 0;
    		Node* cur = _root;
    		while (cur)
    		{
        
    			if (cur->_col == BLACK)
    				ref++;
    			cur = cur->_left;
    		}
    		return Check(_root, 0, ref);// 1.遍历树的所有结点，看当前红结点的父亲是否为红色结点
    		
    		// 每个结点都给一个值，用于标识逆回去的路径上出现的黑色结点的数量。
    		//我们可以改变结点结果，或者利用递归算法的函数栈帧独立性进行解决，每一层的栈帧的黑色结点数量都是不同的。
    
    	}
    private:
    	void _InOrder(Node* _root)
    	{
        
    		if (_root == nullptr)
    			return;
    		_InOrder(_root->_left);
    		cout << _root->_kv.first << ":" << _root->_kv.second << endl;
    		_InOrder(_root->_right);
    	}
    	Node* _root = nullptr;
    };

[c872c5ab24f44a6096f661c1155b8a8b.jpeg_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/f98254bef457438cbba57e9bd21b6246.jpeg
[cfb653e565f14fdfaf8e35a52ed96bab.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/5c881e54ecc3428fb9c3a7e1564e04c6.png
[54c5d317e2b645bba56b56b5ea23de2f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/1eced07cf8c54284bb1f50eeae6ea7b2.png
[c120980568594f558dcb0c41b950cf21.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/503ee09608f8470f8a64694106b1f70e.png
[dc056daa935a4445b3362a2ace532e4b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/b019f94d167a45b8b6142cd3c89ec23e.png
[4db5570d9ee1440abe7f16cb9a316d5b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/d8bc7e5798b946efa6afbf38b997b1a9.png
[1e2fee45dc3043cfa829243eab70ecb5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/434db78635c2473598f64c2120042867.png
[47c4d56d68084980850366c17a8eb8c0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/2be193d8b8fd466b9bb868c88953aa9f.png
[cb260c940c1a4cbbb4c5ca08338b5706.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/203a7785cdf7408a8a66fbcae133f246.png
[ac2629206deb485eb8c9ba1a96eaabd6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/f685597979724e2b98006d970316f74b.png
[351c9c33714c48f3ae2829cb58817d91.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/53514b141a4a43f88269dde5ebd8effb.png
[d9aeb39830bf41e9b7b1ec65cb721dac.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/fa5be39e450a4a43b2eec082b2de7261.png
[f4f4da24471145588259c8710bb81f88.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/50192a7840f840119dc92fa3164828fa.png