C++学习笔记:红黑树

红黑树

  • 什么是红黑树
  • 红黑树的规则
  • 红黑树节点的定义
  • 红黑树的插入
    • 空树插入
    • 非空插入条件判断
    • 新插入的节点 cur 不为 root 且 parent->_col 为红就需要调整
    • 父节点为左 grandf->left == parent
      • 当uncle节点为红色时,只需要进行颜色调整,即可
      • 当uncle为空 或 者存在但是为黑
        • parent 为left , cur 为 left 单纯的grandf右旋
          • uncle 为空
          • uncle不为空
        • parent 为left , cur 为 right 先左旋parent再右旋grandf
          • uncle为空
          • uncle不为空
    • 父节点为右 grandf->right == parent
  • 代码实现

什么是红黑树

红黑树是一种特殊的由二叉搜索树为底的数据结构,**之所以被成为红黑树,是因为在每个节点增加一个存储位表示这个节点的颜色,不是黑色就是红色,**因为其特数的规则,红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。并具有更优的算法复杂度.
在这里插入图片描述

红黑树的规则

正是因为有以下规则的限制,红黑树才能是红黑树

  • 每个结点不是红色就是黑色
  • 根节点是黑色的
  • 红色节点的两个孩子结点是黑色的,即不存在两个连续的红色节点
  • 从任一节点到其每个叶子节点的所有简单路径都包含相同数目的黑色节点：这也称为黑色平衡，确保树的高度相对平衡，从而保证了最长路径不超过最短路径的两倍。
  • 叶子节点均为黑色

红黑树节点的定义

在定义节点之前,最好先定义一个枚举类型,用来记录每个节点的颜色
并且因为涉及到旋转调整,因此红黑树和AVL树一样需要记录父亲节点

enum Color
{
	RED,
	BLACK
};

template<class T>
struct RBTreeNode
{
	RBTreeNode* _parent;
	RBTreeNode* _left;
	RBTreeNode* _right;
	T _data;
	Color _col;

	RBTreeNode(const T& data = T(),Color color = RED)
		:_parent(nullptr)
		, _left(nullptr)
		, _right(nullptr)
		, _col(color)
		, _data(data)
	{}

};

红黑树的插入

红黑树的插入和AVL树的插入相似,但不同点是AVL树插入完成后改变的是平衡因子,而红黑树插入后改变的是节点的颜色.仅凭节点的旋转调整和节点颜色的改变就可以使之成为红黑树,不得不说发明红黑树的人真的是个天才!
因为涉及到后续迭代器的实现,因此我这里使用带头的红黑树来举例
在这里插入图片描述

我们将红黑树的插入分成几种情况依次来看

空树插入

当红黑树是空树时则直接插入,并且每次插入完成后将红黑树的根置为黑色,没什么特别的思路,直接上代码

		if (_root == nullptr)
		{
			//根节点必须为黑色
			Node* root = new Node(data, BLACK);
			_root = root;
			_root->_parent = _pHead;
			_pHead->_parent = _root;

		}

非空插入条件判断

新插入的节点为红色,并且按照正常的二叉搜索树的条件去依次插入

			Node* cur = _root;
			//像搜索二叉树一样插入
			while (cur)
			{
				if (cur->_data > data)
				{
					parent = cur;
					cur = cur->_left;
				}
				else if (cur->_data < data)
				{
					parent = cur;
					cur = cur->_right;
				}
				else
				{
					return false;
				}
			}
			//到位置了,创建节点并赋予红色 
			cur = new Node(data, RED);
			//判断是父节点的左还是右并进行链接
			if (data < parent->_data)
			{
				parent->_left = cur;
			}
			else
			{
				parent->_right = cur;
			}
			cur->_parent = parent;

	链接完成后,查看父亲节点是否为红色  
	因为新节点为红色,若父节点也为红就需要进行调整

并且在每次插入完成后需要进行检查,若还是这种情况,则需要继续调整

新插入的节点 cur 不为 root 且 parent->_col 为红就需要调整

因为新插入的节点默认为红色,此时父亲节点也为红就需要进行调整

而红黑树的调整不仅仅只看cur节点和parent节点,还需要查看uncle(叔叔节点)和grandf(爷爷节点)节点及其颜色来进行判断
uncle节点:
在这里插入图片描述
接下来根据条件来进行调整

父节点为左 grandf->left == parent

当uncle节点为红色时,只需要进行颜色调整,即可

在这里插入图片描述
这种情况下这颗子树的黑色节点的高度依然没有发生变化
在进行颜色的调整后继续检查父亲节点

当uncle为空 或 者存在但是为黑

