【C++】红黑树插入删除

2023-12-14 17:31:39

在这里插入图片描述

喜欢的点赞,收藏,关注一下把!在这里插入图片描述

1.红黑树的概念

红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。

在这里插入图片描述

AVL树是严格平衡的,因为只要不平衡就旋转保持绝对平衡。

红黑树确保没有一条路径会比其他路径长出俩倍的意思是:最长路径不超过最短路径的2倍

那最长路径不超过最短路径的2倍该如何确保呢?
这是由红黑树的性质来保证的。

2.红黑树的性质

  1. 每个结点不是红色就是黑色
  2. 根节点是黑色的
  3. 如果一个节点是红色的,则它的两个孩子结点是黑色的
  4. 对于每个结点,从该结点到其所有后代叶结点的简单路径上,均包含相同数目的黑色结点
  5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

为什么满足上面的性质,红黑树就能保证:其最长路径中节点个数不会超过最短路径节点个数的两倍?

这里首先说明一下,我们所说的路径是指从根节点到NULL,而不是到叶子节点

前两条性质很简单。我们着重说第3,第4条性质。

3.如果一个节点是红色的,则它的两个孩子结点是黑色的
从这条性质可以得到什么样的消息呢?
这个性质就是说没有连续的红色节点,还需要注意的是,并没有说黑的节点的孩子必须是红色的。(不要脑补)

4.对于每个结点,从该结点到其所有后代叶结点的简单路径上,均包含相同数目的黑色结点
这条性质的意思是每条路径上都包含相同数量的黑色节点

前4条性质,就可以帮我们确保红黑树最长路径不超过最短路径的2倍了,为什么这样说呢?
先想一想这样一个问题:一颗红黑树如果只看黑色节点,满足什么状态?
根据性质4,每条路径上都包含相同数量的黑色节点。
如果只看黑色,是不是接近满二叉树状态。

在这里插入图片描述
极限情况下:
最短路径:全黑,一条路径黑色节点的数量
根据性质3和性质4,那最长路径就出来了。

在这里插入图片描述

最长路径:一黑一红相间的路径

5.每个叶子结点都是黑色的(此处的叶子结点指的是空结点,就是NIL节点)
红黑树的叶子节点和我们所熟知的叶子节点是不一样。
那就按照我们所熟知的叶子节点,我就给它黑色的,会有什么样的后果?
在这里插入图片描述
此时这颗树是不是违背了性质4:每条路径上都有包含相同数量黑色节点。(刚才已经说明这个路径指的是到NULL)

如果换成下面这个情况,再看性质5,是不是就明白了。
在这里插入图片描述

我们再说一说近似平衡。那红黑树性能最优情况,最差情况是什么样的呢?
最优情况: 左右平衡
这颗红黑树是一个全黑或者每条路径都是一黑一红间隔的满二叉树

最差情况: 左右越不平衡
假设这颗红黑树,左子树全黑,右子树一黑一红,长的是短的2倍

极限一点考虑,如果我们只考虑全黑呢,是不是就接近满二叉树。
全黑的路径长度是h,只有一两条一黑一红间隔的路径
2^h-1+ 红色节点=N ----->log2N

最长路径是不是就是2log2N

严格来说红黑树没有AVL效率好,但是这几乎不影响。
假设有10亿个数
log2n=10亿,n=30,AVL树只要找30次,就拿红黑树最差情况中最长路径那也只是60次,这相对于计算机CPU每秒上亿次计算有影响吗?并没有。

所以严格来说红黑树比AVL树效率差,但整体来说我们并不觉得差多少。
虽然红黑树没有AVL树效率那么好,但是AVL也带来了一个问题,AVL是通过不平衡就旋转保持绝对平衡的,但旋转是有代价的。而红黑树并不是这样,只是近似平衡,少了很多旋转。

3.红黑树节点的定义

//枚举
enum Coloer
{
	RED,
	BLACK
};

