首页 > 其他分享 >数据结构高阶--红黑树（图解+实现）

数据结构高阶--红黑树（图解+实现）

时间：2022-12-07 14:22:45浏览次数：43  
标签：Node cur parent -- color BLACK 红黑树 数据结构 节点

红黑树

概念和性质

红黑树的概念：

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。它是通过控制节点颜色的方式来控制这棵树的相对平衡，保证了没有一条路径会比其它路径长出两倍，红黑树是一种接近平衡的二叉树（说它是接近平衡因为它并没有像AVL树的平衡因子的概念，它只是靠着满足红黑节点的性质来维持一种接近平衡的结构，进而提升整体的性能，并没有严格的卡定某个平衡因子来维持绝对平衡）。

在讲解红黑树性质之前，先简单了解一下几个概念：

  • parent：父节点
  • sibling：兄弟节点
  • uncle：叔父节点（ parent 的兄弟节点）
  • grand：祖父节点（ parent 的父节点）

红黑树的性质：

  • 节点是红色或黑色

  • 根节点是黑色

  • 所有叶子节点都是黑色（叶子是空结点），这里的叶子节点要注意以下，指的是最底层的空节点（外部节点），上图中的那些NULL节点才是叶子节点，NULL节点的父节点在红黑树里不将其看作叶子节点

  • 每个红色结点的两个子结点都是黑色

    • 红色节点的父节点都是黑色
    • 从根节点到叶子节点的所有路径上不能有2个连续的红色节点

  • 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点

思考一个问题： 为什么红黑树中最长路径的长度不会超过最短路径节点个数的两倍？

最长路径： 该条路径上节点分布是一红一黑
最短路径： 该条路径上节点分布是全黑
假设每条路径黑色节点数为N，则最长路径为2N，最短路径为N，所以这样就推出红黑树中最长路径的长度不会超过最短路径节点个数的两倍

红黑树的实现

红黑树节点定义

这里也是一个三叉链，其中每个节点包含颜色的元素在里面

enum Color
{
	RED, BLACK
};
template <class K,class V>
class RBTree_Node
{
public:
	RBTree_Node(const K& key, const V& value, Color color = RED) :left(nullptr), right(nullptr), parent(nullptr),
		key(key), value(value),color(color)
	{}
public:
	RBTree_Node<K, V>* left;
	RBTree_Node<K, V>* right;
	RBTree_Node<K, V>* parent;
	K key;
	V value;
	Color color;
};

红黑树结构定义

template <class K,class V>
class RB_Tree
{
	typedef RBTree_Node<K,V> Node;
public:

private:
	Node* root = nullptr;
};

红黑树的插入

方法概述

第一步： 我们先按照二叉搜索树树插入节点的方式，插入节点
第二步： 为了不破坏红黑树的规则，我们插入节点后要对红黑树进行相应的调整

思考： 我们插入节点应该默认插入红色节点好还是黑色节点好呢？
答案是红色节点。为什么呢？我们要考虑哪种方式对红黑树的破坏性更大一点。如果是黑色，此时黑导致该条路径比其它路径上黑色节点数都多一个，这样下来调整红黑树的步骤代价似乎会有点大；如果是红色，不会破坏第五条规则，只是破坏第四条规则，可能会出现连续的红色节点，这样我们只需要调整该节点及其附近节点的颜色即可，代价没有前一种方式大，所以我们选择第二种方式。

调整节点颜色

第一种情况： 如果插入节点的父亲是黑色节点，那么可以直接结束，不需要继续调整了
第二种情况： 如果插入节点为的父亲为红色节点，就需要进行相应的调整

下面讨论父亲节点是祖父节点的左孩子的几种情形（是右孩子的情形和这个类型，大家可以自己推演一下，这里我们把父亲节点叫做p(parent)，祖父叫g(grandfather)，叔叔节点叫u(uncle)）：

情景1：插入节点cur为红，p为红色（若p为红，那么g肯定是存在的且为黑），u存在且为红

前情提要：首先你需要知道，红黑树的调整关键看叔叔，因为节点的颜色是固定的，祖父存在且一定为黑，为什么？因为父节点为红色那么他一定不会是根，他一定有一个父节点且为黑，只有 u 节点不知道嘛情况。

操作： 把p和u改成黑，g改成红，如果g为根节点就把g的颜色变成黑然后结束，如果g不为根节点，且g的父亲为黑色也结束，为红色就需要迭代向上调整，判断此时处于何种情况

为什么要这么操作呢？

我们调整红黑树不是像AVL树一样旋转，而是进行变色处理，首先要将父亲变黑，此时就没有连续的红节点了，但是为了保持黑节点数目不变，所以叔叔也要变黑，紧接着还要将祖父变红，为什么呢？这可能是一个子树，叔叔父亲变黑了那么路径上黑节点就会多出一个，对整个结构必然有影响，所以还需要将祖父变红保持黑色数目不变

具像图：

如果g的父亲为红，就迭代向上调整：cur = grandfather，grandfather = grandfather -> parent

抽象图：

抽象图中cur可能是新插入的节点，也可能是迭代调整上来的节点，这里g这棵子树每条路径黑色节点数是相同的，且调整后g这棵子树的每条路径黑色数相同且和之前一样。cur是parent的左孩子和右孩子是一样的，因为这里都是对颜色进行控制，和方向无关

情景2：插入的cur为红色， p为红色（g肯定是存在的且为黑），u不存在

前情提要：在这种情况下的 cur 结点一定是新增节点，因为叔叔不存在，g的右子树没有黑节点，那么 parent 的下面也不可能再挂黑结点了（不然从g到左右子树路径上黑节点的数目就不相同了）

既然产生了连续的红节点那就必须把其中一个变黑，总不能把插进去的红节点变黑吧，不然就变成插黑节点了，因此就在只能把 parent 变黑，但是这样子树就会多出黑节点有会破坏结构，怎么办呢？

操作： cur为parent的左孩子时，对g进行右单旋，然后将p的颜色改黑，g的颜色改红；cur为parent的右孩子时，先对p进行左单旋，然后对g进行右单旋，然后将cur的颜色改黑，g的颜色改红

cur为parent的左孩子时 一条直线，此时进行右单旋

cur为parent的左孩子时 一条折线，此时进行左右双旋

抽像图：

情景3：插入的cur为红色，p为红色（g肯定是存在的且为黑），u存在且为黑

操作： 如果cur为parent的左孩子，对g进行右单旋，然后将p的颜色改为黑，g的颜色改为红；如果cur为parent的右孩子，先对p进行左单旋，对g进行右单旋，然后将cur的颜色改为黑，g的颜色改为红

解释： 假设此时a和b中黑色节点数为a，c的黑色节点数也一定为a，d和e的黑色节点数就是a-1，调整后cur和g的抽象图的黑色节点都是a，整体相等

抽象图：此时cur一定为调整上来的节点，因为如果是新增节点的话，那么原来g这棵子树左右黑色节点数目不等，所以cur一定是调整上来的节点（第一种情况向上调整的结果），祖父节点形成的 cur 节点，具体画个图像看看吧！

