当前位置： 首页 > article >正文

＜C++＞ 红黑树

article 2024/11/20 13:35:20

目录

1. 红黑树的概念

2. 红黑树的性质

3. 红黑树节点的定义

4. 红黑树的插入操作

5. 红黑树的验证

6. 红黑树与AVL树的比较

7. 红黑树的删除

        红黑树比AVL树更优一些，因为AVL要求太严格，左右高度差不超过1，而红黑树采用颜色来控制，只要求最长路径不超过最短路径的2倍，属于近似平衡

1. 红黑树的概念

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

        在高度方面大致是2logN，比AVL高2倍，但是logN效率很高，对于10亿的数据量，也仅仅是30高度和60高度，这种常数级的效率几乎完全相同！

        所以，红黑树的优点就是高度没有AVL要求那么严格，AVL由于高度的严格要求，它的插入和删除需要大量的旋转，而红黑树就少许多，这就是红黑树的优势 

2. 红黑树的性质

  1. 每个结点不是红色就是黑色

  2. 根节点是黑色的 

  3. 如果一个节点是红色的，则它的两个孩子结点必须是黑色的，即任何路径都没有连续的红色节点

  4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点 ，即每条路径上黑色节点的数量相等

  5. 每个叶子结点（NIL节点）都是黑色的（此处的叶子结点指的是空结点）

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

  1. 如果有一个路径它的节点数最少，那么这个最短路径一定是全黑的！红色的出现会导致节点数增加
  2. 对于最长路径一定是红黑相间的！因为每一条路径的黑色节点数量相同，并且红色的孩子一定是黑色，所以就可以在黑色节点之间插入红色，来增加节点数

3. 红黑树节点的定义

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)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_kv(kv)
		,_col(RED)
	{}
};

template<class K, class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
    
private:
    Node* root = nullptr;
}

思考：在节点的定义中，为什么要将节点的默认颜色给成红色的？

        新增节点要为红色，因为红色只会影响当前路径，但是如果是黑色，那么会影响所有路径，因为每个路径黑节点数量要相同。所以我们挑一个影响代价最小的方案，即新增节点为红色，此时只需要修改当前路径即可保证结构正确

4. 红黑树的插入操作

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

        因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，要开始调色，此时需要对红黑树分情况来讨论：

约定：cur为当前节点，p为父节点（parent），g为祖父节点（grandfather），u为叔叔节点（uncle）

情况一: cur为红，p为红，g为黑，u存在且为红（uncle存在且为红：变色，继续向上更新）

解决方式：将 p,u 改为黑， g 改为红，然后把 g 当成 cur ，继续向上调整

 

	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;
		}
		else
		{
			parent->_left = cur;
		}

		cur->_parent = parent;

		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				// u存在且为红
				if (uncle && uncle->_col == RED)
				{
					// 变色
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					// 继续向上处理
					cur = grandfather;
					parent = cur->_parent;
				}
         }
    }

情况二: cur为红，p为红，g为黑，u不存在（uncle不存在：旋转+变色）

 

旋转策略：

  • p为g的左孩子，cur为p的左孩子，则进行右单旋转
  • p为g的右孩子，cur为p的右孩子，则进行左单旋转
  • p、g变色：p变黑，g变红

 

else // u不存在 或 存在且为黑
{
	if (cur == parent->_left)
	{
		//     g
		//   p
		// c
		RotateR(grandfather);
		parent->_col = BLACK;
		grandfather->_col = RED;
	}
	else
	{
		//     g
		//   p
		//		c
		RotateL(parent);
		RotateR(grandfather);

		cur->_col = BLACK;
		grandfather->_col = RED;
	}

	break;
}

情况三: cur为红，p为红，g为黑，u为黑 （uncle存在且为黑：旋转+变色）（旋转就是AVL中单旋、双旋操作）

 

        uncle是黑的，表明cur一定不是新增节点，因为每条路径一定的黑节点数量一定相同，所以此情况一定是从下往上更新上来的） 