template<class T,class V>
struct RBTreeNode
{
	pair<T, V> _kv;
	RBTreeNode<T, V>* _left;
	RBTreeNode<T, V>* _right;
	RBTreeNode<T, V>* _parent;
	Coloer _col;

	RBTreeNode(const pair<T,V>& kv)
		:_kv(kv)
		,_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_col(RED)
	{}
};

4.红黑树的插入

红黑树也是一颗二叉搜索树,所以我们还是按照以往的方式进行插入。不懂的可以看二叉搜索树有详细讲解。

先写一个框架,我们在慢慢完善内容

template<class T,class V>
class RBTree
{
	typedef RBTreeNode<T, V> Node;
public:
	bool Insert(const pair<T, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;//红黑树根是黑色
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;
		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 (cur->_kv.first < parent->_kv.first)
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_right = cur;
			cur->_parent = parent;
		}

		//检测红黑树性质是否遭到破坏


		return true;
	}

private:
	Node _root = nullptr;
};

现在框架还差一步,才真正完成。
新插节点,它应该是什么颜色?
如果是黑的行不行?

其实不能是黑色,插入黑色这条路径一定多一个黑色节点,那其他路径都少了一个,这样调整起来太麻烦了。所以插入节点颜色一定是红色,如果父亲是黑色那没什么问题,不用调整,父亲是红色,违反性质3,那就处理一下。

接下来我们就插入红色节点如果父亲是红色,而破坏性质3,对红黑树分讨论。

约定:cur为当前节点,p为父节点,g为祖父节点,u为叔叔节点

情形一

cur为红,p为红,g为黑,u存在且为红

在这里插入图片描述

孩子是红的,父亲是红的,祖父一定是黑色,这个时候叔叔就是我们的关键
注意,在插入的时候,叔叔一直是我们关注的重点,它是影响我们调整的方向

那情况一该怎么解决呢?

两个红色不能相连,所以我们需要把父亲变黑,但是父亲变黑的,祖父原本就是黑色。那这条路径就多了一个黑色节点。因此我们需要把祖父变红,
在这里插入图片描述
但是叔叔那条路径就少了一个黑色节点,那把叔叔也变黑。在这里插入图片描述
如果g是根节点,调整完成后,需要将就改成黑色。

如果g是子树,g一定有父亲,且g的父亲如果是红色,则需要继续向上调整
在这里插入图片描述

情形一解决方式:将p,u改成黑色,g改成红色,然后把g当初cur,继续向上调整。

上面是抽象图,我们接下来看看具体图

在这里插入图片描述

情形二

cur为红,p为红,g为黑,u不存在/u存在且为黑
在这里插入图片描述

u的情况有两种:
1.如果u节点不存在,那cur一定是新插入节点,因为如果cur不是新插入节点,则cur和p一定右一个节点颜色是黑的,就不满足性质4,每条路径黑色节点个数相同。
在这里插入图片描述
2.如果u存在,则一定是黑色,因为改成u存在且为红色我们已经分析过了
在这里插入图片描述
情形二解决方法:
p为g的左孩子,cur为p的左孩子,则进行右单旋转;相反,
p为g的右孩子,cur为p的右孩子,则进行左单旋转
p、g变色–p变黑,g变红

在这里插入图片描述
注意,旋转+变色调整之后,就不需要向上继续调整了,因为我们把这个子树的根变成黑色的了。

并且注意没,刚才所说的都是cur和p都在同一侧,所以都是单旋情况。

情形三

cur为红,p为红,g为黑,u不存在/u存在且为黑

虽然和情形二是一样,但是这次cur和p不在同一侧,双旋
在这里插入图片描述
在这里插入图片描述
情形三解决方法:
p为g的左孩子,cur为p的右孩子,则针对p做左单旋转,再以cur做右旋
p为g的右孩子,cur为p的左孩子,则针对p做右单旋转,再以cur做左旋
cur、g变色–cur变黑色,g变红色

