回顾

C++红黑树（2/4）

在上一期的博客中我们学到了第一种情况红黑树如何进行平衡性调整

接下来我们要试试第二种情况，红黑树如何进行平衡性调整

下一节

c++红黑树（4/4

情况

第二种情况就是父亲节点为红色，叔叔节点没有或者为黑色，父亲节点为爷爷的左节点，且爷爷节点为曾祖父（爷爷的父亲）节点的左节点。

就是这么一个图

解决办法

这里要把节点进行右旋

在这里可能听起来会比较难以理解

但是记住你需要做的步骤，代码就可以很简单的进行实现

右旋

把曾祖父的左孩子指针从祖父那里断开（同时也断开祖父的父亲指针）

然后曾祖父的左孩子指针指向父亲节点

同时把父亲节点得到右指针指向祖父节点，如果父亲节点有右孩子节点需要把他提取出来放到原曾祖父的左孩子（同时连接祖父的父亲指针，后面都记得变，不说了）

就完成了右旋的操作

结果图为

变色

这个时候只需要变色就行了

把你的父亲节点变为黑色，同时把原爷爷节点变为红色

就为下图

这时候红黑树就进行了平衡

接上一章的问题

上一章的图片为

还记得我们上一回记住的吗？

把篮圈内的部分看为一个整体（因为他已经平衡了）

这时候他就是新的红色节点

他的父亲为“50”，他的祖父为“80”

可能看起来会比较复杂

我们只需要记住操作

由于没有曾祖父所以不需要改曾祖父的节点

把父亲的节点的右孩子连接到祖父节点，再把原父亲右孩子节点连接到祖父的左节点

这样宏观的结果就是相当于把爷爷节点“拽”了下来

最后的图为

最后进行变色

一个红黑树到达平衡

代码讲解

首先接在上一章情况之后

代码

判断爷爷是左节点还是右节点

			//（uncle != nullptr && uncle->colour == RED）不满足
			int sign = 0;
			RBNode<T>* gff = grandpa->parent;
			//标记数据sign判断祖父节点与曾祖父节点的关系
			if (gff != nullptr)
			{
				if (gff->lchild = grandpa)
					sign = 1;
				else
					sign = 2;
			}

这是为了判断祖父是曾祖父的左节点还是右节点方便连接

右旋函数代码

现在我们要创建一个右旋函数

我以函数是传递爷爷节点参数为例

除去曾祖父链接其他代码都按照说明写上去，按照逻辑来，不会那么难理解

	void RotateRight(RBNode<T>*& pointer)
	{
		//         6      -----右旋----             4
		//     /      \                          /     \
		//    4        7                        3       6
		//  /   \                                      /  \
		// 3     5                                    5    7   
		RBNode<T>* node_1 = pointer;
		pointer = pointer->lchild;
		pointer->parent = node_1->parent;
		node_1->lchild = pointer->rchild;
		if (pointer->rchild)
			pointer->rchild->parent = node_1;
		pointer->rchild = node_1;
		node_1->parent = pointer;
	}

选择情况并且执行右旋函数代码

选择祖父为为左节点，父亲也为左节点的情况并执行代码

			//插入数据的父亲是爷爷的左节点
			if (parent->parent->lchild==parent)
			{
				//插入数据是父亲的左节点
				if (parent->lchild = point)
				{
					RotateRight(grandpa);
				}
				//插入数据是父亲的右节点
				else
				{
					//...
				}
			}
			else
			{
				//...
			}

连接到原来的树上

最后就要把原父亲节点连接到曾祖父节点上（也就是连接到原来树上）

			if (parent->colour == BLACK)
				break;
			if (gff == nullptr)
				root = grandpa;
			else if (sign == 1)
				gff->lchild = grandpa;
			else if (sign == 2)
				gff->rchild = grandpa;

注意事项

在每次平衡性调整时，需要注意新节点的颜色最好不要变，因为它可能会是一个整体

比如这个 

这里新节点的颜色被整体看为红色

如果后续新节点要变化颜色，这个整体就要变化为黑色（也就是30这个节点变为黑色），一般情况下要篮圈内进行平衡性调整，这是复杂化且不合理的。

总代码

附上现在更新的总代码

