【C++、数据结构】手撕红黑树

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6

文章目录

📖 前言

本章我们将来介绍一下传说中的 “红黑树”

  • 在次之前我们学习了AVL树AVL树是一棵二叉搜索树通过平衡因子和旋转来保持整棵树的左右平衡。

同样红黑树也是一棵 “二叉搜索树”

  • AVL树相比只是规则不同在实际的学习生活中用到的更多接下来搬好小板凳准备开讲啦~~~ 🙋 🙋 🙋 🙋 🙋

前情回顾AVL树复习 👉 传送门

1. 红黑树的概念⚡

概念

红黑树是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或Black所以叫红黑树。

通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出俩倍因而是接近平衡的。
在这里插入图片描述

🌀 1.2 红黑树的特性

红黑树一共有五大特性

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

思考问题

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

  • 最短 全黑
  • 最长 一黑一红间隔

红黑树是怎样实现 最长路径 <= 最短路径的两倍 呢

  • 根据性质3可以知道红黑树没有连续的红结点
  • 根据性质4可以知道红黑树每条路径上的黑结点个数相同
    在这里插入图片描述

最短路径就是全是黑结点的情况最长路径是一黑一红结点间隔排列的情况。

🌀 1.3 与AVL树的相比

红黑树

  • 红黑树也是二叉搜索树只是换了一种思想
  • 间接控制了高度在每个结点上增加了一个颜色红色和黑色
  • 最长的路径不超过最短路径的2倍

AVL树

  • AVL树是严格控制平衡付出更多的代价去旋转
  • 红黑树则是放松了规则不用很严格的平衡近似平衡最长路径不超过最短路径的2倍

单方面从查找来说

AVL树查找的效率会更高但是代价是AVL树插入时旋转了很多很多次才达到的平衡但是CPU足够的快20次和40次差别不大。

综合来看

红黑树跟胜一筹在保证查找效率底线的同时插入时旋转次数更少。

2. 结点的定义🌟

⭐2.1 Key模型 和 Key_Value模型的引入

🏁2.1.1 K模型

K模型K模型即只有key作为关键码结构中只需要存储Key即可关键码即为需要搜索到的值。

比如给一个单词word判断该单词是否拼写正确具体方式如下

  • 以词库中所有单词集合中的每个单词作为key构建一棵二叉搜索树
  • 在二叉搜索树中检索该单词是否存在存在则拼写正确不存在则拼写错误

🏁2.1.2 KV模型

KV模型每一个关键码key都有与之对应的值Value即<Key, Value>的键值对。该种方式在现实生活中非常常见。

比如英汉词典就是英文与中文的对应关系:

  • 通过英文可以快速找到与其对应的中文英文单词与其对应的中文<word, chinese>就构成一种键值对
  • 再比如统计单词次数统计成功后给定单词就可快速找到其出现的次数单词与其出现次数就是<word, count>就构成一种键值对

⭐2.2 定义结点的代码

我们还是实现的三叉链颜色我们通过枚举类型来实现

enum Colour
{
	RED,
	BLACK,
};

定义的节点如下

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

	Colour _col;

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

这里结点一开始给红色的原因我们下文讲解。

3. 结点的插入重点🔥

💥3.1 新增结点颜色的选择

为什么新增的结点要是红色的呢?

这里就要来解释一下为什么构造新的结点的时候为啥默认颜色要给红色的。

  • 我们这里如果新增的是黑结点的话那么一定违反性质4维护这棵树的时候其他支路的黑结点数量都要跟着改动相当麻烦~
  • 但是如果是新增的结点是红结点的话那么如果被链接的那个结点是红色则违反性质3如果被链接的那个结点是黑色的话则不违反性质3
  • 综上所述新增Black结点一定违反性质4新增Red结点不一定违反性质3

在这里插入图片描述

💥3.2具体插入流程

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

这里用到的思路和AVL树用到的思路大致相同都是不断地向上更新。

插入几大流程

  1. 按照搜索二叉树的查找方法找到要插入的位置
  2. 将新增结点插入到待插入位置
  3. 如果需要调整则调整红黑树

其中需不需要调整主要是看叔叔颜色的情况。