注意只要是旋转+变色都不需要向上调整了,直接结束调整即可。

插入的完整代码

下面这部分代码是写的时候需要注意的东西,所以单独拿出来说一下

bool Insert(const pair<T, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;//红黑树根是黑色
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;
		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 (cur->_kv.first < parent->_kv.first)
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_right = cur;
			cur->_parent = parent;
		}

		//调整

		while (parent && parent->_col == RED) //所以这里parent判断一下
		{
			Node* grandfather = parent->_parent;
			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				if (uncle && uncle->_col == RED)//情形一
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					//继续向上调整
					cur = grandfather;
					parent = cur->_parent; //注意此时grandfather可能为根,那parent就有可能是野指针了
				}
			}

			
		}
		_root->_col = BLACK;//此时还需要把_root变成黑色,不过不管什么时候根都是黑色,所以在外面给一下

		return true;
	}

完整代码

bool Insert(const pair<T, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;//红黑树根是黑色
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;
		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 (cur->_kv.first < parent->_kv.first)
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_right = cur;
			cur->_parent = parent;
		}

		//调整

		while (parent && parent->_col == RED) //所以这里parent判断一下
		{
			Node* grandfather = parent->_parent;
			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				if (uncle && uncle->_col == RED)//情形一
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					//继续向上调整
					cur = grandfather;
					parent = cur->_parent; //注意此时grandfather可能为根,那parent就有可能是野指针了
				}
				else 
				{
					//这里不需要再管uncle存再不存在了,旋转变色都与它无关
					if (cur == parent->_left)//情形二,不管uncle存不存,cur和parent在同一侧都单旋
					{
						RotaleR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else//情形三,不管uncle存不存,cur和parent在异侧双旋
					{
						RotaleL(parent);
						RotaleR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
			else
			{
				Node* uncle = grandfather->_left;
				if (uncle && uncle->_col == RED)//情形一
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_right)//情形二
					{
						RotaleL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						RotaleR(parent);
						RotaleL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}

			
		}
		_root->_col = BLACK;//此时还需要把_root变成黑色,不过不管什么时候根都是黑色,所以在外面给一下

		return true;
	}
	
	void RotaleL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;

		Node* ppNode = parent->_parent;
		subR->_left = parent;
		parent->_parent = subR;

		if (ppNode == nullptr)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else
		{
			if (parent == ppNode->_left)
			{
				ppNode->_left = subR;
			}
			else
			{
				ppNode->_right = subR;
			}
			subR->_parent = ppNode;
		}
	}

	void RotaleR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;

		Node* ppNode = parent->_parent;
		subL->_right = parent;
		parent->_parent = subL;

		if (ppNode == nullptr)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (parent == ppNode->_left)
			{
				ppNode->_left = subL;
			}
			else
			{
				ppNode->_right = subL;
			}
			subL->_parent = ppNode;
		}
	}

5.红黑树的删除

红黑树删除其实挺难的。情况太多了,但是从大方向上来说,删除节点无非就是三种情况:叶子节点,一个孩子的节点,两个孩子的节点,被删的是节点是红色,黑色,这些情况组合在一起删除,其实当我们真正组合分析下来,还是挺简单的。

删除节点的三种情况

1.删除叶子节点(非NIL节点)

  1. 如果是红色,直接删除即可,不影响黑高值
  2. 如果是黑色,导致黑高失衡需要进行平衡调整

在红黑树的删除中,删除红色是最没影响的。
在这里插入图片描述
删除黑色叶子节点,其实一条路径黑色节点就少了一个,导致违背性质3,需要调整
在这里插入图片描述
同样这个情况也是红黑树删除中最麻烦的,等会在分析。

2.删除只有一个叶子节点的节点

  1. 此时删除节点只能是黑色,其子节点为红色,否则就无法满足红黑树的性质
  2. 将红色子节点的值拷贝到父节点上,将删除节点转成删除红色叶子节点(如情况1.1)