如上图所示，根据性质 4 假设祖父上面有 x 个黑节点，那么左子树（含祖父）现在是 x +1 个，右子树（含祖父）是 x + 2 + y 个，很明显 x + 2 + y > x + 1，因此在插入结点前就已经不满足要求了，所以说叔叔结点存在且为黑这种情况，一定是由情况一往上调整过程中才会出现的！
cur为parent的左孩子 一条直线，进行右单旋即可

cur为parent的右孩子 一条折线，此时进行左右双旋

总结： 上面就是p是g的左孩子的所有情形，为g的右孩子是与这个类似。还有注意的是根节点最后一定要改为黑色。

插入代码实现

旋转代码如下：这就是上一篇博客的旋转代码

/*
		注意：一般选取第一个不平衡的节点作为parent
	*/
	//左单旋，新插入的节点在右子树的右侧
	/*
		步骤：
		    1.让subR的左孩子成为parent的右孩子
			2.然后让parent成为subR的左孩子
			3.最后把两个节点的平衡因子修改为0
	*/
	void RotateL(Node* parent)
	{
		Node* subR = parent->right;
		Node* subRL = subR->left;
		//1.先把subR左边（可能为空也可能不为空）作为parent的右边
		parent->right = subRL;
		//2.如果subRL不为空，那么就让subRL的父指针指向parent
		if (subRL)
		{
			subRL->parent = parent;
		}
		//3.先记录parent的父节点的位置，然后把parent作为subR的左边
		Node* ppNode = parent->parent;
		subR->left = parent;
		//4.parent的父指针指向subR
		parent->parent = subR;
		//5.如果ppNode为空-->说明subR现在是根节点，就让subR的父指针指向nullptr
		//如果不是根节点就把subR的父指针指向parent的父节点，parent的父节点（左或右）指向subR
		if (ppNode == nullptr)
		{
			//更新根节点
			root = subR;
			subR->parent = nullptr;
		}
		else
		{
			//判断parent是ppNode的左还是右
			if (ppNode->left == parent)
			{
				ppNode->left = subR;
			}
			else
			{
				ppNode->right = subR;
			}
			subR->parent = ppNode;
		}
	}

//右单旋，新插入的节点在左子树的左侧
	/*
		步骤：
			1.让subL的右孩子成为parent的左孩子
			2.然后让parent成为subL的右孩子
			3.最后把两个节点的平衡因子修改为0
	*/
	void RotateR(Node* parent)
	{
		Node* subL = parent->left;
		Node* subLR = subL->right;
		//1.先把subL的右边（可能为空也可能不为空）作为parent的左边
		parent->left = subLR;
		//2.如果subLR不为空，就把subLR的父指针指向parent
		if (subLR)
		{
			subLR->parent = parent;
		}
		//3.记录parent的父节点的位置，然后把parent作为subL的右边
		Node* ppNode = parent->parent;
		subL->right = parent;
		//4.parent的父亲指针指向subL
		parent->parent = subL;
		//5.如果ppNode为空-->说明subL现在是根节点，就让subL的父节点指向nullptr
		//不是根节点就把subL的父节点指向parent的父节点，parent的父节点（左或右）指向subL
		if (ppNode == nullptr)
		{
			//更新根节点
			root = subL;
			subL->parent = nullptr;
		}
		else
		{
			//判断parent是ppNode的左还是右
			if (ppNode->left == parent)
			{
				ppNode->left = subL;
			}
			else
			{
				ppNode->right = subL;
			}
			subL->parent = ppNode;
		}
	}

插入代码实现如下：

pair<Node*, bool>Insert(const K& key, const V& value)
	{
		if (root == nullptr)
		{
			root = new Node(key, value, BLACK);//根节点默认黑
			return make_pair(root, true);
		}
		Node* cur = root;
		Node* parent = nullptr;
		while (cur)
		{
			parent = cur;
			if (key < cur->key)
			{
				cur = cur->left;
			}
			//大于往右走
			else if (key > cur->key)
			{
				cur = cur->right;
			}
			else
			{
				//待插入节点的key值=当前节点
				return make_pair(nullptr,false);//插入失败
			}
		}
		//节点默认给红节点，带来的影响最小
		cur = new Node(key, value);
		Node* newnode = cur; //记录新插入的结点（便于后序返回）
		if (cur->key < parent->key)
		{
			parent->left = cur;
			cur->parent = parent;
		}
		else
		{
			parent->right = cur;
			cur->parent = parent;
		}
		//调整颜色
	/*
		情况1：p为红，g为黑，u存在且为红
		操作：将p和u改为黑，g改为红
		调整后的几种情况：
			1.如果g是根节点，把g改成黑，结束
			2.如果g不是根节点
				a.g的父节点为黑，结束
				b.g的父节点为红，迭代向上调整，继续判断是那种情况（1和3）
				  cur = grandfather; father = cur->father
				  这里不关心cur是在p的左边还是右边，都是一样的，关心的是颜色而不是位置
		情况2：p为红，g为黑，u不存在/u为黑  cur p g三个一条直线
		操作（左边为例）：1.右单旋 2.把p改成黑，g改成红
			1.u不存在时，cur必定是新增节点
			2.u存在时，cur必定是更新上来的节点
		情况3：p为红，g为黑，u不存在/u为黑  cur p g三个是一条折线
		操作（左边为例）：1.p左单旋 2.g右单旋 3.把cur改成黑，g改成红
			1.u不存在时，cur必定是新增节点
			2.u存在时，cur必定是更新上来的节点
	*/
		//若插入节点的父节点是红色，则需要对红黑树进行调整
		while (parent && parent->color == RED)
		{
			//父节点是红色，那么其父节点一定存在
			Node* grandfather = parent->parent;
			if (parent == parent->left)
			{
				//叔叔节点，红黑树调整的关键就是叔叔节点
				Node* uncle = grandfather->right;
				//情况1：u存在并且为红
				if (uncle && uncle->color == RED)
				{
					//颜色调整
					parent->color = uncle->color = BLACK;
					grandfather->color = RED;
					//迭代处理
				}
				else//情况2+情况3 uncle不存在+uncle为黑
				{
					//折线处理：p左单旋，g右单旋，把cur改成黑，g改成红
					if (cur == parent->right)
					{
						RotateL(parent);
						swap(parent, cur);
					}
					//直线cur p g 把p改成黑，g改成红
					//右单旋 有可能是第三种情况
					RotateR(grandfather);
					parent->color = BLACK;
					grandfather->color = RED;
				}
			}
			//uncle在左边，parent是grandfather的右孩子
			else
			{
				Node* uncle = grandfather->left;
				if (uncle && uncle->color == RED)
				{
					parent->color = uncle->color = BLACK;
					grandfather->color = RED;

					// 迭代  向上调整
					cur = grandfather;
					parent = cur->parent;
				}
				else
				{
					// 折线用一个右单旋处理  g p cur  g变红p边黑
					if (cur == parent->left)
					{
						RotateR(parent);
						swap(parent, cur);
					}

					// 直线 g p cur 把p改成黑，g改成红
					// 左单旋  有可能是第三种情况
					RotateL(grandfather);

					parent->color = BLACK;
					grandfather->color = RED;
				}
				
			}
			
		}
		root->color = BLACK; //暴力处理根节点颜色，防止向上处理根节点变红
		return make_pair(cur,true);
	}