模型讲解
在这里插入图片描述
和AVL树一样三角形也是代表的是子树。

🏁情况一叔叔存在且为红

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

解决方式:将pu改为黑g改为红然后把g当成cur继续向上调整。

首先我们知道红黑树调整主要看叔叔第一步我们将父亲变成黑色为了维护性质4我们也要将叔叔的颜色变成黑色同时也要将祖父结点的颜色变成红色因为我们此时处理的不一定是整棵树有可能是某个子树如果此时不是子树就需要将根节点变成黑色。

在这里插入图片描述
调整的部分可能是一整棵树也可能是某一棵子树

  • 如果g是根节点调整完成后需要将g改为黑色
  • 如果g是子树g一定有双亲且g的双亲如果是红色需要继续向上调整

在这里插入图片描述
情况一不关心左右关系只变色、不旋转p、u是g的左和右是无所谓的cur是p的左或者右也是一样的。

情况一的调整变化是为了变到其他的情况。

🏁情况二叔叔不存在 or 叔叔存在且为黑 — 单旋处理

情况二可能就是从情况一调整变化得到的情况。

具体情况 1

当叔叔不存在时
在这里插入图片描述
如图所示如果单纯的按照情况一方式的调整的话还是 违背了性质4此时我们就想到了旋转的操作方式。
在这里插入图片描述

  • 此时是左边高了我们对图示树进行右单旋这里的旋转和AVL树中旋转的方式如出一辙可以拿过来直接复用。
  • 同样的道理如果是右边高了我们就可以进行左单旋旋转的方法也和AVL树中的如出一辙也可拿过来直接复用。
具体情况 2

当叔叔存在且为黑时

这种情况一定是由情况一变来的

解释

我们用反证法假设是在插入结点之前就有了情况二的样子

  • 假设是某一个棵树
  • n表示g结点所在支路之前黑结点的个数不包括g
  • m表示u结点所在支路之后黑结点的个数不包括u
    在这里插入图片描述
  • 如图所示很明显子树的根是g
  • g结点所在的左子树的支路黑结点个数为 n + 1
  • g结点所在的右子树的支路黑结点个数为 n + m + 2
  • 显然n + m + 2 > n + 1
  • 所以不可能在插入之前就会出现具体情况2的样子已经违背红黑树的性质4了
  • 综上所述只要有可能是由情况一变来的

此时进行旋转 + 变色就能维护好红黑树的结构。
在这里插入图片描述

🏁情况三叔叔不存在 or 叔叔存在且为黑 — 双旋处理

同样是 叔叔不存在 or 叔叔存在且为黑为啥分为情况二和情况三呢

上述旋转的情况都是单边的情况也就是说cur、p、g在一条线上的情况若是出现了这三者不在一条直线的时候单旋就解决不了问题了。

区别:

  • p是g的左cur是p的左那么是情况二 —— 单旋
  • p是g的左cur是p的右那么是情况三 —— 双旋

此时我们就引入了双旋
在这里插入图片描述

  • 先以p为旋转点再以g为旋转点
  • 先变到情况二的样子
  • 再根据情况二来继续变

此时有个疑问情况二和情况三看样子都违背了红黑树的性质4难道没错吗

再此之前我们推测过当叔叔存在且为黑时一定是由情况一变来的所以cur一开始是黑的这个树并不违反性质子树由情况一变化之后的子树结点的颜色也相应变化了只是没有显示出来而已。

💥3.3 代码实现

前序准备工作
在这里插入图片描述
插入实现的代码