那为什么删除节点只能是黑色,其子节点为红色呢?反过来不行吗?
在这里插入图片描述

3.删除两个子节点的的节点

  1. 使用前序或者后继节点作为替代节点,转换为1或2的情况。

经过这样的分析是不是视野清晰起来了。

删除节点步骤

  1. 没找到删除节点直接返回
  2. 如果删除的是唯一根节点,_root置空并返回
  3. 删除有两个子节点的节点
    1. 使用前序或者后继节点作为替换的删除节点
    2. 将del指向替换节点,转换出4或5的情况处理
  4. 删除只有一个节点的节点时,删除节点只能是黑色,其子节点为红色,否则无法满足红黑树的性质
    1. 将红色子节点的值拷贝到父节点
    2. 将删除节点转换为删除红色叶子节点,即5.2
  5. 删除叶子节点
    1. 对要删除的黑色叶子节点进行调整(情况最复杂)
    2. 删除红黑两种叶子节点(红色直接删除,黑色但调整好了也直接删除)

我们先把整个思路写好,然后一点一点分析调整的情况。

//红黑树删除
	bool Erase(const pair<T, V>& kv)
	{
		if (_root == nullptr)
			return false;

		Node* del = _root;
		while (del)
		{
			if (del->_kv.first < kv.first)
			{
				del = del->_right;
			}
			else if (del->_kv.first > kv.first)
			{
				del = del->_left;
			}
			else
			{
				break;
			}
		}
		//没找到
		if (del == nullptr)
			return false;
		//del是唯一的根节点
		if (del ==_root && del->_left == nullptr && del->_right == nullptr)
		{
			delete _root;
			_root = nullptr;
			return true;
		}
		//del有两个孩子
		if (del->_left != nullptr && del->_right != nullptr)
		{
			//找后序替代删除
			Node* MinRight = del->_right;
			while (MinRight->_left)
			{
				MinRight = MinRight->_left;
			}
			del->_kv = MinRight->_kv;
			del = MinRight;//删除节点指向替换节点
		}
		//del只有一个孩子
		if ((del->_left != nullptr && del->_right == nullptr) || (del->_right != nullptr && del->_left == nullptr))
		{
			//只有一个孩子,父亲一定为黑,孩子一定为红
			//1.将红色节点的值赋值给父亲
			//2.将删除节点转换成删除红色叶子节点
			Node* child = del->_left == nullptr ? del->_right : del->_left;
			del->_kv = child->_kv;
			del = child;//删除节点指向替代的红色节点
		}


		//上面有两个孩子/一个孩子最终都会转换成叶子节点
		
		//叶子节点是黑色,直接删除违背性质4,还需要调整
		if (del->_col == BLACK)
		{
			//调整
			AdjustRBTreeBalance(del);
		}

		//叶子节点是红色或是黑色但调整好了,就可以直接删除了
		//并且我们这是三叉,不用找父亲
		Node* parent = del->_parent;
		if (del == parent->_left)
		{
			parent->_left = nullptr;
		}
		else
		{
			parent->_right = nullptr;
		}
		delete del;
		return true;
		
	}

删除黑色叶子节点调整平衡情况分析

删除黑色叶子节点需要调整的情况有三种

  1. 根节点,直接返回删除
  2. 兄弟节点为黑色
    1. 兄弟有红色子节点
    2. 兄弟无红色字节的
  3. 兄弟为红色

删除的是黑色叶子节点,我们着重关注它的兄弟节点

第一种情况没什么好说的。下面就第二种第三种情况详细分析。

2.兄弟节点为黑色

1.兄弟有红色子节点

在这里插入图片描述这里细分成三种情况。
1.1兄弟有红色左子节点

在这里插入图片描述
1.2兄弟有两个红色子节点
在这里插入图片描述
1.3兄弟有红色右子节点
在这里插入图片描述

注意这里D是黑色右叶子节点,D当然还有可能是黑色左孩子节点,那旋转和变色就反过来了,这里就不再演示,写代码一定注意分情况。

