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

红黑树

article 2024/11/15 15:57:57

  

目录

  红黑树

红黑树的概念

红黑树的性质

红黑树节点的定义

插入的代码实现

情况一

情况二

uncle不存在

uncle存在且为黑单旋

情况三

uncle存在且为黑的双旋情况

情况二和情况三的总代码 

以上是父亲在爷爷左边的情况,右边的情况也类似

左旋代码

右旋代码

红黑树的验证

总代码

红黑树

红黑树的概念

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

红黑树的性质

(路径是从根到空节点,上图是11个节点)                 不是红黑树

(最长路径：一黑一红相间的路径  最短：全黑路径)

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

2. 根节点是黑色的 

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

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

5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

红黑树节点的定义

//枚举
//节点颜色
enum Colour
{
	RED,
	BLACK
};
//红黑树节点的定义
template<class K,class  V>
struct RBTreeNode
{
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _left;
	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)
	{}
};

插入的代码实现

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

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

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

情况一

cur为红，p为红，g为黑，u存在且为红

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

举个例子：

 

//第一种情况父亲在爷爷的左边
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不存在/u存在且为黑

p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反，

p为g的右孩子，cur为p的右孩子，则进行左单旋转

p、g变色--p变黑，g变红

举个例子

uncle不存在

	//uncle不存在，且插入的在父亲的左边
	if (cur == parent->_left)
	{
		//     g
		//   p
		// c
		//右旋
		RotateR(grandfather);
		//变色
		parent->_col = BLACK;
		grandfather->_col = RED;
	}
	//cur在父亲右边时，需要双旋
	else
	{
		//     g
		//   p
		//		c
		RotateL(parent);
		RotateR(grandfather);

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

还有可能父亲在爷爷的右边

uncle存在且为黑单旋

(变色后，parent不能直接变黑，因为变黑后每个路径的黑节点不同了)

图上情况，插入后先变色，uncle为红色，然后再向上处理，发现uncle为黑色就需要旋转了，旋转后就不用调整了

情况三

uncle存在且为黑的双旋情况

cur为红，p为红，g为黑，u不存在/u存在且为黑

p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；相反，

p为g的右孩子，cur为p的左孩子，则针对p做右单旋转

则转换成了情况2

//这种情况也是uncle为黑时，且需要旋转的，上面的是单旋的情况，这个是双旋的情况

情况二和情况三的总代码 

else // u不存在 或 存在且为黑
{
	//uncle不存在，且插入的在父亲的左边
	if (cur == parent->_left)
	{
		//     g
		//   p
		// c
		//右旋
		RotateR(grandfather);
		//变色
		parent->_col = BLACK;
		grandfather->_col = RED;
	}
	//cur在父亲右边时，需要双旋
	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;
		}
	}
}

左旋代码

void RotateL(Node* parent)
{

	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)
{

	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;
	}
}

红黑树的验证

红黑树的检测分为两步：

1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)

2. 检测其是否满足红黑树的性质

红黑树的删除

红黑树 - _Never_ - 博客园

红黑树与AVL树的比较

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

总代码

RBTree.h
#pragma once
#include<iostream>
#include<assert.h>
#include<vector>
//枚举
//节点颜色
enum Colour
{
	RED,
	BLACK
};
//红黑树节点的定义
template<class K,class  V>
struct RBTreeNode
{
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _left;
	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;

		//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不存在 或 存在且为黑
				{
					//uncle不存在，且插入的在父亲的左边
					if (cur == parent->_left)
					{
						//     g
						//   p
						// c
						//右旋
						RotateR(grandfather);
						//变色
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					//cur在父亲右边时，需要双旋
					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;
};


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

相关文章：

  • ssm114基于SSM框架的网上拍卖系统的设计与实现+vue(论文+源码)_kaic
  • LeetCode题解：5.最长回文子串【Python题解超详细，中心拓展、动态规划、暴力解法】
  • 第 13 章 -Go 语言 接口
  • datastage在升级版本到11.7之后，部分在11.3上正常执行的SP报错SQLSTATE = 22007: 本机错误代码 = -180
  • AUTOSAR_EXP_ARAComAPI的7章笔记（3）
  • 当你想要conda安装遇到UnavailableInvalidChannel: HTTP 404 NOT FOUND for channel的问题
  • 【日常记录-Git】如何为post-checkout脚本传递参数
  • 【SQL】sql常用命令
  • uniapp在app模式下组件传值
  • 【go从零单排】Ticker
  • Python自动化操作JSON文件详解
  • 在Ubuntu 24.04 LTS上安装飞桨PaddleX
  • uniapp隐藏自带的tabBar
  • 【刷题19】队列+bfs专题
  • 生成自签名证书并配置 HTTPS 使用自签名证书
  • uni-app快速入门（四）--maninfest.json及pages.json配置
  • CSS新特性
  • Ai编程从零开始全栈开发一个后台管理系统之用户登录、权限控制、用户管理-前端部分（十二）
  • nacos配置中心入门
  • 【达梦数据库】参数优化脚本主要改什么
  • spark.default.parallelism 在什么时候起作用，与spark.sql.shuffle.partitions有什么异同点？
  • LaTeX中浮动体（图片、表格）的位置及上下间距设置
  • 使用命令强制给ESXI上的硬盘分区
  • Grafana Username password invalid
  • JavaScript的展开运算符在React中的应用
  • 游戏引擎学习第11天