红黑树的删除

方法概述

第一步： 先按照二叉搜索树删除节点的方式找到要删除节点（也可能是替代节点）
第二步： 然后为了不破坏红黑树的几条规则，要对节点的颜色进行相应地调整

调整节点颜色

在红黑树中，删除一个节点，只有以下四种情况：

情况一：删除的节点的左、右子树都非空

情况二：删除的节点的左子树为空树，右子树非空

情况三：删除的节点的右子树为空树，左子树非空

情况四：删除的节点的左、右子树都为空树

其中情况一，可以按与其他二叉搜索树的删除方式一样处理，最终可以转换到后面的三种情况，在二叉搜索树删除中我有介绍，当左右节点都不为空的时候，最终会转化为情况二三四，所以我们只需要讨论后三种情况就可以了

第一种情况：删除节点（也可能是替代节点）（之后都叫delNode），如果该节点为红色，则直接删除退出即可，delNode没找到也可以直接退出

注意delNode的左节点之所以为NULL，不是因为我们没考虑delNode左孩子存在的情况，而是左右都存在的情况最终都会转化为只有一棵子树的形况，参考二叉搜索树的删除节点

这里的DR存在两种情况，为空或存在右子树，在后面会对DR进行详细的讨论

分析一下：因为delNode是红色，所以P必定为黑色，同时DR不可能为红色，根据红黑树的性质，DR必定为NULL，若DR存在节点，那么下面必定还有有NULL节点，delNode的左右节点数目不对，所以此时DR一定是NULL，现在要删除delNode节点，只需要直接将delNode删除，并且把DR作为P的左孩子即可，相信大家都明白了当要删除节点为红色的时候，为什么直接删除就可以了吧

第二种情况：delNode为黑色且delNode只有一个孩子时（此时该孩子一定为红色，不可能是黑色），删除delNode节点，然后把孩子节点的颜色改成黑色，也可直接结束

分析一下：若delNode是黑色，并且只有一个孩子DR时，此时就要分析DR为空还是不为空，若DR不为空，根据性质，那么DR必定为红色，且DR的两个子节点必定为NULL，此时删除的delNode是黑色，删除后P的左子树的黑节点数必定少1，刚好此时DR为黑色，并且删除后DR可以占据delNode的位置（此时仍是一棵二叉搜索树，只是暂时还是不是合格的红黑树），然后再将DR的颜色改为黑色，刚好可以填补P左子树所减少的黑节点数，从而达到红黑树的平衡

第三种情况：delNode为黑色，且没有孩子时，有下面几种情况（兄弟节点叫b(brother)，父亲节点叫p(parent)）：

情况1：delNode为黑，b为红，则两个孩子一定为黑

如果DR为NULL，删除delNode后，p的左子树黑节点数必定少1，纯粹想在p的左子树做文章来平衡p树是绝无可能的了。因此，必定需要其他分支的辅助来最终完成平衡调整。根据红黑树的定义，p会有一个右子节点，称为b子节点。此处又可细节分两种情况：黑b与红b。此处先讨论红b的情况。

操作：对p进行左单旋，然后将p的颜色改成红，b的颜色改成黑

分析一下：删除前P树的左右子树的黑节点数平衡，删除后（上图右侧所示），经过DR分支的黑节点数将比通过b分支的黑节点数少1。此时进行下面操作

将p左单旋，再将p由黑色改成红色，将b由红色改成黑色，让我们看看演变的过程：

经过上边的变化之后，经过p的路径，左分支黑节点数仍是少1（因为此时DR为NULL，而bL不是NULL，下面还有一个黑色的NULL，所以左分支比右分支少1），其他分支的黑节点数仍然保持不变。此时的情况却变成DR的兄弟节点为黑色(不再是红色的情况了)，此时就回到了一开始所说的另一种情况（b为黑色的情况）的处理。

提示：此时需要把 bL 节点看成原先的 b节点

注意：可能有人会一时想不明白什么要这样转换。因为这样转换后，虽然对于p树的左子树的黑节点数仍然会比右子树的黑节点数少1，但此时DR的兄弟(以前的b节点)现在已经变为bL，即已经由红色变为黑色，并且非常重要的此时的DR的兄弟节点bL的子结点(即：DR的两个侄子节点)，要不就是红色节点要不就必为NULL节点，而这种情况正是delNode为黑色、b也黑色的情况。(注意看注意看注意看一定注意看这点：对于被删除节点delNode的父节点来说，delNode黑b黑的情况下，无论如何delNode的兄弟节点b的两个儿子节点dL与dR都不可能是非NULL的黑节点)。因此实际上，这种转换就是把delNode为黑，b为红这种情况，转化为下面情况2中的情景三和情景四进行分析。

情况2：被删除的delNode为黑色，b也为黑色的情况（分四种情景讨论）

情景一：bL为红，bR颜色任意(对于该情况的处理，其实我们不关心P的颜色)

操作： 先对b进行右单旋，然后把b改红，bL改黑，然后对p进行左单旋，然后交换p和b的颜色，并把b的颜色改成黑

​ 如图当对b进行右单旋，将bL变黑，b改红之后，实际上变成了下面的情景二，接下来执行情景二的操作就可以了

分析一下：此时p树的左子树黑节点树减少1，因此，想要平衡，必需想办法让左子树的黑结节数增加1，而且同时P的右子树的黑节点数要保持不变。因此，想办法将bL这个红色节点利用起来，让它来填补p的左子树所缺少的黑节点个数。因此，立马想到旋转，只要有办法转到p的左子树或p位置上，则就有可能填平p左子树的高度。

情景二：bR为红，bL颜色任意(对于该情况的处理，其实我们不关心P的颜色)

操作： 对p进行左单旋，然后交换p和b的颜色，并把bR的颜色改成黑

情景三：bL、bR都为黑（其实都是NULL节点）；p为红。(注意：这种情况下，实际上就是delNode为黑，b为红转换之后的情况，此时b不为NULL，而bL与bR必定必定都为NULL节点)

操作：把p的颜色改成黑，b的颜色改成红

分析一下：此情况较为简单，直接将红色的p改为黑色，以此为填补DR缺少的黑节点个数。此时p右子树黑节点数却增多，因此，再将b改为红色即可平衡

情景四：bL、bR都为黑（其实都是NULL节点）；p为黑。(注意：这种情况下，实际上就是delNode为黑，b为红转换之后的情况，此时b不为NULL，而bL与bR必定必定都为NULL节点)

操作：把b的颜色改为红

分析一下：因为DR、p、b、bL、bR全都为黑色，则不论如何变换，都永远不可能使用p的左右子树的黑节点数达到平衡。而p不平衡的原因是因为P的右子树黑节点数会比左子树多1个。因此，干脆将b由黑色改为红色，如此一来，p的左、右子树的黑节点个数是平衡的。但是，此时经过p的路径的黑节点个数将会比不经过它的路径少一个。因此，我们将p作为待平衡的节点(即：此时的p相当于DR的角色)往上继续上溯，直到p为根节点为止。

思考一下：为什么要向上回溯？前面的几种情况为什么不用回溯