我们可以总结总结一下
在在这里插入图片描述
这里插入图片描述

2.兄弟无红色子节点

兄弟无红色子节点,这里依照父亲节点颜色要分成两种情况。
2.1父亲是红色节点
在这里插入图片描述

2.2父亲是黑色节点
在这里插入图片描述
这里还像上面一样,父变黑,兄变黑可以解决问题吗?
当然如果上图就是我们整颗树,这种方法肯定解决问题了。
那是以p为根的子树呢?
这样简单变色,然后删除D,这条路径相对其他路径来说,就少了一个黑色节点,违背了性质4。
所以父亲节点是黑色的具体做法

1.将兄弟节点染红
2.把父节点当作新的删除节点,递归调用前面的方法,进行相应处理,直至遇到红色父亲节点并将其染黑,兄弟染红或者遇到根节点结束

在这里插入图片描述

3.兄弟是红色节点

兄弟是红色节点,那父亲一定是黑色的,否则违背性质3,并且这个兄弟一定有两个黑色字节的,否则违背性质4 。
在这里插入图片描述

自此关于删除黑色叶子节点调整的所有情况都说完了,其实按照大方向然后再细分一些小的方向也还可以。
下面总结一下。
在这里插入图片描述

黑色节点调整平衡方法步骤

  1. 是根节点:直接返回删除即可
  2. 兄弟黑色
    1. 兄弟有子:黑不够,侄来凑
      1. 根据LL,RR,RL,LR类型旋转+变色
    2. 兄弟无子:兄无够,父红头
      1. 父节点是红色:父变黑 兄变红
      2. 父节点是黑色:兄变红 父作为新删除(调整)节点向上递归调整
  3. 兄弟红色
    兄弟红,旋中黑;随父侄,黑变红
    1. 兄弟是左子树:右旋+兄变黑+兄右变红
    2. 兄弟是左子树:左旋+兄边黑+兄左变红

删除的完整代码

