【数据结构】红黑树相关知识详细梳理

25 阅读 0 评论 0 点赞

1. 红黑树的概念

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

例如：

2. 红黑树的性质

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

如何理解以上性质呢：

首先，根据红黑树的主要特点：最长路径中节点个数不会超过最短路径节点
个数的两倍。在以上性质的约束下，我们可以假设出最长路径和最短路径的差值来看看他是否符合要求。例如：

可以看到，通过几条性质的约束，的确可以使最长路径中节点个数不会超过最短路径节点个数的两倍，从而达到整棵树的相对平衡。

3. 红黑树插入

和AVL树一样，在插入节点破坏树的平衡的情况下，红黑树也要进行旋转操作来维持树的平衡。那么什么情况下红黑树会进行旋转，如何旋转呢？

3.1 插入变色/旋转

在进行旋转操作之前，我们首先要决定插入节点的颜色：

黑色可以吗？根据性质4（对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点），如果我们将插入节点设为黑色，则一定会破坏规则，由于树形结构的路径具有唯一性，插入节点一定会违反性质4。

所以我们默认设定除根节点外的（性质2）插入节点为红色。

那么就有了以下几种情况：

情况1：

情况2：

情况3：

3.2删除

和AVL树一样，红黑树的删除比较复杂，掌握插入的原理就够用了，这里不再详细说明。

4. 红黑树模拟实现

4.1 红黑树结构：

首先为了方便封装map和set，我定义了一个头节点方便后续操作。

（头节点的父节点指向红黑树的根，左节点指向红黑树的最小值，右节点指向红黑树的最大值）

enum Color
{
	RED,
	BLACK
};
template<class T>
struct RBTreeNode
{
	RBTreeNode(const T& data = T())//构造
		:_data(data)
		,_color(RED)//新节点默认插入红色
		,_pParent(nullptr)
		,_pLeft(nullptr)
		,_pRight(nullptr)
	{}

	T _data;//数据
	Color _color;//颜色
	RBTreeNode* _pParent;//父节点
	RBTreeNode* _pLeft;//左节点
	RBTreeNode* _pRight;//右节点
};

template<class T>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	//默认构造
	RBTree()
	{
		//为了后序封装map和set，本文在实现时给红黑树多增加了一个头节点
		_pHead = new Node;
		//可以特别把头节点设为黑色
		_pHead->_color = BLACK;
		_pHead->_pLeft = _pHead;
		_pHead->_pRight = _pHead;
		_pHead->_pParent = _pHead;
	}
	//析构
	~RBTree()
	{
		Destroy(GetRoot());
		delete _pHead;
	}
	//插入
	bool Insert(const T& data);
	//查找
	Node* Find(const T& data);
	//获取红黑树最左侧节点
	Node* LeftMost();
	//获取红黑树最右侧节点
	Node* RightMost();
	//检测是否为有效红黑树
	bool IsValidRBTree();
private:
	//检测是否为有效红黑树
	bool _IsValidRBTree(Node* pRoot,size_t k,size_t blackcount);
	//左单旋
	void RotateL(Node* pParent);
	//右单旋
	void RotateR(Node* pParent);
	//获取根节点
	Node* GetRoot();
	//析构
	void Destroy(Node* pRoot);
private:
	Node* _pHead;
};

4.2 构造/析构

//默认构造
RBTree()
{
	//为了后序封装map和set，本文在实现时给红黑树多增加了一个头节点
	_pHead = new Node;
	//可以特别把头节点设为黑色
	_pHead->_color = BLACK;
	_pHead->_pLeft = _pHead;
	_pHead->_pRight = _pHead;
	_pHead->_pParent = _pHead;
}

//析构
~RBTree()
{
	Destroy(GetRoot());
	delete _pHead;
}

//析构
template<class T>
void RBTree<T>::Destroy(Node* pRoot)
{
	if (pRoot == nullptr)
		return;
	Destroy(pRoot->_pLeft);
	Destroy(pRoot->_pRight);
	delete pRoot;
}

4.3 获取元素：

//查找
template<class T>
typename RBTree<T>::Node* RBTree<T>::Find(const T& data)
{
	if (_pHead->_pParent == _pHead)
		return nullptr;
	Node* pcur = GetRoot();
	while (pcur)
	{
		if (data == pcur->_data)
			return pcur;
		if (data > pcur->_data)
			pcur = pcur->_pRight;
		else
			pcur = pcur->_pLeft;
	}
	return pcur;
}

