标签搜索

目 录CONTENT

文章目录

红黑树.md

小小城
2021-08-22 / 0 评论 / 0 点赞 / 9 阅读 / 4,778 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-04,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

红黑树的模拟实现

@[toc]

本篇博客当中使用了二叉搜索树和AVL树的相关性质:
二叉搜索树
AVL树

1. 红黑树的概念

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

在这里插入图片描述

2. 红黑树的性质

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

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

  1. 如何让红黑树的最长路径中节点个数超过最短路径节点个数的两倍?
  2. 必定要让一条路径最长,一条路径最短,最长有多长?最短有多短?
  3. 如果让一条路径有很多的黑色节点,根据性质4那么另一条路径,也会有相同的黑色节点,即黑色节点不会影响最长路径中节点个数和最短路径节点个数。
  4. 所以为了让一条路径上的节点变多,就只能增加红色节点,而又根据性质3,不能出现连续的红色节点,所以红色和黑色只能交替出现。
  5. 又根据性质2,红黑树的根节点是黑色的,所以最长路径当中红色节点的个数也只能和黑色节点的个数相等,即最好的情况下是最长路径中节点个数刚好等于最短路径节点个数的两倍。并没有违反性质。

3. 红黑树节点的定义

// 节点的颜色
enum Color{RED, BLACK};
// 红黑树节点的定义
template<class ValueType>
struct RBTreeNode
{
RBTreeNode(const ValueType& data = ValueType(),Color color = RED)
: _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr)
, _data(data), _color(color)
{}
RBTreeNode<ValueType>* _pLeft; // 节点的左孩子
RBTreeNode<ValueType>* _pRight; // 节点的右孩子
RBTreeNode<ValueType>* _pParent; // 节点的双亲(红黑树需要旋转,为了实现简单给出该字段)
ValueType _data; // 节点的值域
Color _color; // 节点的颜色
};

在节点的定义中,为什么要将节点的默认颜色给成红色的

  • 其实给出黑色和红色都是可以的
  • 如果给成黑色,那么在插完某一个节点后,在插左/右孩子的时候就违反性质4,左右子树的路径上黑色节点的个数不同,就要进行调整
  • 如果给成红色,如过插入节点的父亲节点是红色的就会违反性质3,不能出现连续的红色节点,就需调整
  • 相对而言,默认颜色给成红色的调整频率小一些,不可能插入节点的父亲节点都是红色
  • 所以默认颜色给成红色

4 .红黑树结构

为了后续实现关联式容器简单,红黑树的实现中增加一个头结点,因为跟节点必须为黑色,为了与根节点进行区分,将头结点给成黑色,并且让头结点的 pParent 域指向红黑树的根节点,pLeft域指向红黑树中最小的节点,_pRight域指向红黑树中最大的节点,如下:

在这里插入图片描述

5 .红黑树的插入操作

红黑树是在二叉搜索树的基础上加上其平衡限制条件,因此红黑树的插入可分为两步:

  1. 按照二叉搜索的树规则插入新节点
template<class ValueType>
class RBTree
{
	//……
	bool Insert(const ValueType& data)
	{
		PNode& pRoot = GetRoot();
		if (nullptr == pRoot)
		{
			pRoot = new Node(data, BLACK);
			// 根的双亲为头节点
			pRoot->_pParent = _pHead;
			_pHead->_pParent = pRoot;
		}
		else
		{
			// 1. 按照二叉搜索的树方式插入新节点
			// 2. 检测新节点插入后,红黑树的性质是否造到破坏,
			// 若满足直接退出,否则对红黑树进行旋转着色处理
		}
		// 根节点的颜色可能被修改,将其改回黑色
		pRoot->_color = BLACK;
		
		_pHead->_pLeft = LeftMost();
		_pHead->_pRight = RightMost();
	return true;
}
private:
	PNode& GetRoot()
	{ 
		return _pHead->_pParent;
	}

	// 获取红黑树中最小节点,即最左侧节点
	PNode LeftMost();
	
	// 获取红黑树中最大节点,即最右侧节点
	PNode RightMost();
private:
	PNode _pHead;
};

2 . 检测新节点插入后,红黑树的性质是否造到破坏

对于这种情况我们就需要仔细的品了!细品。

情况一
因为新节点的默认颜色是红色,因此:如果其双亲节点的颜色是黑色,没有违反红黑树任何性质,则不需要调整;

但当新插入节点的双亲节点颜色为红色时,就违反了性质三不能有连在一起的红色节点,此时需要对红黑树分情况来讨论:

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

情况二cur为红,p为红,g为黑,u存在且为红

在这里插入图片描述
cur和p违法反了性质3,把cur改为红色还是把p改为红色呢?

1.如果直接把cur改为黑色,那么以g为根节点的左右子树当中的黑色节点个数不相同,违反性质4,所以还需要把u改为黑色,这样就保证局部符合红黑树的性质。

2.又因为g可能是根节点,也有可能是某颗子树