//这里是为了能够返回旋转类型而随便定义的,没有任何实际意义
//如果不想写GetRotaleType函数,可以直接在AdjustRBTreeBalance判断都是一样的结果
#define LL 1
#define RR 2
#define LR 3
#define RL 4

	int GetRotaleType(Node* Brother)
	{
		Node* parent = Brother->_parent;
		if (Brother == parent->_left)//Brother是左子树
		{
			//Brother,只有一个孩子并且和它同侧,或者有两个孩子都单旋
			if (Brother->_left != nullptr && Brother->_left->_col == RED)
			{
				return RR;
			}
			//rother,只有一个孩子并且和它异侧,双旋
			if(Brother->_right != nullptr && Brother->_right->_col == RED)
			{
				return LR;
			}
		}
		else//Brother是右子树
		{
			//同上
			if (Brother->_right != nullptr && Brother->_right->_col == RED)
			{
				return LL;
			}
			if(Brother->_left != nullptr && Brother->_left->_col == RED)
			{
				return RL;
			}
		}
		//无红色子节点不旋转
		return 0;
	}
	

	void *AdjustRBTreeBalance*(Node* del)
	{
		//1.是根节点
		//2.兄弟是黑色节点 ------ 2.1兄弟有红色子节点  2.2兄弟无红色子节点
		//3.兄弟是红色节点

		//1.是根节点,刚开始我们就把del是根节点情况考虑过了
		//这里del还是根的情况,是因为下面我们有递归,递归到根要结束
		//注意我们这里的del是形参,形参的改变并不影响实参,所有最后删除不会是删除根,而造成删除出现野指针的情况
		if (del == _root)
			return;

		//2.兄弟是黑色节点

		//兄弟要分左右两种情况旋转
		Node* parent = del->_parent;
		Node* Brother = parent->_left == del ? parent->_right : parent->_left;
		if (Brother->_col == BLACK)
		{
			int type = GetRotaleType(Brother);
			switch(type)//兄不够,侄来凑
			{
				// 2.1兄弟有红色子节点 ---- 通过旋转变色达到平衡
				case LL: //变色原则:恢复未删除前各个位置颜色  爷孙变色,兄变父色
					Brother->_col = parent->_col;//兄弟旋转后取代父亲节点颜色
					Brother->_right->_col = parent->_col = BLACK;//父亲和侄节点变黑
					RotaleL(parent);
					break;
				case RR:
					Brother->_col = parent->_col;
					Brother->_left->_col = parent->_col = BLACK;
					RotaleR(parent);
					break;
				case LR:
					Brother->_right->_col = parent->_col;//侄节点变成父节点颜色
					parent->_col = BLACK;//父节点变黑
					RotaleL(Brother);
					RotaleR(parent);
					break;
				case RL:
					Brother->_left->_col = parent->_col;
					parent->_col = BLACK;
					RotaleR(Brother);
					RotaleL(parent);
				default://兄无后,父红头
					//2.2兄弟无红色子节点 ---- 2.2.1父节点是红色   2.2.2父节点是黑色
					if (parent->_col == RED)//2.2.1父节点是红色 ---交换父兄颜色
					{
						parent->_col = BLACK;
						Brother->_col = RED;
					}
					else//父节点是黑色,需要向上递归调整---虽然这个最麻烦,但是我们以前把情况都写出来了,直接递归即可
					{
						//del被删,以parent为根节点违背性质4,因此兄先变红先把以parent为根先平衡
						//然后在以parent为被删节点,向上递归调用,注意不是真的要删parent,从始至终删的都是del
						Brother->_col = RED;
						AdjustRBTreeBalance(parent);
					}
			}
		}
		else//3.兄弟是红色节点  兄弟红,旋黑中,随父侄,黑变红
		{

			//1.兄弟是左子树:右旋---右侄变红

			//兄弟是红色节点,它父亲必定是黑色,同时它的孩子必定有两个黑节点,否则违背性质4
			if (Brother == parent->_left)
			{
				Brother->_col = BLACK;//兄弟变色
				Brother->_right->_col = RED;//随着父亲的侄子,颜色变红

				//虽然Brother有两个孩子,但是单旋就可以
				RotaleR(parent);

			}
			else //2.兄弟是右子树:左旋--左侄变红
			{
				Brother->_col = BLACK;
				Brother->_left->_col = RED;
				RotaleL(parent);

			} 
		}
	}

//红黑树删除
	bool Erase(const pair<T, V>& kv)
	{
		if (_root == nullptr)
			return false;

		Node* del = _root;
		while (del)
		{
			if (del->_kv.first < kv.first)
			{
				del = del->_right;
			}
			else if (del->_kv.first > kv.first)
			{
				del = del->_left;
			}
			else
			{
				break;
			}
		}
		//没找到
		if (del == nullptr)
			return false;
		//del是唯一的根节点
		if (del ==_root && del->_left == nullptr && del->_right == nullptr)
		{
			delete _root;
			_root = nullptr;
			return true;
		}
		//del有两个孩子
		if (del->_left != nullptr && del->_right != nullptr)
		{
			//找后序替代删除
			Node* MinRight = del->_right;
			while (MinRight->_left)
			{
				MinRight = MinRight->_left;
			}
			del->_kv = MinRight->_kv;
			del = MinRight;
		}
		//del只有一个孩子
		if ((del->_left != nullptr && del->_right == nullptr) || (del->_right != nullptr && del->_left == nullptr))
		{
			//只有一个孩子,父亲一定为黑,孩子一定为红
			//1.将红色节点的值赋值给父亲
			//2.将删除节点转换成删除红色叶子节点
			Node* child = del->_left == nullptr ? del->_right : del->_left;
			del->_kv = child->_kv;
			del = child;
		}


		//上面有两个孩子/一个孩子最终都会转换成叶子节点
		
		//叶子节点是黑色,直接删除违背性质4,还需要调整
		if (del->_col == BLACK)
		{
			AdjustRBTreeBalance(del);
		}

		//叶子节点是红色或是黑色但调整好了,就可以直接删除了
		//并且我们这是三叉,不用找父亲
		Node* parent = del->_parent;
		if (del == parent->_left)
		{
			parent->_left = nullptr;
		}
		else
		{
			parent->_right = nullptr;
		}
		delete del;
		return true;
		
	}