旋转+变色策略：

  • p为g的左孩子，cur为p的右孩子，则针对p做左单旋转，再对g做右单旋
  • p为g的右孩子，cur为p的左孩子，则针对p做右单旋转，再对g做左单旋
  • p为g的左孩子，cur为p的左孩子，则进行右单旋转
  • p为g的右孩子，cur为p的右孩子，则进行左单旋转（变为情况二）
  • 根据单旋还是双旋进行变色。单旋：p、g变色，p变黑，g变红；双旋：cur变黑，g变红

情况二、三都不需要往上继续更新，因为这个结构更新后的根是黑色，不管上面存不存在、或者存在，都不会影响

 

 

小结：

  • 新增节点应为红色
  • 出现连续的红色时，根据uncle分三种情况
  • 如果不是旋转的情况，循环往上继续更新（如果继续出现连续的红才会进入循环）；如果是旋转的情况，不用继续往上更新
#pragma once
#pragma once
#include<iostream>
using namespace std;

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)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _col(RED)
	{}
};

template<class K, class V>
class RBTree
{
	typedef RBTreeNode<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;
		}
		else
		{
			parent->_left = cur;
		}

		cur->_parent = parent;

		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				// u存在且为红
				if (uncle && uncle->_col == RED)
				{
					// 变色
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					// 继续向上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				else // u不存在 或 存在且为黑
				{
					if (cur == parent->_left)
					{
						//     g
						//   p
						// c
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						//     g
						//   p
						//		c
						RotateL(parent);
						RotateR(grandfather);

						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					break;
				}
			}
			else // parent == grandfather->_right
			{
				Node* uncle = grandfather->_left;
				// u存在且为红
				if (uncle && uncle->_col == RED)
				{
					// 变色
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					// 继续向上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_right)
					{
						// g
						//	  p
						//       c
						RotateL(grandfather);
						grandfather->_col = RED;
						parent->_col = BLACK;
					}
					else
					{
						// g
						//	  p
						// c
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					break;
				}
			}
		}

		_root->_col = BLACK;

		return true;
	}

	void RotateL(Node* parent)
	{
		++_rotateCount;

		Node* cur = parent->_right;
		Node* curleft = cur->_left;

		parent->_right = curleft;
		if (curleft)
		{
			curleft->_parent = parent;
		}

		cur->_left = parent;

		Node* ppnode = parent->_parent;

		parent->_parent = cur;


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

			}

			cur->_parent = ppnode;
		}
	}


	void RotateR(Node* parent)
	{
		++_rotateCount;

		Node* cur = parent->_left;
		Node* curright = cur->_right;

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

		Node* ppnode = parent->_parent;
		cur->_right = parent;
		parent->_parent = cur;

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

			cur->_parent = ppnode;
		}
	}

	bool CheckColour(Node* root, int blacknum, int benchmark)
	{
		if (root == nullptr)
		{
			if (blacknum != benchmark)
				return false;

			return true;
		}

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

		if (root->_col == RED && root->_parent && root->_parent->_col == RED)
		{
			cout << root->_kv.first << "出现连续红色节点" << endl;
			return false;
		}

		return CheckColour(root->_left, blacknum, benchmark)
			&& CheckColour(root->_right, blacknum, benchmark);
	}

	bool IsBalance()
	{
		return IsBalance(_root);
	}

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

		if (root->_col != BLACK)
		{
			return false;
		}

		// 基准值
		int benchmark = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
				++benchmark;

			cur = cur->_left;
		}

		return CheckColour(root, 0, benchmark);
	}

	int Height()
	{
		return Height(_root);
	}

	int Height(Node* root)
	{
		if (root == nullptr)
			return 0;

		int leftHeight = Height(root->_left);
		int rightHeight = Height(root->_right);

		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	}

private:
	Node* _root = nullptr;

public:
	int _rotateCount = 0;
};

 

5. 红黑树的验证