3.如果g为根节点,那么调整就结束了,如果g不为根节点,假设g的父亲节点为gg,那么我们在其左子树/右子树的路径上增加了一个黑色节点,那么节点gg的左右两个子树的路径上黑色节点的个数是不相等的,违反性质4.

4.所以还需要把黑色节点的个数减少一个,就把g变为红色,如果gg为红色还需要再继续向上调整。

5.此时你发现p和g又都是红色的了,又违反了性质3,所以把cur改为红色是不可以的。

正确的操作是:把p、u改为黑色,g改为红色,把cur移到g位置,p移到gg位置继续向上判断
在这里插入图片描述
完整调整图:
在这里插入图片描述

情况二的解决方式:将p,u改为黑,g改为红,然后把g当成cur,继续向上调整

情况三:cur为红,p为红,g为黑,u不存在/u为黑
在这里插入图片描述
解决方式:

1.如果p在g的左子树上,cur在p的左子树上,就把p改为黑色,那么如果g的父亲节点存在,那么同样违反性质4,所以还需要把g改为红色,再进行右单旋。

2.如果p在g的右子树上,cur在p的右子树上,就把p改为黑色,那么如果g的父亲节点存在,那么同样违反性质4,所以还需要把g改为红色,再进行左单旋

完整调整图:
在这里插入图片描述
p为g的左孩子,cur为p的左孩子,则进行右单旋转 相反,
p为g的右孩子,cur为p的右孩子,则进行左单旋转
p、g变色--p变黑,g变红

情况四: cur为红,p为红,g为黑,u不存在/u为黑

在这里插入图片描述

p为g的左孩子,cur为p的右孩子,则针对p做左单旋转;相反,
p为g的右孩子,cur为p的左孩子,则针对p做右单旋转
则转换成了情况3

到这里红黑树的所有情况都讨论完了!!!

6.代码:

bool Insert(const ValueType& data)
{
	// ...
	// 新节点插入后,如果其双亲节点的颜色为空色,则违反性质3:不能有连在一起的红色结点
	while(pParent && RED == pParent->_color)
	{
		// 注意:grandFather一定存在
		// 因为pParent存在,且不是黑色节点,则pParent一定不是根,则其一定有双亲
		PNode grandFather = pParent->_pParent;
		// 先讨论左侧情况
		if(pParent == grandFather->_pLeft)
		{
			PNode unclue = grandFather->_pRight;
			
			// 情况二:叔叔节点存在,且为红
			if(unclue && RED == unclue->_color)
			{
				pParent->_color = BLACK;
				unclue->_color = BLACK;
				grandFather->_color = RED;

				//向上调整
				pCur = grandFather;
				pParent = pCur->_pParent;
			}
			else
			{
				// 情况三/四:叔叔节点不存在,或者叔叔节点存在且为黑
				if(pCur == pParent->_pRight)
				{
					//转化为情况三:
					_RotateLeft(pParent);
					swap(pParent, pCur);
				}
				// 情况四最后转化成情况三
				grandFather->_color = RED;
				pParent->_color = BLACK;
				_RotateRight(grandFather);
			}
		}
		else
		{
			// ...相反的而已
		}
	}
	// ...
}

7. 红黑树的验证

红黑树写出来了就需要验证,我们总不能拿手去画一个把,如果数字少一点还好,现在给你10000个,去给我画!!!!

红黑树的检测分为两步:

  1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)
  2. 检测其是否满足红黑树的性质
bool IsValidRBTree()
{
	PNode pRoot = GetRoot();
	
	// 空树也是红黑树
	if (nullptr == pRoot)
		return true;
		
	// 检测根节点是否满足情况
	if (BLACK != pRoot->_color)
	{
		cout << "违反红黑树性质二:根节点必须为黑色" << endl;
		return false;
	}
	
	// 获取任意一条路径中黑色节点的个数
	size_t blackCount = 0;
	PNode pCur = pRoot;
	while (pCur)
	{
		if (BLACK == pCur->_color)
			blackCount++;
		pCur = pCur->_pLeft;
	}
	
	// 检测是否满足红黑树的性质,k用来记录路径中黑色节点的个数
	size_t k = 0;
	return _IsValidRBTree(pRoot, k, blackCount);
}

bool _IsValidRBTree(PNode pRoot, size_t k, const size_t blackCount)
{
	//走到null之后,判断k和black是否相等
	if (nullptr == pRoot)
	{
		if (k != blackCount)
		{
			cout << "违反性质四:每条路径中黑色节点的个数必须相同" << endl;
			return false;
		}
		return true;
	}
	// 统计黑色节点的个数
	if (BLACK == pRoot->_color)
		k++;
		
	// 检测当前节点与其双亲是否都为红色
	PNode pParent = pRoot->_pParent;
	if (pParent && RED == pParent->_color && RED == pRoot->_color)
	{
		cout << "违反性质三:没有连在一起的红色节点" << endl;
		return false;
	}
	
	return _IsValidRBTree(pRoot->_pLeft, k, blackCount) &&
			_IsValidRBTree(pRoot->_pRight, k, blackCount);
}

8. 红黑树的删除

红黑树的删除

0

评论区