#include <iostream>
using namespace std;
//定义一个颜色
enum Colour
{
	RED,
	BLACK,
};
//定义一个模版T
template<typename T>
//一个节点的结构体
struct RBNode
{
	RBNode* lchild,
		* rchild,
		* parent;
	T	data;
	//初始化为RED也可以后面定义一个初始化函数
	Colour colour=RED;
};
//再定义一个模版T（template只能联系到下面一句语句）
template <typename T>
class RBTree//树
{
public:
	RBTree()
	{
		root = nullptr;
	}
	~RBTree()
	{
		ReleaseNode(root);
	}
	//插入元素
	void InsNode(const T& e)
	{
		InsNode(root, e);
	}
	void InsNode(RBNode<T>*& tnode, const T& e)
	{
		RBNode<T>* point = tnode;
		RBNode<T>* parent = nullptr;
		//深入到叶子节点准备插入新数据
		while (point->data==nullptr)
		{
			if (e == point->data)
			{
				printf("该数据已经存在");
				return;
			}
			parent = point;
			if (e >= point)
				point = point->rchild;
			else
				point = point->lchild;
 
		}
		//准备插入数据
		point = new RBNode<T>;
		point->data = e;
		point->lchild = nullptr;
		point->rchild = nullptr;
		point->parent = nullptr;
		point->colour = RED;
		
		if (parent == nullptr)
		{
			//插入的是根节点
			point->colour = BLACK;
			tnode = point;
		}
		//不是根节点
		if (e > parent->data)
			parent->rchild = point; 
		else
			parent->lchild = point;
 
		point->parent = parent;
		if (parent->colour == BLACK)
		{
			count << e << "插入完成" << endl;
			return;
		}
		//接下来就是插入地方的父亲节点是红色的，且深度至少为3（因为第二层父亲节点颜色一定为黑色
		RBNode<T>* uncle = nullptr;
		RBNode<T>* grandpa = nullptr;
		//开始整个平衡性调整
		while (true)
		{
			uncle = (parent->parent != nullptr) ? (getuncle(parent) :nullptr);
			grandpa = point->parent->parent;
			if grandpa == nullptr
				break;
			if (uncle != nullptr && uncle->colour == RED)
			{
				parent->colour = BLACK;
				uncle->colour = BLACK;
				grandpa->colour = RED;
				if (grandpa == root)
				{
					grandpa->colour = BLACK;
					break;
				}
				point = grandpa;
				parent = grandpa->parent;
				if (parent->colour == BLACK)
					break;
				continue;
			}
 
 
			//（uncle != nullptr && uncle->colour == RED）不满足
			int sign = 0;
			RBNode<T>* gff = grandpa->parent;
			//标记数据sign判断祖父节点与曾祖父节点的关系
			if (gff != nullptr)
			{
				if (gff->lchild = grandpa)
					sign = 1;
				else
					sign = 2;
			}
			//插入数据的父亲是爷爷的左节点
			if (parent->parent->lchild==parent)
			{
				//插入数据是父亲的左节点
				if (parent->lchild = point)
				{
					RotateRight(grandpa);
				}
				//插入数据是父亲的右节点
				else
				{
					//...
				}
			}
			else
			{
				//...
			}
			if (parent->colour == BLACK)
				break;
			if (gff == nullptr)
				root = grandpa;
			else if (sign == 1)
				gff->lchild = grandpa;
			else if (sign == 2)
				gff->rchild = grandpa;
 
			break;
		}
		//无论如何根节点颜色为黑色
		root->colour = BLACK;
	}
private:
	//删除节点，释放内存
	void ReleaseNode(RBNode<T>* pnode)
	{
		if (pnode != nullptr)
		{
			ReleaseNode(pnode->lchild);
			ReleaseNode(pnode->rchild);
		}
		delete pnode;
	}
 
	//获取叔叔节点
	RBNode<T>* getuncle(RBNode<T>* p)
	{
		if (p->parent->lchild == p)
			return p->parent->rchild;
		else
			return p->parent->rchild;
	}
 
	//右旋节点
	void RotateRight(RBNode<T>*& pointer)
	{
		//         6      -----右旋----             4
		//     /      \                          /     \
		//    4        7                        3       6
		//  /   \                                      /  \
		// 3     5                                    5    7   
		RBNode<T>* node_1 = pointer;
		pointer = pointer->lchild;
		pointer->parent = node_1->parent;
		node_1->lchild = pointer->rchild;
		if (pointer->rchild)
			pointer->rchild->parent = node_1;
		pointer->rchild = node_1;
		node_1->parent = pointer;
	}
 
private:
	//根节点
	RBNode <T>* root;
};
template<typename T>
int main()
{
	RBNode<T>* root;
	RBTree();
	//还没有到定义的时候
	printf("OK");
	return 0;
}

总结

再次恭喜你，了解了红黑树的第二种情况的处理方法，接下来的最后一章的要讲剩下来的三种情况——因为设计左旋的代码和右旋其实相差不多，我们理解了右旋代码可以很快的理解并且使用左旋代码。