6.判断是否是红黑树

给你一颗红黑树你会怎么判断它是否是红黑树呢。
如果用最长路径不超过最短路径的2倍可不可以?
答案是不可以。如果确实是最长路径不超过最短路径2倍,但是其它路径颜色不符合红黑树,这颗树还是红黑树吗?显而易见不是的。

所有我们应该用红黑树的性质来判断。

  1. 每个结点不是红色就是黑色
  2. 根节点是黑色的
  3. 如果一个节点是红色的,则它的两个孩子结点是黑色的
  4. 对于每个结点,从该结点到其所有后代叶结点的简单路径上,均包含相同数目的黑色结点
  5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

我们主要用第2,3,4的性质
先给一个框架

	bool IsRBTree(Node* root)
	{
		if (_root == nullptr)
			return true;
		
		//第2条性质
		if (_root->_col != BLACK)
			return false;
		
		//接下来就是第3,4条性质
	}

现在有一个问题第3条性质你要怎么样用?
首先肯定得用递归把整颗树都查完这是肯定的。
然后呢,如果碰见红色节点,你是拿它与它的父亲做比较,还是它的孩子做比较呢?

应该选择与它的父亲做比较,看是不是连续的红色节点。这是因为一个节点它孩子情况有很多,你需要判断有没有孩子,左孩子还是右孩子,这样写代码太繁琐,而选择与它父亲做比较,因为它只有一个父亲。

	bool Check(const Node* root)
	{
		if (root == nullptr)
			return true;

		if (root->_col == RED && root->_parent->_col == RED)
			return false;

		return Check(root->_left) && Check(root->_right);
	}

	bool IsRBTree()
	{
		if (_root == nullptr)
			return true;

		if (_root->_col != BLACK)
			return false;

		//不能拿IsRBTree当递归使用,自己重新写一个
		Check(_root);
	}

性质4:每条路径都有相同的黑色节点,该怎么检验呢?
既然我们刚才已经写了递归检验整棵树,那我们依旧还是用这个递归,改造一下。

就拿下图来说,每个节点都给一个值,来记录根节点到该节点的黑色节点的数量。 当递归走到空就能探查到每条路径黑色节点的数量。
在这里插入图片描述
这里给两个思路
1.把每层黑色节点数量都存下来,最后在比较
2.给一个参考值,参考值是红黑树中某条路径的黑色节点的数量,递归每条路径走完都与这个值比较,不相等就报错

	bool Check(const Node* root,int blacknum,int ref)
	{
		if (root == nullptr)
		{
			if (blacknum != ref)
			{
				cout << "违反第四条规定" << ";" << "每条路径都有相同的黑色节点" << endl;
				return false;
			}

			return true;
		}

		if (root->_col == RED && root->_parent->_col == RED)
		{
			//打印错误信息,方便查找
			cout << "违反第3条规定" << ":" << root->_kv.first << "不能有相连的红色节点" << endl;
			return false;		
		}


		if (root->_col == BLACK)
			++blacknum;

		return Check(root->_left,blacknum,ref) && Check(root->_right,blacknum,ref);
	}

	bool IsRBTree()
	{
		if (_root == nullptr)
			return true;

		if (_root->_col != BLACK)
			return false;

		//参考值
		int ref = 0;
		Node* left = _root;
		while (left)
		{
			if (left->_col == BLACK)
				++ref;

			left = left->_left;
		}

		return Check(_root,0,ref);
	}

文章来源:https://blog.csdn.net/fight_p/article/details/134952054
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。