//获取红黑树最左侧节点
template<class T>
typename RBTree<T>::Node* RBTree<T>::LeftMost()
{
	if (GetRoot() == nullptr)
		return nullptr;
	return _pHead->_pLeft;
}

//获取红黑树最右侧节点
template<class T>
typename RBTree<T>::Node* RBTree<T>::RightMost()
{
	if (GetRoot() == nullptr)
		return nullptr;
	return _pHead->_pRight;
}

//获取红黑树根节点
template<class T>
typename RBTree<T>::Node* RBTree<T>::GetRoot()
{
	if (_pHead->_pParent == _pHead)
		return nullptr;
	return _pHead->_pParent;
}

4.4 旋转：

//左单旋
template<class T>
void RBTree<T>::RotateL(Node* pParent)
{
	Node* subR = pParent->_pRight;
	Node* subRL = subR->_pLeft;
	Node* grand = pParent->_pParent;
	subR->_pParent = grand;
	//如果祖父节点不是头节点
	if (grand != _pHead)
	{
		if (pParent == grand->_pRight)
			grand->_pRight = subR;
		else
			grand->_pLeft = subR;
	}
	//如果祖父节点是头节点
	else
	{
		grand->_pParent = subR;
	}
	subR->_pLeft = pParent;
	pParent->_pParent = subR;
	pParent->_pRight = subRL;
	//如果subRL不为空
	if (subRL)
		subRL->_pParent = pParent;
	//变色
	pParent->_color = RED;
	subR->_color = BLACK;
}

//右单旋
template<class T>
void RBTree<T>::RotateR(Node* pParent)
{
	Node* subL = pParent->_pLeft;
	Node* subLR = subL->_pRight;
	Node* grand = pParent->_pParent;
	//如果祖父节点不是头节点
	subL->_pParent = grand;
	if (grand != _pHead)
	{
		if (pParent == grand->_pRight)
			grand->_pRight = subL;
		else
			grand->_pLeft = subL;
	}
	//如果祖父节点是头节点
	else
	{
		grand->_pParent = subL;
	}
	subL->_pRight = pParent;
	pParent->_pParent = subL;
	pParent->_pLeft = subLR;
	//如果subLR不为空
	if (subLR)
		subLR->_pParent = pParent;
	//变色
	pParent->_color = RED;
	subL->_color = BLACK;
}

4.5 插入：

template<class T>
bool RBTree<T>::Insert(const T& data)
{

	Node* pcur = GetRoot();
	//如果树为空，只有头节点
	if (pcur == nullptr)
	{
		//直接插入节点
		Node* newnode = new Node(data);
		_pHead->_pParent = newnode;
		_pHead->_pLeft = newnode;
		_pHead->_pRight = newnode;
		newnode->_pParent = _pHead;
		newnode->_color = BLACK;
		//插入成功，返回true
		return true;
	}
	//树不为空，按照搜索树规律找到插入位置
	Node* parent = nullptr;
	while (pcur)
	{
		//如果树中存在该元素，插入失败
		if (data == pcur->_data)
			return false;
		parent = pcur;
		if (data > pcur->_data)
			pcur = pcur->_pRight;
		else
			pcur = pcur->_pLeft;
	}
	//在正确的位置插入节点
	Node* newnode = new Node(data);
	if (data > parent->_data)
		parent->_pRight = newnode;
	else
		parent->_pLeft = newnode;
	newnode->_pParent = parent;

	//插入后检查红黑树结构是否需要调整
	pcur = newnode;
	Node* grand = nullptr;
	Node* uncle = nullptr;
	//以pcur为基准，循环向上调整
	while (pcur!=GetRoot())
	{
		//更新父，叔节点
		parent = pcur->_pParent;
		grand = parent->_pParent;
		uncle = nullptr;
		//如果父节点颜色为黑，则不需要调整,跳出循环
		if (parent->_color == BLACK)
		{
			break;
		}
		//父节点颜色为红，违反规则，需要调整
		else
		{
			//此时祖父节点一定存在
			if (grand->_pRight == parent)
				uncle = grand->_pLeft;
			else
				uncle = grand->_pRight;

			//如果叔节点存在
			if (uncle)
			{
				//如果叔节点为红色
				if (uncle->_color == RED)
				{
					//父，叔节点都变黑，祖父节点变红
					parent->_color = BLACK;
					uncle->_color = BLACK;
					grand->_color = RED;
					//如果祖父节点为根节点，把祖父节点变黑
					if (grand == GetRoot())
						grand->_color = BLACK;
					//更新pcur
					pcur = grand;
				}
				//如果叔节点为黑色
				else
				{
					//如果叔节点为祖父节点的右节点
					if (uncle == grand->_pRight)
					{
						//如果pcur为parent的右节点
						if (pcur == parent->_pRight)
						{
							//对parent左单旋
							RotateL(parent);
							pcur->_color = RED;
						}
						//此时可看做pcur为parent的左节点的情况
						RotateR(grand);
					}
					//如果叔节点为祖父节点的左节点
					else
					{
						//如果pcur为parent的左节点
						if (pcur == parent->_pLeft)
						{
							//对parent右单旋
							RotateR(parent);
							pcur->_color = RED;
						}
						//此时看看作pcur为parent的右节点的情况
						RotateL(grand);
					}
				}
			}
			//如果叔节点不存在，则pcur一定为新增节点
			else
			{
				//如果parent为grand的右节点
				if (parent == grand->_pRight)
				{
					//如果pcur为parent的左节点
					if (pcur == parent->_pLeft)
					{
						RotateR(parent);
						pcur->_color = RED;
					}	
					RotateL(grand);
				}
				//如果parent为grand的左节点
				else
				{
					//如果pcur为parent的右节点
					if (pcur == parent->_pRight)
					{
						RotateL(parent);
						pcur->_color = RED;
					}
					RotateR(grand);
				}
			}
		}
	}
	//更新最大最小值
	Node* max = GetRoot();
	while (max->_pRight)
	{
		max = max->_pRight;
	}
	Node* min = GetRoot();
	while (min->_pLeft)
	{
		min = min->_pLeft;
	}
	//将最小给头节点的左
	_pHead->_pLeft = min;
	//将最大给头节点的右
	_pHead->_pRight = max;
	//统一返回真
	return true;
}

