【C++进阶学习】第八弹——红黑树的原理与实现——探讨树形结构存储的最优解

2024-07-22 19:48:04
开发
16

二叉搜索树：【C++进阶学习】第五弹——二叉搜索树——二叉树进阶及set和map的铺垫-CSDN博客

AVL树：

【C++进阶学习】第七弹——AVL树——树形结构存储数据的经典模块-CSDN博客

前言：

在前面，我们已经学习了二叉搜索树和它的改进AVL树，今天，我们来学习另一种由二叉搜索树改进而来的树形结构——红黑树

一、红黑树的概念

红黑树是一种特殊的二叉树，它的每个节点都增加一个存储为表示颜色，要么是黑色，要么是白色。并且通过对每条路径上添加节点时节点的颜色限制，来确保每个路径上的黑色节点数量一致，且最长路径长度最多是最短路径长度的两倍，因此达到平衡。

二、红黑树的性质

红黑树有以下五个性质：

节点是红色或黑色：每个节点都有一个颜色属性，颜色可以是红色或黑色。

根节点是黑色：树的根节点必须是黑色。

红色节点的子节点是黑色：如果一个节点是红色，则它的两个子节点必须是黑色（即不能有两个连续的红色节点）。

每个节点到其每个叶子节点的路径都包含相同数量的黑色节点：从任何节点到其每个叶子节点的路径上，经过的黑色节点的数量必须相同。

叶子节点是黑色：红黑树的叶子节点（通常是指空节点）被视为黑色。

三、红黑树的节点结构

template<class K, class V>
struct BSTreeNode
{
	BSTreeNode<K, V>* _left;    //左子树
	BSTreeNode<K, V>* _right;   //右子树
	BSTreeNode<K, V>* _parent;  //父亲
	pair<K, V> _kv;       //存放节点值的
	string _col;    //颜色（通过这个可以直到左右子树存在情况）

	//构造函数
	BSTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _col("RED")     //默认颜色为红色
	{}
};

红黑树的节点结构与二叉搜索树和AVL树差别不大，最大的差别就是加入了一个新的存储点——颜色

四、红黑树的操作

红黑树的基本操作包括插入、删除和查找。以下是这些操作的简要说明：

插入：

将新节点插入到树中，初始时将其标记为红色。

可能会破坏红黑树的性质，需要通过旋转和重新着色来恢复性质。

删除：

删除节点后，可能会破坏红黑树的性质。

需要进行调整，包括旋转和重新着色，以恢复红黑树的性质。

查找：

查找操作与普通的二叉搜索树相同，通过比较节点值来决定向左或向右子树查找。

在这几个操作中，插入是红黑树的关键，因为这是构造红黑树的关键，怎样插入才能保证红黑树的节点颜色、路径长度符合规定，下面我们就来重点讲解一下红黑树的节点插入操作：

首先我们要先清楚一点，红黑树也是二叉搜索树，所以它肯定是符合二叉搜索树的性质的——左边子树值小于根，右边子树值大于根

问题的关键是如何保证插入后结构的颜色符合规定，要做到这一点，我们首先就先要摸清插入节点会遇到的所有情况，然后我们再分析如何解决这些情况：

（强调一下：一定要把前面AVL树中讲的左右旋先弄明白）

假设：cur表示当前节点，p表示父节点，g表示祖父节点，u为叔叔节点

情况一：cur为红，p为黑

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

解决方法：把p、u变成黑，g变为红，然后让g变为cur继续向上处理

情况三：cur为红，p为红，g为黑，u不存在

解决方法：把p变为黑，g变为红，然后进行左旋/右旋

情况四：cur为红，p为红，g为黑，u存在且为黑

解决方法：把p变为黑，g变为红，同时右旋/左旋

特殊情况：如果当cur的插入位置形似AVL树中的RL型或LR型时，要先进行旋转转换成上面几种情况

五、红黑树的实现代码

RBTree.h

//红黑树
#include<iostream>
using namespace std;

template<class K, class V>
struct BSTreeNode
{
	BSTreeNode<K, V>* _left;    //左子树
	BSTreeNode<K, V>* _right;   //右子树
	BSTreeNode<K, V>* _parent;  //父亲
	pair<K, V> _kv;       //存放节点值的
	string _col;    //颜色（通过这个可以直到左右子树存在情况）

	//构造函数
	BSTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _col("RED")     //默认颜色为红色
	{}
};