此时就要进行旋转和变色了,因为已经没有办法仅仅只通过变色来使这个子树的黑色节点的高度不发生变化了

在这里插入图片描述

parent 为left , cur 为 left 单纯的grandf右旋
uncle 为空

在这里插入图片描述

uncle不为空

此时当前的这个新插入的节点一定是从子树中调节变色变上来的,因为在有当前节点之前,parent一定有一个黑色节点的子树,否则这颗红黑树不平衡,
在这里插入图片描述

这种情况下这颗子树的黑色节点的高度依然没有发生变化
此时插入完成

parent 为left , cur 为 right 先左旋parent再右旋grandf
uncle为空

在这里插入图片描述

uncle不为空

在这里插入图片描述
在这里插入图片描述

父节点为右 grandf->right == parent

父节点为右时,与父节点为左完全相反,对照查看即可

代码实现

为了方便后续迭代器的实现,我使用了带头的红黑树:
定义头文件 RBTree.h

#pragma once

#include<iostream>
using namespace std;

enum Color
{
	RED,
	BLACK
};

template<class T>
struct RBTreeNode
{
	RBTreeNode* _parent;
	RBTreeNode* _left;
	RBTreeNode* _right;
	T _data;
	Color _col;

	RBTreeNode(const T& data = T(),Color color = RED)
		:_parent(nullptr)
		, _left(nullptr)
		, _right(nullptr)
		, _col(color)
		, _data(data)
	{}

};

template<class T>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	RBTree()
	{
		_pHead = new Node();
		_pHead->_left = _pHead;
		_pHead->_right = _pHead;
	}

	// 在红黑树中插入值为data的节点，插入成功返回true，否则返回false
	// 注意：为了简单起见，本次实现红黑树不存储重复性元素
	bool Insert(const T& data)
	{
		Node*& _root = _pHead->_parent;
		if (_root == nullptr)
		{
			//根节点必须为黑色
			Node* root = new Node(data, BLACK);
			_root = root;
			_root->_parent = _pHead;
			_pHead->_parent = _root;

		}
		else
		{
			Node* parent = nullptr;
			Node* cur = _root;
			//像搜索二叉树一样插入
			while (cur)
			{
				if (cur->_data > data)
				{
					parent = cur;
					cur = cur->_left;
				}
				else if (cur->_data < data)
				{
					parent = cur;
					cur = cur->_right;
				}
				else
				{
					return false;
				}
			}
			//到位置了,创建节点并赋予红色 
			cur = new Node(data, RED);
			//判断是父节点的左还是右并进行链接
			if (data < parent->_data)
			{
				parent->_left = cur;
			}
			else
			{
				parent->_right = cur;
			}
			cur->_parent = parent;

			//链接完成后,查看父亲节点是否为红色  
			//因为新节点为红色,若父节点也为红就需要进行调整
			while (parent != _pHead && parent->_col == RED)
			{
				Node* uncle = nullptr;
				Node* grandf = parent->_parent;
				if (grandf->_left == parent)
				{
					//    g
					//   p    u
					//  c/c
					uncle = grandf->_right;
					//叔叔存在且为红
					if (uncle && uncle->_col == RED)
					{
						//变色
						parent->_col = uncle->_col = BLACK;
						grandf->_col = RED;

						//继续往上更新
						cur = grandf;
						parent = cur->_parent;
					}
					//叔叔为空 或 者存在但是为黑
					else
					{
						//p 为left  cur 为 left  单纯的右旋
						if (cur == parent->_left)
						{
							RotateR(grandf);
							parent->_col = BLACK;
							grandf->_col = RED;
						}
						//p 为left  cur 为 right   先左旋p再右旋grandf
						else
						{
							RotateL(parent);
							RotateR(grandf);
							cur->_col = BLACK;
							grandf->_col = RED;
						}
						break;
					}

				}
				else //grandf->_right == parent
				{
					//    g
					//  u    p
					//      c/c
					uncle = grandf->_left;
					//叔叔存在且为红
					if (uncle && uncle->_col == RED)
					{
						//变色
						parent->_col = uncle->_col = BLACK;
						grandf->_col = RED;

						//继续往上更新
						cur = grandf;
						parent = cur->_parent;
					}
					//叔叔不存在或者 叔叔为黑
					else
					{
						//p 为 right c 为 right 单纯的左旋
						if (cur == parent->_right)
						{
							RotateL(grandf);
							parent->_col = BLACK;
							grandf->_col = RED;
						}
						//p 为 right c 为 left 先右旋parent再左旋grandf
						else
						{
							RotateR(parent);
							RotateL(grandf);
							cur->_col = BLACK;
							grandf->_col = RED;
						}
						break;
					}

				}
			}

		}
		_root->_col = BLACK;
		_pHead->_left = LeftMost();
		_pHead->_right = RightMost();
		return true;

	}

	// 检测红黑树中是否存在值为data的节点，存在返回该节点的地址，否则返回nullptr
	Node* Find(const T& data)
	{
		Node*& _root = _pHead->_parent;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_data > data)
			{
				cur = cur->_left;
			}
			else if (cur->_data < data)
			{
				cur = cur->_right;
			}
			else
			{
				return cur;
			}
		}

		return nullptr;
	}

	// 获取红黑树最左侧节点
	Node* LeftMost()
	{
		if (_pHead->_parent == nullptr)
		{
			return _pHead;
		}
		Node* root = _pHead->_parent;;
		while (root->_left)
		{
			root = root->_left;
		}
		return root;

	}

	// 获取红黑树最右侧节点
	Node* RightMost()
	{
		if (_pHead->_parent == nullptr)
		{
			return _pHead;
		}
		Node* root = _pHead->_parent;;
		while (root->_right)
		{
			root = root->_right;
		}
		return root;
	}

	// 检测红黑树是否为有效的红黑树，注意：其内部主要依靠_IsValidRBTRee函数检测
	bool IsValidRBTRee()
	{
		Node*& _root = _pHead->_parent;
		//空树
		if (_root == nullptr)
		{
			return true;
		}
		else if(_root->_col == BLACK)
		{
			size_t blacknum = 0;
			Node* cur = _root;
			while (cur)
			{
				if (cur->_col == BLACK)
				{
					blacknum++;
				}
				cur = cur->_left;
			}
			size_t k = 0;
			return _IsValidRBTRee(_root, k , blacknum);
		}
		else
		{
			return false;
		}
	}
	void InOrder()
	{
		_InOrder(_pHead->_parent);
		cout << endl;
	}