bool Insert(const pair<K, V>& kv)
{
	//1、搜索树的规则插入
	//2、看是否违反平衡规则如果违反就需要处理旋转
	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;
	}
	else
	{
		parent->_left = cur;
	}

	//三叉链的链接 -- 链上父节点
	cur->_parent = parent;

	//...

	//存在连续红色结点
	while (parent && parent->_col == RED)
	{
		//理论而言祖父是一定存在的父亲存在且是红不可能是根根一定是黑的
		Node* grandfather = parent->_parent;
		assert(grandfather);

		if (grandfather->_left == parent)
		{
			Node* uncle = grandfather->_right;
			//情况一叔叔存在且为红
			if (uncle && uncle->_col == RED)
			{
				//父亲和叔叔变成黑色
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;

				//继续往上处理
				cur = grandfather;
				parent = cur->_parent;
			}
			//情况二叔叔不存在 or 叔叔存在且为黑
			else if (uncle == nullptr || uncle->_col == BLACK)
			{
				//单旋
				//	   g
				//	 p
				// c
				if (cur == parent->_left)
				{
					RotateR(grandfather);
					parent->_col = BLACK;
					grandfather->_col = RED;
				}
				//双旋
				//    g
				//  p
				//    c
				else if (cur == parent->_right)
				{
					RotateL(parent);
					RotateR(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}

				break;
			}
		}
		//无论父亲和叔叔是左是右都是一样的
		//grandfather->_right == parent;
		else if(grandfather->_right == parent)
		{
			Node* uncle = grandfather->_left;
			//情况一
			if (uncle && uncle->_col == RED)
			{
				//祖父和叔叔变成黑色
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;

				//继续往上处理
				cur = grandfather;
				parent = cur->_parent;
			}
			//情况二叔叔不存在 or 叔叔存在且为黑
			else if (uncle == nullptr || uncle->_col == BLACK)
			{
				//单旋
				// g
				//   p
				//     c
				if (cur == parent->_right)
				{
					RotateL(grandfather);
					parent->_col = BLACK;
					grandfather->_col = RED;
				}
				//双旋
				//  g
				//    p
				//  c
				else if (cur == parent->_left)
				{
					RotateR(parent);
					RotateL(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}

				break;
			}
		}
	}

	//父亲为空就出循环将根节点设置成黑色
	_root->_col = BLACK;

	return true;
}

旋转实现的代码

//左旋
void RotateL(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 (parent == _root)
	{
		_root = subR;
		_root->_parent = nullptr;
	}
	else
	{
		if (parent == ppNode->_left)
		{
			ppNode->_left = subR;
		}
		else
		{
			ppNode->_right = subR;
		}

		subR->_parent = ppNode;
	}
}

//右旋
void RotateR(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 (parent == _root)
	{
		_root = subL;
		_root->_parent = nullptr;
	}
	else
	{
		if (ppNode->_left == parent)
		{
			ppNode->_left = subL;
		}
		else
		{
			ppNode->_right = subL;
		}
		subL->_parent = ppNode;
	}

}

4. 验证红黑树⭕

我们通过一段代码来验证一下红黑树

首先我们先将整个树遍历一遍来观察一下是否符合搜索二叉树

中序遍历红黑树

  • 同时我们再提供几个函数用来求红黑树的高度和
//中序遍历
void InOrder()
{
	_InOrder(_root);
	cout << endl;
}

void _InOrder(Node* root)
{
	if (root == nullptr)
		return;

	_InOrder(root->_left);
	cout << root->_kv.first << " ";
	_InOrder(root->_right);
}

//求红黑树的最长路径
int _maxHeight(Node* root)
{
	if (root == nullptr)
		return 0;

	int lh = _maxHeight(root->_left);
	int rh = _maxHeight(root->_right);

	return lh > rh ? lh + 1 : rh + 1;
}

//求红黑树的最短路径
int _minHeight(Node* root)
{
	if (root == nullptr)
		return 0;

	int lh = _minHeight(root->_left);
	int rh = _minHeight(root->_right);

	return lh < rh ? lh + 1 : rh + 1;
}

void Height()
{
	cout << "最长路径:" << _maxHeight(_root) << endl;
	cout << "最短路径:" << _minHeight(_root) << endl;
}

//层序遍历
vector<vector<int>> levelOrder() 
{
	vector<vector<int>> vv;
	if (_root == nullptr)
		return vv;

	queue<Node*> q;
	int levelSize = 1;
	q.push(_root);

	while (!q.empty())
	{
		// levelSize控制一层一层出
		vector<int> levelV;
		while (levelSize--)
		{
			Node* front = q.front();
			q.pop();
			levelV.push_back(front->_kv.first);
			if (front->_left)
				q.push(front->_left);

			if (front->_right)
				q.push(front->_right);
		}
		vv.push_back(levelV);
		for (auto e : levelV)
		{
			cout << e << " ";
		}
		cout << endl;

		// 上一层出完下一层就都进队列
		levelSize = q.size();
	}

	return vv;
}

测试1

void TestRBTree1()
{
	//int a[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
	int a[] = { 30, 29, 28, 27, 26, 25, 24, 11, 8, 7, 6, 5, 4, 3, 2, 1 };
	RBTree<int, int> t;
	for (auto e : a)
	{
		t.Insert(make_pair(e, e));
	}
	t.levelOrder();
	t.InOrder();
	t.Height();
}

测试结果
在这里插入图片描述
接下来我们通过红黑树的五大性质进行验证

//判断是否符合红黑树
bool IsBalanceTree()
{
	//检查红黑树几条规则

	Node* pRoot = _root;
	//空树也是红黑树
	if (nullptr == pRoot)
		return true;

	//检测根结点是否满足情况
	if (BLACK != pRoot->_col)
	{
		cout << "违反红黑树性质二根节点必须为黑色" << endl;
		return false;
	}

	//获取任意一条路径中黑色节点的个数 -- 作为比较基准值
	size_t blackCount = 0;
	Node* pCur = pRoot;
	while (pCur)
	{
		if (BLACK == pCur->_col)
			blackCount++;

		pCur = pCur->_left;
	}

	//检测是否满足红黑树的性质k用来记录路径中黑色节点的个数
	size_t k = 0;
	return _IsValidRBTree(pRoot, k, blackCount);
}

//上一个函数的返回值是调用这个函数
bool _IsValidRBTree(Node* pRoot, size_t k, const size_t blackCount)
{
	//走到nullptr之后判断k和black是否相等
	if (nullptr == pRoot)
	{
		if (k != blackCount)
		{
			cout << "违反性质四每条路径中黑色节点的个数必须相同" << endl;
			return false;
		}
		return true;
	}

	//统计黑色节点的个数
	if (BLACK == pRoot->_col)
		k++;

	//检测当前节点与其双亲是否都为红色
	if (RED == pRoot->_col && pRoot->_parent && pRoot->_parent->_col == RED)
	{
		cout << "违反性质三存在连在一起的红色节点" << endl;
		return false;
	}

	return _IsValidRBTree(pRoot->_left, k, blackCount) &&
		_IsValidRBTree(pRoot->_right, k, blackCount);
}

通过递归的方式将每条支路都走了一遍和基准值比较并且将红黑树的性质全都验证了。

测试2

void TestRBTree2()
{
	const size_t N = 1024 * 1024 * 10;
	vector<int> v;
	v.reserve(N);
	srand(time(0));
	for (size_t i = 0; i < N; ++i)
	{
		//v.push_back(rand());
		v.push_back(i);
	}

	RBTree<int, int> t;
	for (auto e : v)
	{
		t.Insert(make_pair(e, e));
	}

	//t.levelOrder();
	//cout << endl;
	cout << "是否为红黑树" << t.IsBalanceTree() << endl;
	t.Height();

	//t.InOrder();
}

测试结果
在这里插入图片描述

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6
标签: c++
返回列表

上一篇：Redis学习笔记

下一篇：轻松实现一个Python+Selenium的自动化测试框架_python+selenium自动化框架

“【C++、数据结构】手撕红黑树” 的相关文章

FreeRTOS上线中文版网页，C++获得 2022 年度编程语言1年前 (2023-02-02)
C/C++编程题之句子逆序1年前 (2023-02-02)
C/C++编程题之购物清单1年前 (2023-02-02)
带你走入虚函数和多态的世界（c++）1年前 (2023-02-02)
用c/c++代码求解时分秒针重合次数1年前 (2023-02-02)
【C++】非递归实现二叉树的前中后序遍历1年前 (2023-02-02)
基于2D Object Detection的目标几何中心三维位置估计（C++）1年前 (2023-02-02)
C/C++之（五）洛谷刷题基础题 --- 新年好1年前 (2023-02-02)
C++之多态1年前 (2023-02-02)
C++设计模式（2）——工厂方法模式1年前 (2023-02-02)

阿里云国际版