template<class K, class V>
class BSTree
{
	typedef BSTreeNode<K, V> Node;
public:
	bool Insert(const pair<K, 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);
		cur->_col = "RED";          //插入节点颜色为红色
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}


		//按搜索二叉树规则插入到指定位置后，再检验一下是否符合红黑树的规则进行相关调整
		while (parent && parent->_col == "RED")    //当父节点存在且父节点为红时，进行相关调整
		{
			Node* grandfather = parent->_parent;
			if(parent==grandfather->_left)       //p为g的左孩子时
			{
				//     g
				//   p       
				Node* uncle = grandfather->_right;
				if (uncle && uncle->_col == "RED")    //u存在且为红
				{
					//       g
					//    p      u
					// cur
					parent->_col = uncle->_col = "BLACK";
					grandfather->_col = "RED";

					//继续往上更新
					cur = grandfather;
					parent = cur->_parent;
				}
				else                               //u不存在/u存在且为黑
				{
					//       g
					//     p
					//  cur
					if (cur == parent->_left)
					{
						RotateR(grandfather);
						grandfather->_col = "RED";
						parent->_col = "BLACK";
					}
					else
					{
						//LR型
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = "BLACK";
						grandfather->_col = "RED";
					}
					break;
				}
			}
			else                      //p为g的右孩子时，与上面的相反即可
			{
				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)
					{
						//       g
						//     u    p
						//            c
						RotateL(grandfather);
						grandfather->_col = "RED";
						parent->_col = "BLACK";
					}
					else
					{
						//       g
						//     u   p
						//        c
						//RL型
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = "BLACK";
						grandfather->_col = "RED";
					}
					break;
				}
			}
		}
		_root->_col = "Black";
		return true;
	}

	//进行旋转调整（旋转操作与AVL树中的完全一样，不明白的可以看我之前的文章）
	void RotateL(Node* parent)   //左单旋
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		Node* parentParent = parent->_parent;

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

		if (_root == parent)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (parentParent->_left == parent)
			{
				parentParent->_left = subR;
			}
			else
			{
				parentParent->_right = subR;
			}
			subR->_parent = parentParent;
		}
		parent->_parent = subR;
	}
	void RotateR(Node* parent)   //右单旋
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		Node* parentParent = parent->_parent;

		parent->_left = subLR;
		subL->_right = parent;

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

	//中序打印
	void Inorder()
	{
		_Inorder(_root);
		cout << endl;
	}
	void _Inorder(Node* root)
	{
		if (root == nullptr)
			return;
		_Inorder(root->_left);
		cout << root->_kv.first << " ";
		_Inorder(root->_right);
	}

	//检查是否为BS树（检查两点）
	//一：是否有连续的红节点
	//二：各个路径上的黑色节点个数是否相等
	bool Check(Node* root,int blacknum,const int refVal)
	{
		if (root == nullptr)
		{
			if (blacknum != refVal)
			{
				cout << "存在黑色节点个数不相等的路径" << endl;
				return false;
			}
			return true;
		}
		if (root->_col == "RED"&&root->_parent->_col=="RED")
		{
			cout << "有连续的红色节点" << endl;
			return false;
		}
		if (root->_col == "BLACK")
			++blacknum;
		return Check(root->_left, blacknum, refVal)       //红黑树的左右子树也是红黑树
			&& Check(root->_right, blacknum, refVal);     //所以要用递归对左右子树也进行判断
	}
	bool IsBalance()
	{
		if (_root == nullptr)
			return true;
		if (_root->_col == "RED")
			return false;

		int refVal = 0;      //参考值
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == "BLACK")
			{
				++refVal;
			}
			cur = cur->_left;
		}
		int blacknum = 0;    //根节点到当前节点黑色节点数量
		return Check(_root, blacknum,refVal);
	}

private:
	Node* _root = nullptr;
};

RBTree.c

//红黑树
int main()
{
	int a[] = { 4,2,6,1,3,5,15,7,16,14 };   
	//int a[] = { 790,760,969,270,31,424,377,24,702 };
	BSTree<int, int> t;
	for (auto e : a)
	{
		t.Insert(make_pair(e, e));
	}
	t.Inorder();
	cout << "是否是红黑树（1/0）："<<t.IsBalance() << endl;
	return 0;
}

运行结果：

六、总结

以上就是红黑树的全部内容，红黑树因为其自平衡的特性，及通过节点颜色来操作其树形结构的特点，极大的提高了数据存储及处理的效率，需要我们好好掌握

感谢各位大佬观看，创作不易，还请各位大佬一键三连！！！

原文地址:https://blog.csdn.net/2301_80220607/article/details/140610404 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1815353111250866176.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部