private:

	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_InOrder(root->_left);
		cout << root->_data << ":";
		if (root->_col == RED)
		{
			cout << "red"<<endl;
		}
		else
		{
			cout << "black" << endl;
		}

		_InOrder(root->_right);
	}

	bool _IsValidRBTRee(Node* root, size_t k, size_t blacknum )
	{
		if (root == nullptr)
		{
			if (k != blacknum)
			{
				cout << "黑色节点平衡" << endl;
				return false;
			}
			return true;
		}

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

		Node* parent = root->_parent;
		if (parent && parent->_col == RED && parent != _pHead && root->_col == RED)
		{
			cout << "有连续的红色节点" << endl;
			return false;
		}

		return _IsValidRBTRee(root->_left, k, blacknum)
			&& _IsValidRBTRee(root->_right, k, blacknum);
			
	}

	// 左单旋
	void RotateL(Node* parent)
	{
		Node*& _root = _pHead->_parent;
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		subR->_left = parent;

		Node* pparent = parent->_parent;

		parent->_parent = subR;
		if (subRL)
		{
			subRL->_parent = parent;
		}

		if (parent == _root)
		{
			_root = subR;
			subR->_parent = _pHead;
		}
		else
		{
			if (pparent->_left == parent)
			{
				pparent->_left = subR;
			}
			else
			{
				pparent->_right = subR;
			}
			subR->_parent = pparent;
		}

	}
	// 右单旋
	void RotateR(Node* parent)
	{
		Node*& _root = _pHead->_parent;
		Node* pparent = parent->_parent;
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

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

		if (subLR)
		{
			subLR->_parent = parent;
		}

		if (_root == parent)
		{
			_root = subL;
			subL->_parent = _pHead;
		}
		else
		{
			if (pparent->_left == parent)
			{
				pparent->_left = subL;
			}
			else
			{
				pparent->_right = subL;
			}
			subL->_parent = pparent;
		}

	}



	// 为了操作树简单起见：获取根节点
	Node* GetRoot()
	{
		return  _pHead->_parent;
	}


private:
	Node* _pHead;
};

小小测试以下

#define _CRT_SECURE_NO_WARNINGS 1

#include"RBTree.h"