检验：

  • 根节点是黑色
  • 不能有连续的红节点（以子判父更方便，如果从父亲视角看，要分问情况）
  • 每条路径的黑节点数量相等（先算出一个基准值，例如最左路径上黑节点的数量）
	bool CheckColour(Node* root, int blacknum, int benchmark)
	{
		if (root == nullptr)
		{
			if (blacknum != benchmark)
				return false;

			return true;
		}

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

		if (root->_col == RED && root->_parent && root->_parent->_col == RED)
		{
			cout << root->_kv.first << "出现连续红色节点" << endl;
			return false;
		}

		return CheckColour(root->_left, blacknum, benchmark)
			&& CheckColour(root->_right, blacknum, benchmark);
	}

	bool IsBalance()
	{
		return IsBalance(_root);
	}

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

		if (root->_col != BLACK)
		{
			return false;
		}

		// 基准值
		int benchmark = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
				++benchmark;

			cur = cur->_left;
		}

		return CheckColour(root, 0, benchmark);
	}

	int Height()
	{
		return Height(_root);
	}

	int Height(Node* root)
	{
		if (root == nullptr)
			return 0;

		int leftHeight = Height(root->_left);
		int rightHeight = Height(root->_right);

		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	}
int main()
{
	const int N = 10000000;
	vector<int> v;
	v.reserve(N);
	srand(time(0));

	for (size_t i = 0; i < N; i++)
	{
		v.push_back(i);
	}

	RBTree<int, int> rbt;
	for (auto e : v)
	{
		rbt.Insert(make_pair(e, e));
		//cout << "Insert:" << e << "->" << t.IsBalance() << endl;
	}

    return 0;
}

6. 红黑树与AVL树的比较

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

int main()
{
	const int N = 100000;
	vector<int> v;
	v.reserve(N);
	srand(time(0));

	for (size_t i = 0; i < N; i++)
	{
		v.push_back(rand());
	}

	RBTree<int, int> rbt;
	for (auto e : v)
	{
		rbt.Insert(make_pair(e, e));
		//cout << "Insert:" << e << "->" << t.IsBalance() << endl;
	}
	cout << rbt.IsBalance() << endl;
	cout << rbt.Height() << endl;
	cout << rbt._rotateCount << endl;


	AVLTree<int, int> avlt;
	for (auto e : v)
	{
		avlt.Insert(make_pair(e, e));
		//cout << "Insert:" << e << "->" << t.IsBalance() << endl;
	}
	cout << avlt.IsBalance() << endl;
	cout << avlt.Height() << endl;
	cout << avlt._rotateCount << endl;


	return 0;
}

红黑树的应用

1. C++ STL库 -- map/set、mutil_map/mutil_set

2. Java 库

3. linux内核

4. 其他一些库

7. 红黑树的删除 

红黑树 - _Never_ - 博客园 (cnblogs.com)


http://www.kler.cn/a/287264.html

相关文章：

  • SRP 实现 Cook-Torrance BRDF
  • 1Panel 推送 SSL 证书到阿里云、腾讯云
  • 第二十一周学习周报
  • 笔记｜M芯片MAC (arm64) docker上使用 export / import / commit 构建amd64镜像
  • 【HarmonyOS】鸿蒙系统在租房项目中的项目实战（二）
  • PHP代码审计 --MVC模型开发框架rce示例
  • golang make 函数的三个参数分别有什么作用
  • 峟思大坝安全监测系统：科技筑牢工程稳定的基石
  • TCP ISO/OSI模型
  • 开启ROS 2中的geometry坐标模拟展示
  • SQLi-LABS靶场56-60通过攻略
  • [Python]之深拷贝与浅拷贝
  • Flask之Hello world 详解
  • 【补-办公室】拟批语的区别
  • 重构贪心算法（二）
  • 12大常用自动化测试工具，请记得转发收藏！
  • Leetcode 3277. Maximum XOR Score Subarray Queries
  • PostgreSQL LIMIT 子句的使用与优化
  • Jenkins版本升级
  • 米家“智能中枢网关”和“智能多模网关”有什么区别？
  • 快速回顾-HTML5
  • 前端宝典二十一：前端异步编程规范手写Promise、async、await
  • 01.项目初始化
  • 解决yum不能正常使用，报错： No module named yum，如何安装python2和python3并行版本,搭建自动化环境
  • 【Python机器学习】NLP词中的数学——向量化
  • 驭势科技研究成果入选学术顶会IROS 2024