答案很简单，因为只有这种情况下，p这棵树整体黑节点数目-1了，试想一下，若p的父亲g，假设p是g的右子树，在没有删除delNode节点之前，g到左右子树的黑节点数目都是相同的，但是如果删除了delNode，p这棵树的黑节点整体-1，那么g的左右子树就不再平衡，g经过p和不经过p的黑节点数目始终相差1，所以需要向上回溯调整

总结： 删除就是以上几种情况，一般是左边少一个黑色节点，就靠右边补一个，结束，或者右边减少一个，然后两边整体少一个，对父亲节点进行检索。

删除代码实现

bool Erase(const K& key)
	{
		//如果树为空，删除失败
		if (root == nullptr)
		{
			return false;
		}
		Node* parent = nullptr;
		Node* cur = root;
		Node* delNode = nullptr;
		Node* delNodeParent = nullptr;
		while (cur)
		{
			//小于往左走
			if (key < cur->key)
			{
				parent = cur;
				cur = cur->left;
			}
			//大于往右走
			else if (key > cur->key)
			{
				parent = cur;
				cur = cur->right;
			}
			else
			{
				//找到了，当前要删除的节点是cur
				// 1.左右子树都为空 直接删除  可以归类为左为空
				// 2.左右子树只有一边为空  左为空，父亲指向我的右，右为空，父亲指向我的左  
				// 3.左右子树都不为空  取左子树最大的节点或右子树最小的节点和要删除的节点交换，然后再删除
				if (cur->left == nullptr)
				{
					//要删除的节点为根节点的时候，直接把右子树的根节点赋值给root
					//根节点的话会导致parent为nullptr
					if (root == cur)
					{
						root = root->right;
						if (root)
						{
							root->parent = nullptr;
							//根节点都是黑节点
							root->color = BLACK;
						}
						return true;
					}
					else
					{
						delNode = cur;
						delNodeParent = parent;
					}
				}
				else if (cur->right == nullptr)
				{
					if (root == cur)
					{
						root = root->left;
						if (root)
						{
							root->parent = nullptr;
							//根节点都是黑节点
							root->color = BLACK;
						}
						return true;
					}
					else
					{
						delNode = cur;
						delNodeParent = parent;
					}
				}
				else
				{
					//此时是左右子树都不为空的情况，要进行转化
					//找到右子树中最小的节点
					Node* rightMinParent = cur;
					Node* rightMin = cur->right;//去右子树去找
					while (rightMin->left)
					{
						rightMinParent = rightMin;
						rightMin = rightMin->left;
					}
					cur->key = rightMin->key;//替代，但是不删除，只是利用了二叉搜索树的替换
					//替换的是右子树最左边的节点，一定不存在左子树，是不是就将左右子树都存在的情况进行了转化

					delNode = rightMin;
					delNodeParent = rightMinParent;
				}
				break;
			}
		}
		//没找到
		if (cur == nullptr)
		{
			return false;
		}
		/*
			1.替代节点为红，直接删除
			2.替代节点为黑
				a.左右子树都存在，这种情况可以转化为b，上面介绍过了
				b.只有一棵子树存在（该子树节点一定为红），把孩子的颜色改成黑
				c.左右子树都不存在
		*/
		cur = delNode;
		parent = delNodeParent;
		if (cur->color == BLACK)
		{
			if (cur->left)//左孩子不为空
			{
				cur->left->color = BLACK;
			}
			else if (cur->right)
			{
				cur->right->color = BLACK;
			}
			else//替换的节点两个孩子都是空
			{
				while (parent)
				{
					//cur是parent的左
					if (cur == parent->left)
					{
						Node* brother = parent->right;
						//p为黑
						if (parent->color == BLACK)
						{
							Node* bL = brother->left;
							Node* bR = brother->right;
							if (brother->color == RED)//b为红，那么bL和bR一定是黑
							{
								//对p进行左单旋，然后将p的颜色改成红，b的颜色改成黑
								RotateL(parent);
								brother->color = BLACK;
								parent->color = RED;
								//还没结束，此时只是将b为红的情况转化为b为黑的情况，还需要继续检索
							}
							//b为黑，孩子都为黑，情景四
							else if (bL && bR && bL->color == BLACK && bR->color == BLACK)
							{
								//把b的颜色改为红，继续向上回溯
								brother->color = RED;
								cur = parent;
								parent = parent->parent;
							}
							//b为黑，bR为红，情景二
							else if (bR && bR->color == RED)
							{
								// 对p进行左单旋，然后交换p和b的颜色，并把bR的颜色改成黑
								RotateL(parent);
								swap(brother->color, parent->color);
								bR->color = BLACK;
								break;
							}
							//b为黑，bL为红，情景一
							else if (bL && bL->color == RED && (!bR || (bR && bR->color == BLACK)))
							{
								//b进行右单旋，将bL变黑，b改红之后，实际上变成了下面的情景二，接下来执行情景二的操作就可以了
								RotateR(brother);
								bL->color = BLACK;
								brother->color = RED;
							}
							//还剩一个情景三
							else
							{
								//操作：把p的颜色改成黑，b的颜色改成红
								//cur p b都是黑，且b无孩子，迭代更新，parent为红就结束
								brother->color = RED;
								cur = parent;
								parent = parent->parent;
							}
						}
						//p为红，b一定是黑
						else
						{
							Node* bL = brother->left;
							Node* bR = brother->right;
							// b的孩子全为黑 情景三 p变黑，b变红 结束
							if (bL && bR && bL->color == BLACK && bR->color == BLACK)
							{
								brother->color = RED;
								parent->color = BLACK;
								break;
							}
							// bL存在为红，bR不存在或bR为黑 情景一  右旋后变色转为情景一
							else if (bL && bL->color == RED && (!bR || (bR && bR->color == BLACK)))
							{
								RotateR(brother);
								bL->color = BLACK;
								brother->color = RED;
							}
							//bR存在为红，进行一个左旋，然后把右孩子的颜色改成黑色 情景二
							else if (bR && bR->color == RED) 
							{
								RotateL(parent);
								brother->color = parent->color;
								parent->color = BLACK;
								bR->color = BLACK;
								break;
							}
							else// cur 为黑，p为红，b为黑  调整颜色，结束
							{
								parent->color = BLACK;
								brother->color = RED;
								break;
							}
						}
					}
					//cur是右子树的情况，和左正好反过来
					else
					{
						Node* brother = parent->left;
						// p为黑
						if (parent->color == BLACK)
						{
							Node* bL = brother->left;
							Node* bR = brother->right;
							// SL和SR一定存在且为黑
							if (brother->color == RED)// b为红，SL和SR都为黑  b的颜色改黑，p的颜色改红  情况a
							{
								RotateR(parent);
								brother->color = BLACK;
								parent->color = RED;

								// 没有结束，还要对cur进行检索
							}
							else if (bL && bR && bL->color == BLACK && bR->color == BLACK)// b为黑，孩子存在
							{
								// 且孩子也为黑  把brother改成红色，迭代 GP比GU小1  情况b
								brother->color = RED;
								cur = parent;
								parent = parent->parent;
							}
							// 右孩子存在且为红，但左孩子不存在或为黑  情况e  右旋后变色转为情况d
							else if (bR && bR->color == RED && (!bL || (bL && bL->color == BLACK)))
							{
								RotateL(brother);
								brother->color = RED;
								bR->color = BLACK;
							}
							else if (bL && bL->color == RED) // 左孩子为红，进行一个右旋，然后把左孩子的颜色改成黑色 情况d
							{
								RotateR(parent);
								swap(brother->color, parent->color);
								bL->color = BLACK;
								break;
							}
							else
							{
								// cur p b 都是黑，且b无孩子，迭代更新
								// if (parent == _root) // p是根节点，把b变红 否则迭代
								brother->color = RED;
								cur = parent;
								parent = parent->parent;
							}
						}
						// p为红  b一定为黑
						else
						{
							Node* bL = brother->left;
							Node* bR = brother->right;
							if (bL && bR && bL->color == BLACK && bR->color == BLACK)// b的孩子全为黑 情况c p变黑，b变红 结束
							{
								brother->color = RED;
								parent->color = BLACK;
								break;
							}
							// 右孩子存在且为红，但左孩子不存在或为黑  情况e  右旋后变色转为情况d
							else if (bR && bR->color == RED && (!bL || (bL && bL->color == BLACK)))
							{
								RotateL(brother);
								brother->color = RED;
								bR->color = BLACK;
							}
							else if (bL && bL->color == RED) // 左孩子为红，进行一个右旋，然后把左孩子的颜色改成黑色 情况d
							{
								RotateR(parent);
								// swap(brother->color, parent->color);
								brother->color = parent->color;
								parent->color = BLACK;
								bL->color = BLACK;
								break;
							}
							else// cur 为黑，p为红，b为黑  调整颜色，结束
							{
								parent->color = BLACK;
								brother->color = RED;
								break;
							}
						}
					}
				}
			}
		}
		//上面是对颜色进行了调整，接下来进行删除操作
		delNodeParent = delNode->parent;
		//删除
		if (delNode->left == nullptr)
		{
			if (delNodeParent->left == delNode)
			{
				delNodeParent->left = delNode->right;
			}
			else
				delNodeParent->right = delNode->right;
			if (delNode->right)// 右不为空，就让右节点的父指针指向delNodeParent
				delNode->right->parent = delNodeParent;
		}
		else
		{
			if (delNodeParent->left == delNode)
				delNodeParent->left = delNode->left;
			else
				delNodeParent->right = delNode->left;
			if (delNode->left)// 右不为空，就让右节点的父指针指向delNodeParent
				delNode->left->parent = delNodeParent;
		}
		delete delNode;
		delNode = nullptr;
		return true;
	}