void test1()
{

	int arr[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	RBTree<int> rb;
	for (auto& e : arr)
	{
		rb.Insert(e);
	}

	rb.InOrder();
	if (rb.Find(11) != nullptr)
	{
		cout << "get find" << endl;
	}

	if (rb.IsValidRBTRee())
	{
		cout << "is RBTree" << endl;
	}
	else
	{
		cout << "is not BRTree" << endl;
	}
}

int main()
{
	test1();


	return 0;
}

在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/450653.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

cnetos7 清理 journal 日志

cnetos7 清理 journal 日志

journal 日志如果长时间不清理&#xff0c;会占用系统很多空间&#xff0c;所有需要清理占用过多的一些日志。 1、查看journal日志当前使用情况&#xff0c;包括占用的磁盘空间、日志数量 journalctl --disk-usage 2、清除 journal 日志中超过 100MB 大小的内容 journalctl -…
阅读更多...
Lord 3DMCV7-AHRS 时间同步硬件触发设置

Lord 3DMCV7-AHRS 时间同步硬件触发设置

目的：通过FPGA发送脉冲触发IMU采集数据。FPGA发送脉冲时，IMU才有数据产生。 FPGA与IMU的硬件接线就不讲了，这里主要说明的是IMU的设置以及ROS驱动的config文件更改。 1. WIN上位机设置 通过IMU在WINDOWS的上位机SensorConnect对IMU的GPIO、波特率等基本功能进行设值，具体…
阅读更多...
项目解决方案：视频监控接入和录像系统设计方案（下）

项目解决方案：视频监控接入和录像系统设计方案（下）

目 录 1.概述 2. 建设目标及需求 2.1建设总目标 2.2 需求描述 ​2.3 需求分析 3.设计依据与设计原则 3.1设计依据 3.2 设计原则 4.建设方案设计 4.1系统方案设计 4.2组网说明 5.产品介绍 5.1视频监控综合资源管理平台介绍 5.2视频录像服务器和存储 5.2.…
阅读更多...
SpringController返回值和异常自动包装

SpringController返回值和异常自动包装

今天遇到一个需求&#xff0c;在不改动原系统代码的情况下。将Controller的返回值和异常包装到一个统一的返回对象中去。 例如原系统的接口 public String myIp(ApiIgnore HttpServletRequest request);返回的只是一个IP字符串"0:0:0:0:0:0:0:1"&#xff0c;目前接口…
阅读更多...
Django入门 整体流程跑通

Django入门 整体流程跑通

Django学习笔记 一、Django整体流程跑通 1.1安装 pip install django //安装 import django //在python环境中导入django django.get_version() //获取版本号&#xff0c;如果能获取到&#xff0c;说明安装成功Django目录结构 Python310-Scripts\django-admi…
阅读更多...
噬菌体展示文库类型与应用-卡梅德生物

噬菌体展示文库类型与应用-卡梅德生物

噬菌体展示抗体库构建的途径&#xff1a;目前主要有两种&#xff1a;一是有机合成法&#xff0c;二是基因合成法。前者是直接合成含有各种可能序列的短肽&#xff0c;构建至噬菌体载体。基因工程方法是将目的基因构建至载体&#xff0c;与噬菌体的pⅢ外壳蛋白融合表达。 卡梅德…
阅读更多...
数据结构——堆的应用 堆排序详解

数据结构——堆的应用 堆排序详解

&#x1f49e;&#x1f49e; 前言 hello hello~ &#xff0c;这里是大耳朵土土垚~&#x1f496;&#x1f496; &#xff0c;欢迎大家点赞&#x1f973;&#x1f973;关注&#x1f4a5;&#x1f4a5;收藏&#x1f339;&#x1f339;&#x1f339; &#x1f4a5;个人主页&#x…
阅读更多...
制造业工厂的设备管理系统

制造业工厂的设备管理系统

对企业来说&#xff0c;时间就是金钱&#xff0c;所有企业都在极力避免因生产延误而导致的金钱损失。在设备保养、设备维护和设备运行方面更是如此。如果工厂的设备因突发故障处于长时间停机状态&#xff0c;但没能被及时解决&#xff0c;工厂所需支付的成本可能就会螺旋式上升…
阅读更多...
11、设计模式之享元模式（Flyweight）

11、设计模式之享元模式（Flyweight）

一、什么是享元模式 享元模式是一种结构型的设计模式。它的主要目的是通过共享对象来减少系统种对象的数量&#xff0c;其本质就是缓存共享对象&#xff0c;降低内存消耗。 享元模式将需要重复使用的对象分为两个部分&#xff1a;内部状态和外部状态。 内部状态是不会变化的&…
阅读更多...
基于java+springboot+mybatis+laiyu实现学科竞赛管理系统

基于java+springboot+mybatis+laiyu实现学科竞赛管理系统

基于javaspringbootmybatislaiyu实现学科竞赛管理系统 博主介绍&#xff1a;5年java开发经验&#xff0c;专注Java开发、定制、远程、文档编写指导等,csdn特邀作者、专注于Java技术领域 作者主页 央顺技术团队 Java毕设项目精品实战案例《1000套》 欢迎点赞 收藏 ⭐留言 文末获…
阅读更多...
UI学习 一 可访问性 基础

UI学习 一 可访问性 基础

教程&#xff1a;Accessibility – Material Design 3 需要科学上网&#xff0c;否则图片显示不出来。设计教程没有图片说明&#xff0c;不容易理解。 优化UI方向 清晰可见的元素足够的对比度和尺寸重要性的明确等级一眼就能辨别的关键信息 传达某一事物的相对重要性 将重…
阅读更多...
蓝牙系列七：开源蓝牙协议栈BTStack数据处理（Wireshark抓包分析）

蓝牙系列七：开源蓝牙协议栈BTStack数据处理（Wireshark抓包分析）

继续蓝牙系列的研究。 在上篇博客&#xff0c;通过阅读BTStack的源码&#xff0c;大体了解了其框架&#xff0c;对于任何一个BTStack的应用程序都有一个main函数&#xff0c;这个main函数是统一的。这个main函数做了某些初始化之后&#xff0c;最终会调用到应用程序提供的btst…
阅读更多...
学习Java的第八天

学习Java的第八天

本节我们重点研究对象和类的概念。 对象&#xff08;Object&#xff09;是一个应用系统中的用来描述客观事物的实体&#xff0c;是有特定属性和行为&#xff08;方法&#xff09;的基本运行单位。是类的一个特殊状态下的实例。对象可以是一个实体、一个名词、一个可以想象为有…
阅读更多...
鸿蒙Harmony应用开发—ArkTS声明式开发（基础手势：MenuItemGroup）

鸿蒙Harmony应用开发—ArkTS声明式开发（基础手势：MenuItemGroup）

该组件用来展示菜单MenuItem的分组。 说明&#xff1a; 该组件从API Version 9开始支持。后续版本如有新增内容&#xff0c;则采用上角标单独标记该内容的起始版本。 子组件 包含MenuItem子组件。 接口 MenuItemGroup(value?: MenuItemGroupOptions) 参数&#xff1a; 参…
阅读更多...
搜索组件的编写与数据的联动

搜索组件的编写与数据的联动

src\components\SearchInput\index.vue 搜索组件编写 <template><div class"search-wrap"><input type"text":placeholder"placeholder":maxlength"maxlength":value"inputValue"input"searchData($ev…
阅读更多...
软件测试 - postman高级使用

软件测试 - postman高级使用

断言 概念&#xff1a;让程序代替人判断测试用例执行的结果是否符合预期的一个过程 特点&#xff1a; postman断言使用js编写&#xff0c;断言写在postman的tests中 tests脚本在发送请求之后执行&#xff0c;会把断言的结果最终在testresult中进行展示 常用的postman提供的…
阅读更多...
Linux系统架构----nginx的访问控制

Linux系统架构----nginx的访问控制

nginx的访问控制 一、nginx基于授权的访问控制概述 Nginx与Apache一样&#xff0c;可以实现基于用户权限的访问控制&#xff0c;当客户端想要访问相应的网站或者目录时&#xff0c;要求用户输入用户名和密码&#xff0c;才能正常访问配置步骤生成用户密码认证文件 &#xff1…
阅读更多...
48. 【Linux教程】yum 软件包管理

48. 【Linux教程】yum 软件包管理

本小节介绍如何在 Linux 系统中使用 yum 命令软件管理。 1.yum 简介 yum 是 Red Hat 软件包管理器&#xff0c;它能够查询有关可用软件包的信息&#xff0c;从存储库获取软件包&#xff0c;安装和卸载软件包&#xff0c;以及将整个系统更新到最新的可用版本。yum 在更新&#…
阅读更多...
sql注入基础学习

sql注入基础学习

1.常用SQL语句 01、显示数据库 show databases&#xff1b; 02、打开数据库 use db name&#xff1b; 03、显示数据表 show tables&#xff1b; 04、显示表结构 describe table_name&#xff1b; 05、显示表中各字段信息&#xff0c;即表结构 show columns from table_nam…
阅读更多...
c++初阶------类和对象(下)

c++初阶------类和对象(下)

作者前言 &#x1f382; ✨✨✨✨✨✨&#x1f367;&#x1f367;&#x1f367;&#x1f367;&#x1f367;&#x1f367;&#x1f367;&#x1f382; ​&#x1f382; 作者介绍&#xff1a; &#x1f382;&#x1f382; &#x1f382; &#x1f389;&#x1f389;&#x1f389…
阅读更多...
最新文章

Copyright @ 2022~2023