4.6 检验红黑树：

//检测是否为有效红黑树
template<class T>
bool RBTree<T>::IsValidRBTree()
{
	Node* pRoot = GetRoot();
	if (pRoot == nullptr)
		//空树是有效红黑树
		return true;
	//检查根节点是否为黑色
	if (pRoot->_color != BLACK)
		return false;

	//记录任意一条路径的黑节点个数
	size_t blackcount = 0;
	Node* pcur = pRoot;
	while (pcur)
	{
		if (pcur->_color == BLACK)
			++blackcount;
		pcur = pcur->_pRight;
	}
	size_t k = 0;
	//调用子函数
	return _IsValidRBTree(pRoot,k,blackcount);
}

//检测是否为有效红黑树
template<class T>
bool RBTree<T>::_IsValidRBTree(Node* pRoot, size_t k, size_t blackcount)
{
	if (pRoot == nullptr)
	{
		//一条路径走完，检查黑色节点个数是否和一开始给的相同
		if (k == blackcount)
			return true;
		else
			return false;
	}

	//检查是否有连续的红色节点
	Node* pParent = pRoot->_pParent;
	//根节点为红色才判断pParent，不用考虑根节点
	if ( pRoot->_color == RED && pParent->_color == RED)
		//有连续的红色节点，违反规则
		return false;
	//如果pRoot为黑色节点，计数k+1
	if (pRoot->_color == BLACK)
		++k;
	//继续向子树递归
	return _IsValidRBTree(pRoot->_pLeft, k, blackcount) && _IsValidRBTree(pRoot->_pRight, k, blackcount);
}

5. 红黑树和AVL树的比较

红黑树和AVL树都是高效的平衡二叉树，两者也非常相似，增删改查的时间复杂度都是，区别在于，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。

6. 红黑树的应用

        1. C++ STL库 -- map/set、mutil_map/mutil_set。
        2. Java 库。
        3. linux内核。
        4. 其他一些库。

本站资源均来自互联网，仅供研究学习，禁止违法使用和商用，产生法律纠纷本站概不负责！如果侵犯了您的权益请与我们联系！

转载请注明出处：免费源码网-免费的源码资源网站 » 【数据结构】红黑树相关知识详细梳理

点赞(0) 打赏

本文分类：文章资讯
本文标签：【数据结构】红黑树相关知识详细梳理
浏览次数：25 次浏览
本文链接：https://freeymw.com/article/31051.html

上一篇 > 【Power Query】M函数-List.Sum
下一篇 > Selenium WebDriver和Chrome对照表

评论列表共有 0 条评论

暂无评论