红黑树的查找

//红黑树的查找
	bool Find(const K& key)
	{
		if (root == nullptr)
			return false;

		Node* cur = root;
		while (cur)
		{
			// 小于往左走
			if (key < cur->key)
			{
				cur = cur->left;
			}
			// 大于往右走
			else if (key > cur->key)
			{
				cur = cur->right;
			}
			else
			{
				// 找到了
				return true;
			}
		}
		return false;
	}

红黑树遍历

//中序遍历（递归）
	void InOrder()
	{
		_InOrder(root);
		cout << endl;
	}
	void _InOrder(Node* root)
	{
		if (root == NULL)
		{
			return;
		}
		else
		{
			_InOrder(root->left);
			cout << root->key << ":" << root->value << " ";
			_InOrder(root->right);
		}
	}

红黑树的验证

//红黑树的验证
	bool IsValidRBTree()
	{
		// 空树也是红黑树
		if (root == nullptr)
			return true;
		// 判断根节点的颜色是否为黑色
		if (root->color != BLACK)
		{
			cout << "违反红黑树的根节点为黑色的规则" << endl;
			return false;
		}
		// 计算出任意一条路径的黑色节点个数
		size_t blackCount = 0;
		Node* cur = root;
		while (cur)
		{
			if (cur->color == BLACK)
				++blackCount;
			cur = cur->left;
		}
		// 检测每条路径黑节点个数是否相同 第二个参数记录路径中黑节点的个数
		return _IsValidRBTree(root, 0, blackCount);
	}
	bool _IsValidRBTree(Node* root, size_t k, size_t blackCount)
	{
		// 走到空就判断该条路径的黑节点是否等于blackCount
		if (root == nullptr)
		{
			if (k != blackCount)
			{
				cout << "违反每条路径黑节点个数相同的规则" << endl;
				return false;
			}
			return true;
		}

		if (root->color == BLACK)
			++k;

		// 判断是否出现了连续两个红色节点
		Node* parent = root->parent;
		if (parent && root->color == RED && parent->color == RED)
		{
			cout << "违反了不能出现连续两个红色节点的规则" << endl;
			return false;
		}

		return _IsValidRBTree(root->left, k, blackCount)
			&& _IsValidRBTree(root->right, k, blackCount);
	}
	int _Height(Node* root)
	{
		if (root == nullptr)
			return 0;

		int leftHeight = _Height(root->left);
		int rightHeight = _Height(root->right);

		return 1 + max(leftHeight, rightHeight);
	}

红黑树完整代码及测试

