C++红黑树（2/4）

回顾

情况

回顾

C++红黑树（1/4）_木木em哈哈的博客-CSDN博客https://blog.csdn.net/mumuemhaha/article/details/131152321?spm=1001.2014.3001.5501

红黑树c++（3/4）_木木em哈哈的博客-CSDN博客 icon-default.png?t=N4P3 https://blog.csdn.net/mumuemhaha/article/details/131191005?spm=1001.2014.3001.5501

上一章学到了红黑树的特点以及基本定义

本章我们要学插入时候的第一类情况——父亲节点为红色叔叔节点也为红（当然祖父节点一定为黑色）

情况

当我的红色节点插上去时因为特性二——红色节点不可以相邻出现从而要对整个树进行平衡性调整

我们可以把新节点的颜色不变，然后把父亲节点和叔叔节点的颜色变为黑色，然后把爷爷节点的颜色变为红色

局部解决办法

从而达到这棵树的平衡

需要注意的是如果祖父是根节点的话要把祖父的颜色也调为黑色

全局解决的思想

然而不幸的是一颗树的深度不仅仅可以是3，他可以更深——4，5,，6，7…或者更多

如图

要在这个红黑树上把插入一个新的红色节点

那么还是安装之前的方法调整你会发现一个问题就是你插入节点的祖父节点的父亲节点（也就是你的曾祖父节点）是红色的且你祖父节点的叔叔节点是黑色不在这一类方法中

如图

但是不要慌张，后面两节会讲到其他的情况以及应对的方法（需要注意的时在后续解决中你要把蓝圈部分当成一个整体【因为他已经平衡了】）

现在恭喜你，你已经学到了红黑树插入时会遇到的第一种情况的解决办法

接下来就是代码讲解了

代码

首先我要创建一个RBTree（红黑树）的类

分别有lchild（左孩子）rchild（右孩子）parent（父母节点）data（自身的数据）color（颜色）

这几个类别除去color为RED（红色）其他全为空（nullptr）上一章讲过了

深入到叶子节点准备插入新数据

while (point->data==nullptr)
{
	if (e == point->data)
	{
		printf("该数据已经存在");
		return;
	}
	parent = point;
	if (e >= point)
		point = point->rchild;
	else
		point = point->lchild;

}

和其他的树一样，大的在右边，小的在左边重复数据插不了

每次保存其父亲节点

在一次次遍历中一直找到最深层

准备插入数据

接下来就是初始化数据

除了colour其他全为空

point = new RBNode<T>;
point->data = e;
point->lchild = nullptr;
point->rchild = nullptr;
point->parent = nullptr;
point->colour = RED;

需要注意的是如果为根节点那么colour还是要改为黑色

if (parent == nullptr)
{
	//插入的是根节点
	point->colour = BLACK;
	tnode = point;
}

插入

插入，接下来就是链接他的父亲节点

依照data的大小来判断插入左孩子还是右孩子

并且当父亲节点为黑色时不用判断直接插入完成返回

if (e > parent->data)
	parent->rchild = point;
else
	parent->lchild = point;

point->parent = parent;
if (parent->colour == BLACK)
{
	count << e << "插入完成" << endl;
	return;
}

出现本章情况

那么首先要创建其叔叔节点以及祖父节点并开始赋值

1 2	RBNode<T>* uncle = nullptr; RBNode<T>* grandpa = nullptr;

祖父节点赋值

祖父节点简单就是父亲的父亲

1	grandpa = point->parent->parent;

叔叔节点赋值

而叔叔节点麻烦一点

最好创建一个函数用来获取其叔叔节点

1	uncle = (parent->parent != nullptr) ? (getuncle(parent) :nullptr);

那么getuncle（）函数定义就为

RBNode<T>* getuncle(RBNode<T>* p)
{
	if (p->parent->lchild == p)
		return p->parent->rchild;
	else
		return p->parent->rchild;
}

需要注意的是获取叔叔节点的函数最好放在private（确保函数是私有的）

变色——进行平衡性调整

最后变颜色

在获取到了叔叔以及祖父节点后接下的工作就变得简单了

按照上面的图片依葫芦画瓢去变色就行

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;

	}
}
//无论如何根节点颜色为黑色
root->colour = BLACK;

总代码

最后附上调整后的源代码

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

			}
			point = grandpa;
			parent = grandpa->parent;
			if (parent->colour == BLACK)
				break;
			continue;
		}
		//无论如何根节点颜色为黑色
		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;
	}
private:
	//根节点
	RBNode <T>* root;
};

int main()
{
	//还没有到定义的时候
	printf("OK");
	return 0;
}