#define _CRT_SECURE_NO_WARNINGS
#include<iostream> //引入头文件
#include<string>//C++中的字符串
#include<vector>
using namespace std; //标准命名空间
enum Color
{
	RED, BLACK
};
template <class K,class V>
class RBTree_Node
{
public:
	RBTree_Node(const K& key, const V& value, Color color = RED) :left(nullptr), right(nullptr), parent(nullptr),
		key(key), value(value), color(color)
	{}
public:
	RBTree_Node<K, V>* left;
	RBTree_Node<K, V>* right;
	RBTree_Node<K, V>* parent;
	K key;
	V value;
	Color color;
};
template <class K,class V>
class RB_Tree
{
	typedef RBTree_Node<K,V> Node;
public:
	/*
		注意：一般选取第一个不平衡的节点作为parent
	*/
	//左单旋，新插入的节点在右子树的右侧
	/*
		步骤：
			1.让subR的左孩子成为parent的右孩子
			2.然后让parent成为subR的左孩子
			3.最后把两个节点的平衡因子修改为0
	*/
	void RotateL(Node* parent)
	{
		Node* subR = parent->right;
		Node* subRL = subR->left;
		//1.先把subR左边（可能为空也可能不为空）作为parent的右边
		parent->right = subRL;
		//2.如果subRL不为空，那么就让subRL的父指针指向parent
		if (subRL)
		{
			subRL->parent = parent;
		}
		//3.先记录parent的父节点的位置，然后把parent作为subR的左边
		Node* ppNode = parent->parent;
		subR->left = parent;
		//4.parent的父指针指向subR
		parent->parent = subR;
		//5.如果ppNode为空-->说明subR现在是根节点，就让subR的父指针指向nullptr
		//如果不是根节点就把subR的父指针指向parent的父节点，parent的父节点（左或右）指向subR
		if (ppNode == nullptr)
		{
			//更新根节点
			root = subR;
			subR->parent = nullptr;
		}
		else
		{
			//判断parent是ppNode的左还是右
			if (ppNode->left == parent)
			{
				ppNode->left = subR;
			}
			else
			{
				ppNode->right = subR;
			}
			subR->parent = ppNode;
		}
	}
	//右单旋，新插入的节点在左子树的左侧
	/*
		步骤：
			1.让subL的右孩子成为parent的左孩子
			2.然后让parent成为subL的右孩子
			3.最后把两个节点的平衡因子修改为0
	*/
	void RotateR(Node* parent)
	{
		Node* subL = parent->left;
		Node* subLR = subL->right;
		//1.先把subL的右边（可能为空也可能不为空）作为parent的左边
		parent->left = subLR;
		//2.如果subLR不为空，就把subLR的父指针指向parent
		if (subLR)
		{
			subLR->parent = parent;
		}
		//3.记录parent的父节点的位置，然后把parent作为subL的右边
		Node* ppNode = parent->parent;
		subL->right = parent;
		//4.parent的父亲指针指向subL
		parent->parent = subL;
		//5.如果ppNode为空-->说明subL现在是根节点，就让subL的父节点指向nullptr
		//不是根节点就把subL的父节点指向parent的父节点，parent的父节点（左或右）指向subL
		if (ppNode == nullptr)
		{
			//更新根节点
			root = subL;
			subL->parent = nullptr;
		}
		else
		{
			//判断parent是ppNode的左还是右
			if (ppNode->left == parent)
			{
				ppNode->left = subL;
			}
			else
			{
				ppNode->right = subL;
			}
			subL->parent = ppNode;
		}
	}
	pair<Node*, bool>Insert(const K& key, const V& value)
	{
		if (root == nullptr)
		{
			root = new Node(key, value, BLACK);//根节点默认黑
			return make_pair(root, true);
		}
		Node* cur = root;
		Node* parent = nullptr;
		while (cur)
		{
			parent = cur;
			if (key < cur->key)
			{
				cur = cur->left;
			}
			//大于往右走
			else if (key > cur->key)
			{
				cur = cur->right;
			}
			else
			{
				//待插入节点的key值=当前节点
				return make_pair(nullptr,false);//插入失败
			}
		}
		//节点默认给红节点，带来的影响最小
		cur = new Node(key, value);
		Node* newnode = cur; //记录新插入的结点（便于后序返回）
		if (cur->key < parent->key)
		{
			parent->left = cur;
			cur->parent = parent;
		}
		else
		{
			parent->right = cur;
			cur->parent = parent;
		}
		//调整颜色
	/*
		情况1：p为红，g为黑，u存在且为红
		操作：将p和u改为黑，g改为红
		调整后的几种情况：
			1.如果g是根节点，把g改成黑，结束
			2.如果g不是根节点
				a.g的父节点为黑，结束
				b.g的父节点为红，迭代向上调整，继续判断是那种情况（1和3）
				  cur = grandfather; father = cur->father
				  这里不关心cur是在p的左边还是右边，都是一样的，关心的是颜色而不是位置
		情况2：p为红，g为黑，u不存在/u为黑  cur p g三个一条直线
		操作（左边为例）：1.右单旋 2.把p改成黑，g改成红
			1.u不存在时，cur必定是新增节点
			2.u存在时，cur必定是更新上来的节点
		情况3：p为红，g为黑，u不存在/u为黑  cur p g三个是一条折线
		操作（左边为例）：1.p左单旋 2.g右单旋 3.把cur改成黑，g改成红
			1.u不存在时，cur必定是新增节点
			2.u存在时，cur必定是更新上来的节点
	*/
		//若插入节点的父节点是红色，则需要对红黑树进行调整
		while (parent && parent->color == RED)
		{
			//父节点是红色，那么其父节点一定存在
			Node* grandfather = parent->parent;
			if (parent == parent->left)
			{
				//叔叔节点，红黑树调整的关键就是叔叔节点
				Node* uncle = grandfather->right;
				//情况1：u存在并且为红
				if (uncle && uncle->color == RED)
				{
					//颜色调整
					parent->color = uncle->color = BLACK;
					grandfather->color = RED;
					//迭代处理
				}
				else//情况2+情况3 uncle不存在+uncle为黑
				{
					//折线处理：p左单旋，g右单旋，把cur改成黑，g改成红
					if (cur == parent->right)
					{
						RotateL(parent);
						swap(parent, cur);
					}
					//直线cur p g 把p改成黑，g改成红
					//右单旋 有可能是第三种情况
					RotateR(grandfather);
					parent->color = BLACK;
					grandfather->color = RED;
				}
			}
			//uncle在左边，parent是grandfather的右孩子
			else
			{
				Node* uncle = grandfather->left;
				if (uncle && uncle->color == RED)
				{
					parent->color = uncle->color = BLACK;
					grandfather->color = RED;

					// 迭代  向上调整
					cur = grandfather;
					parent = cur->parent;
				}
				else
				{
					// 折线用一个右单旋处理  g p cur  g变红p边黑
					if (cur == parent->left)
					{
						RotateR(parent);
						swap(parent, cur);
					}

					// 直线 g p cur 把p改成黑，g改成红
					// 左单旋  有可能是第三种情况
					RotateL(grandfather);

					parent->color = BLACK;
					grandfather->color = RED;
				}
				
			}
			
		}
		root->color = BLACK; //暴力处理根节点颜色，防止向上处理根节点变红
		return make_pair(cur,true);
	}
	bool Erase(const K& key)
	{
		//如果树为空，删除失败
		if (root == nullptr)
		{
			return false;
		}
		Node* parent = nullptr;
		Node* cur = root;
		Node* delNode = nullptr;
		Node* delNodeParent = nullptr;
		while (cur)
		{
			//小于往左走
			if (key < cur->key)
			{
				parent = cur;
				cur = cur->left;
			}
			//大于往右走
			else if (key > cur->key)
			{
				parent = cur;
				cur = cur->right;
			}
			else
			{
				//找到了，当前要删除的节点是cur
				// 1.左右子树都为空 直接删除  可以归类为左为空
				// 2.左右子树只有一边为空  左为空，父亲指向我的右，右为空，父亲指向我的左  
				// 3.左右子树都不为空  取左子树最大的节点或右子树最小的节点和要删除的节点交换，然后再删除
				if (cur->left == nullptr)
				{
					//要删除的节点为根节点的时候，直接把右子树的根节点赋值给root
					//根节点的话会导致parent为nullptr
					if (root == cur)
					{
						root = root->right;
						if (root)
						{
							root->parent = nullptr;
							//根节点都是黑节点
							root->color = BLACK;
						}
						return true;
					}
					else
					{
						delNode = cur;
						delNodeParent = parent;
					}
				}
				else if (cur->right == nullptr)
				{
					if (root == cur)
					{
						root = root->left;
						if (root)
						{
							root->parent = nullptr;
							//根节点都是黑节点
							root->color = BLACK;
						}
						return true;
					}
					else
					{
						delNode = cur;
						delNodeParent = parent;
					}
				}
				else
				{
					//此时是左右子树都不为空的情况，要进行转化
					//找到右子树中最小的节点
					Node* rightMinParent = cur;
					Node* rightMin = cur->right;//去右子树去找
					while (rightMin->left)
					{
						rightMinParent = rightMin;
						rightMin = rightMin->left;
					}
					cur->key = rightMin->key;//替代，但是不删除，只是利用了二叉搜索树的替换
					//替换的是右子树最左边的节点，一定不存在左子树，是不是就将左右子树都存在的情况进行了转化

					delNode = rightMin;
					delNodeParent = rightMinParent;
				}
				break;
			}
		}
		//没找到
		if (cur == nullptr)
		{
			return false;
		}
		/*
			1.替代节点为红，直接删除
			2.替代节点为黑
				a.左右子树都存在，这种情况可以转化为b，上面介绍过了
				b.只有一棵子树存在（该子树节点一定为红），把孩子的颜色改成黑
				c.左右子树都不存在
		*/
		cur = delNode;
		parent = delNodeParent;
		if (cur->color == BLACK)
		{
			if (cur->left)//左孩子不为空
			{
				cur->left->color = BLACK;
			}
			else if (cur->right)
			{
				cur->right->color = BLACK;
			}
			else//替换的节点两个孩子都是空
			{
				while (parent)
				{
					//cur是parent的左
					if (cur == parent->left)
					{
						Node* brother = parent->right;
						//p为黑
						if (parent->color == BLACK)
						{
							Node* bL = brother->left;
							Node* bR = brother->right;
							if (brother->color == RED)//b为红，那么bL和bR一定是黑
							{
								//对p进行左单旋，然后将p的颜色改成红，b的颜色改成黑
								RotateL(parent);
								brother->color = BLACK;
								parent->color = RED;
								//还没结束，此时只是将b为红的情况转化为b为黑的情况，还需要继续检索
							}
							//b为黑，孩子都为黑，情景四
							else if (bL && bR && bL->color == BLACK && bR->color == BLACK)
							{
								//把b的颜色改为红，继续向上回溯
								brother->color = RED;
								cur = parent;
								parent = parent->parent;
							}
							//b为黑，bR为红，情景二
							else if (bR && bR->color == RED)
							{
								// 对p进行左单旋，然后交换p和b的颜色，并把bR的颜色改成黑
								RotateL(parent);
								swap(brother->color, parent->color);
								bR->color = BLACK;
								break;
							}
							//b为黑，bL为红，情景一
							else if (bL && bL->color == RED && (!bR || (bR && bR->color == BLACK)))
							{
								//b进行右单旋，将bL变黑，b改红之后，实际上变成了下面的情景二，接下来执行情景二的操作就可以了
								RotateR(brother);
								bL->color = BLACK;
								brother->color = RED;
							}
							//还剩一个情景三
							else
							{
								//操作：把p的颜色改成黑，b的颜色改成红
								//cur p b都是黑，且b无孩子，迭代更新，parent为红就结束
								brother->color = RED;
								cur = parent;
								parent = parent->parent;
							}
						}
						//p为红，b一定是黑
						else
						{
							Node* bL = brother->left;
							Node* bR = brother->right;
							// b的孩子全为黑 情景三 p变黑，b变红 结束
							if (bL && bR && bL->color == BLACK && bR->color == BLACK)
							{
								brother->color = RED;
								parent->color = BLACK;
								break;
							}
							// bL存在为红，bR不存在或bR为黑 情景一  右旋后变色转为情景一
							else if (bL && bL->color == RED && (!bR || (bR && bR->color == BLACK)))
							{
								RotateR(brother);
								bL->color = BLACK;
								brother->color = RED;
							}
							//bR存在为红，进行一个左旋，然后把右孩子的颜色改成黑色 情景二
							else if (bR && bR->color == RED) 
							{
								RotateL(parent);
								brother->color = parent->color;
								parent->color = BLACK;
								bR->color = BLACK;
								break;
							}
							else// cur 为黑，p为红，b为黑  调整颜色，结束
							{
								parent->color = BLACK;
								brother->color = RED;
								break;
							}
						}
					}
					//cur是右子树的情况，和左正好反过来
					else
					{
						Node* brother = parent->left;
						// p为黑
						if (parent->color == BLACK)
						{
							Node* bL = brother->left;
							Node* bR = brother->right;
							// SL和SR一定存在且为黑
							if (brother->color == RED)// b为红，SL和SR都为黑  b的颜色改黑，p的颜色改红  情况a
							{
								RotateR(parent);
								brother->color = BLACK;
								parent->color = RED;

								// 没有结束，还要对cur进行检索
							}
							else if (bL && bR && bL->color == BLACK && bR->color == BLACK)// b为黑，孩子存在
							{
								// 且孩子也为黑  把brother改成红色，迭代 GP比GU小1  情况b
								brother->color = RED;
								cur = parent;
								parent = parent->parent;
							}
							// 右孩子存在且为红，但左孩子不存在或为黑  情况e  右旋后变色转为情况d
							else if (bR && bR->color == RED && (!bL || (bL && bL->color == BLACK)))
							{
								RotateL(brother);
								brother->color = RED;
								bR->color = BLACK;
							}
							else if (bL && bL->color == RED) // 左孩子为红，进行一个右旋，然后把左孩子的颜色改成黑色 情况d
							{
								RotateR(parent);
								swap(brother->color, parent->color);
								bL->color = BLACK;
								break;
							}
							else
							{
								// cur p b 都是黑，且b无孩子，迭代更新
								// if (parent == _root) // p是根节点，把b变红 否则迭代
								brother->color = RED;
								cur = parent;
								parent = parent->parent;
							}
						}
						// p为红  b一定为黑
						else
						{
							Node* bL = brother->left;
							Node* bR = brother->right;
							if (bL && bR && bL->color == BLACK && bR->color == BLACK)// b的孩子全为黑 情况c p变黑，b变红 结束
							{
								brother->color = RED;
								parent->color = BLACK;
								break;
							}
							// 右孩子存在且为红，但左孩子不存在或为黑  情况e  右旋后变色转为情况d
							else if (bR && bR->color == RED && (!bL || (bL && bL->color == BLACK)))
							{
								RotateL(brother);
								brother->color = RED;
								bR->color = BLACK;
							}
							else if (bL && bL->color == RED) // 左孩子为红，进行一个右旋，然后把左孩子的颜色改成黑色 情况d
							{
								RotateR(parent);
								// swap(brother->color, parent->color);
								brother->color = parent->color;
								parent->color = BLACK;
								bL->color = BLACK;
								break;
							}
							else// cur 为黑，p为红，b为黑  调整颜色，结束
							{
								parent->color = BLACK;
								brother->color = RED;
								break;
							}
						}
					}
				}
			}
		}
		//上面是对颜色进行了调整，接下来进行删除操作
		delNodeParent = delNode->parent;
		//删除
		if (delNode->left == nullptr)
		{
			if (delNodeParent->left == delNode)
			{
				delNodeParent->left = delNode->right;
			}
			else
				delNodeParent->right = delNode->right;
			if (delNode->right)// 右不为空，就让右节点的父指针指向delNodeParent
				delNode->right->parent = delNodeParent;
		}
		else
		{
			if (delNodeParent->left == delNode)
				delNodeParent->left = delNode->left;
			else
				delNodeParent->right = delNode->left;
			if (delNode->left)// 右不为空，就让右节点的父指针指向delNodeParent
				delNode->left->parent = delNodeParent;
		}
		delete delNode;
		delNode = nullptr;
		return true;
	}
	//红黑树的查找
	bool Find(const K& key)
	{
		if (root == nullptr)
			return false;

		Node* cur = root;
		while (cur)
		{
			// 小于往左走
			if (key < cur->key)
			{
				cur = cur->left;
			}
			// 大于往右走
			else if (key > cur->key)
			{
				cur = cur->right;
			}
			else
			{
				// 找到了
				return true;
			}
		}
		return false;
	}
	//红黑树的验证
	bool IsValidRBTree()
	{
		// 空树也是红黑树
		if (root == nullptr)
			return true;
		// 判断根节点的颜色是否为黑色
		if (root->color != BLACK)
		{
			cout << "违反红黑树的根节点为黑色的规则" << endl;
			return false;
		}
		// 计算出任意一条路径的黑色节点个数
		size_t blackCount = 0;
		Node* cur = root;
		while (cur)
		{
			if (cur->color == BLACK)
				++blackCount;
			cur = cur->left;
		}
		// 检测每条路径黑节点个数是否相同 第二个参数记录路径中黑节点的个数
		return _IsValidRBTree(root, 0, blackCount);
	}
	bool _IsValidRBTree(Node* root, size_t k, size_t blackCount)
	{
		// 走到空就判断该条路径的黑节点是否等于blackCount
		if (root == nullptr)
		{
			if (k != blackCount)
			{
				cout << "违反每条路径黑节点个数相同的规则" << endl;
				return false;
			}
			return true;
		}

		if (root->color == BLACK)
			++k;

		// 判断是否出现了连续两个红色节点
		Node* parent = root->parent;
		if (parent && root->color == RED && parent->color == RED)
		{
			cout << "违反了不能出现连续两个红色节点的规则" << endl;
			return false;
		}

		return _IsValidRBTree(root->left, k, blackCount)
			&& _IsValidRBTree(root->right, k, blackCount);
	}
	int _Height(Node* root)
	{
		if (root == nullptr)
			return 0;

		int leftHeight = _Height(root->left);
		int rightHeight = _Height(root->right);

		return 1 + max(leftHeight, rightHeight);
	}
	//中序遍历（递归）
	void InOrder()
	{
		_InOrder(root);
		cout << endl;
	}
	void _InOrder(Node* root)
	{
		if (root == NULL)
		{
			return;
		}
		else
		{
			_InOrder(root->left);
			cout << root->key << ":" << root->value << " ";
			_InOrder(root->right);
		}
	}
public:
	Node* root = nullptr;
};
void TestRBTree()
{
	//srand((size_t)time(nullptr));
	RB_Tree<int, int> rbt;
	int b[] = { 0,1,2,3,4,5,6,7,8,9,10,11,12};
	// int b[] = { 16,3,7,11,9,26,18,14,15 };
	// int b[] = { 4,2,6,1,3,5,15,7,16,14 };
	// int b[] = { 10,9,8,7,6,5,4,3,2,1 };
	vector<int> a;
	for (size_t i = 0; i < sizeof(b) / sizeof(int); ++i)
	{
		// a.push_back(rand());
		a.push_back(b[i]);
	}
	//int a[] = { 4,2,6,7,3,5 };
	/*vector<int> v;
	v.reserve(100000);

	for (size_t i = 1; i <= v.capacity();  ++i)
	{
		v.push_back(i);
	}*/
	for (auto e : a)
	{
		rbt.Insert(e,e);

		cout << "插入数据 " << e << " 后：" << "树的高度：" << rbt._Height(rbt.root) << " 是否为红黑树：" << rbt.IsValidRBTree();
		cout << "打印二叉树： ";
		rbt.InOrder();

	}
	cout << "-------------------------------------------------------" << endl;
	for (auto e : a)
	{
		rbt.Erase(e);
		cout << "删除数据 " << e << " 后：" << "树的高度：" << rbt._Height(rbt.root) << " 是否为红黑树：" << rbt.IsValidRBTree();
		cout << "打印二叉树： ";
		rbt.InOrder();
	}

}
int main()
{
	TestRBTree();
	system("pause");
	return EXIT_SUCCESS;
}

运行结果如下：

AVL树和红黑树的比较

AVL树 红黑树
如何控制平衡 通过条件平衡因子，子树左右高度差不超过1 用过颜色控制，使得最长路径不超出最短路径的长度的两倍
增删查改的时间复杂度 可以稳定在O(logN) 基本是O(logN)，极端情况下是O(log2N)

总结： AVL树是严格意义上的平衡，红黑树是相对的平衡，两者都很高效，但后者用的更多，因为它旋转更是，实现相对简单，付出的代价少一点。

标签：Node,cur,parent,--,color,BLACK,红黑树,数据结构,节点
From： https://www.cnblogs.com/yzsn12138/p/16962928.html

相关文章

  • SQL Server undocument extended stored procedures
    一些有时候比较有用的扩展存储过程sp_MSgetversionThisextendedstoredprocedurecanbeusedtogetthecurrentversionofMicrosoftSQLServer.Syntax:EXECma......
  • 直播app系统源码，使用scroll-view实现内容列表的竖向滚动
    直播app系统源码，使用scroll-view实现内容列表的竖向滚动app.json{ "pages":[  "pages/index/index" ], "window":{  "navigationBarBackgroundColor":"......
  • SpringBoot pom.xml配置文件详解
    <?xmlversion="1.0"encoding="UTF-8"?><projectxmlns="http://maven.apache.org/POM/4.0.0"xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"   xsi:sch......
  • SLS-Logtail部署
    1.在Linux宿主机上直接部署官方安装示例：https://help.aliyun.com/document_detail/28982.html#section-v94-r79-ru6自建机器安装logtail在上述官网中找到自己的SLS-Pr......
  • 凸函数的判断方法及案例
    目录：凸集、凸函数、单峰函数、拟凸函数凸集：凸集中的任意两点的连线仍然处于凸集中。凸函数：任意两点之间的函数图像都在弦的下方。凸函数的判别方法：https://blog.csdn.ne......
  • 有没有哪里可以打印资料，打印出来可以送上门的？
    在日常的生活、工作和学习中，有不少网友都需要打印一些资料，那么目前可以打印资料的方式有哪些呢？有一些人表示可以直接在学校或小区周边打印店打印资料，不过实体打印店的收费......
  • WebGL之Matrix4库
    1.Matrix4是由<<WebGL编程指南>>作者写的提供WebGL的4*4矩阵操作的方法库，简化我们编写的代码。源代码共享地址，点击链接：Matrix4源代码。参考：https://www.cnblogs.com/w-wa......
  • 学会待办任务清单法，学习效率可提高
    无论是对于大学生还是上班族来说，持续学习的能力都是必不可少的，如果不能够与时俱进的学习各类新事物，就会被时代所抛弃，例如我们可以利用每天的空余时间学习写作、新媒体运营......
  • Java数组和字符串的相互转换
    Java数组和字符串的相互转换字符串转换为数组JavaString类中的toCharArray()方法将字符串转换为字符数组，具体代码如下所示。Stringstr="123abc";char[]arr=......
  • 文字转语音
    文字转语音方法有：1.百度TTS可直接用浏览器访问https://tts.baidu.com/text2audio?tex=helloworld&cuid=baike&lan=ZH&ie=utf-8&ctp=1&pdt=301&vol=9&rate=32&per=02.p......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99