红黑树底层实现

什么是红黑树

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

一棵红黑树有以下特性: 

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

因为每条路径中黑色结点的个数都是一定的,且红色结点是不能连续的,所以红黑树的一条路径上的结点数最少就是:n(全黑),最多就是 2n个(黑红相间隔),因为保证了这棵树的相对均衡,所以最差的查找是复杂度也是 O(log2*N)

那为什么不用 AVL树来存储呢,查找效率不是更高一些?

AVL树是依据高度差(平衡因子)来旋转调整树的形状的,一旦左右子树平衡因子之差超过1,就要进行旋转;而红黑树是正常插入数据,通过变色来调整维持红黑树的特性,直到通过变色无法维持红黑树的特性时才进行旋转调整,因此相对于AVL树旋转次数更少一些,效率较高。

红黑树结点

相对于普通搜索二叉树多了个_parent的指针,方便建立树,一个枚举类型的变量表示树的颜色。 

红黑树的插入及验证

红黑树的插入内核就是依照二叉搜索树的基本方法进行插入,但如果违反了红黑树的特性,就要进行调整。

  • 插入红色结点:因为红黑树中的每条路径上的黑色结点的个数都是一定的,因此插入的时候只有插入红色结点,才能保证不影响每条路径黑色结点个数相等这一特性。
  • 看插入结点的父亲结点的颜色:确定插入的是红色结点,那么就要看父亲结点的颜色,父亲结点如果是黑色,那么插入就直接结束了,如果父亲结点是红色,那么就违反了红黑树的第三个特性,要进行调整,去看叔叔结点的颜色。
  • 看叔叔结点:叔叔结点(父亲的父亲结点的另一个孩子结点),父亲为红色。如果叔叔也为红色,那么隐藏条件就是爷爷结点为黑色,这种情况只需要将爷爷结点的颜色变为红色,父亲和叔叔结点的颜色变为黑色,这样就保证了红黑树的特性;如果叔叔不存在或者叔叔为黑色,那就需要旋转和变色一起调整了,因为此时仅仅靠变色已经难以解决问题了,至于如果旋转,只需要遵循红黑树的他特性。

验证建立的红黑树是否正确,就要从红黑树的几个特性依次卡,只要不符合就返回 false,只有全部成立才返回 true

代码实现

#pragma once
#include<iostream>
using namespace std;
typedef enum Color
{
	RED,  // 红色
	BLACK // 黑色
}Color;
template<class K, class V>
struct RBTreeNode
{
	RBTreeNode(const pair<K, V>& kv)
		:_right(nullptr)
		, _left(nullptr)
		, _parent(nullptr)
		,_col(RED)
		, _kv(kv)
	{}
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _parent;
	// 颜色:枚举类型
	Color _col;
	pair<K, V> _kv;
	 
};

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->_parent = parent;
		// 调整父子之间的关系
		if (parent->_kv.first < kv.first)
			parent->_right = cur;
		else if (parent->_kv.first > kv.first)
			parent->_left = cur;
		Node* grandparent = parent->_parent;
		while (parent && parent->_col == RED)
		{
			grandparent = parent->_parent;
			Node* uncle = nullptr;
			// 调整父亲和叔叔与爷爷的关系
			if (parent->_kv.first > grandparent->_kv.first)
			{
				grandparent->_right = parent;
				uncle = grandparent->_left;
			}
			else if (parent->_kv.first < grandparent->_kv.first)
			{
				grandparent->_left = parent;
				uncle = grandparent->_right;
			}
			// 新插入结点的父亲是红色结点,需要调整
			// 调整父亲和叔叔的左右
			if (uncle && uncle->_col == RED) // 叔叔存在并且为红色
			{
				grandparent->_col = RED;
				uncle->_col = parent->_col = BLACK;
				cur = grandparent;
				parent = cur->_parent;
			}
			else if(uncle == nullptr || uncle->_col == BLACK)
			{
				if (parent == grandparent->_left)
				{
					if (cur == parent->_left)
					{
						RotateR(grandparent);
						parent->_col = BLACK;
						grandparent->_col = RED;
					}
					else if (cur == parent->_right)
					{
						RotateL(parent);
						RotateR(grandparent);
						cur->_col = BLACK;
						grandparent->_col = RED;
					}
				}
				else
				{
					if (cur == parent->_left)
					{
						RotateR(parent);
						RotateL(grandparent);
						grandparent->_col = RED;
						cur->_col = BLACK;
					}
					else if (cur == parent->_right)
					{
						RotateL(grandparent);
						grandparent->_col = RED;
						parent->_col = BLACK;
					}
				}
				break;
			}
		}
		_root->_col = BLACK;
		return true;
	}
	bool IsValidRBTree()
	{
		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)
	{
		//走到null之后,判断k和black是否相等
		if (nullptr == pRoot)
		{
			if (k != blackCount)
			{
				cout << "违反性质四:每条路径中黑色节点的个数必须相同" << endl;
				return false;
			}
			return true;
		}
		// 统计黑色节点的个数
		if (BLACK == pRoot->_col)
			k++;
		// 检测当前节点与其双亲是否都为红色
		Node* pParent = pRoot->_parent;
		if (pParent && RED == pParent->_colo && RED == pRoot->_col)
		{
			cout << "违反性质三:没有连在一起的红色节点" << endl;
			return false;
		}
		return _IsValidRBTree(pRoot->_left, k, blackCount) && 
			_IsValidRBTree(pRoot->_right, k, blackCount);
	}
	void Order()
	{
		_Order(_root);
		cout << endl;
	}
	void _Order(Node* root)
	{
		if (root == nullptr)
			return;
		_Order(root->_left);
		cout << root->_kv.first << " ";
		_Order(root->_right);
	}
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		Node* parentParent = parent->_parent;
		subL->_right = parent;
		parent->_parent = subL;
		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;
		if (parent == _root)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (parentParent->_left == parent)
			{
				parentParent->_left = subL;
			}
			else if (parentParent->_right == parent)
			{
				parentParent->_right = subL;
			}
			subL->_parent = parentParent;
		}
	}
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		Node* parentParent = parent->_parent;
		subR->_left = parent;
		parent->_parent = subR;
		if (subRL)
			subRL->_parent = parent;
		parent->_right = subRL;
		if (parent == _root)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			// 先找到 parent 是父亲的左子树还是右子树
			if (parentParent->_left == parent) // 左子树
			{
				parentParent->_left = subR;
			}
			else if (parentParent->_right == parent) // 右子树
			{
				parentParent->_right = subR;
			}
			subR->_parent = parentParent;
		}
	}
private:
	Node* _root = nullptr;
};

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

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

相关文章

微信小程序开发position等于static、relative、absolute、fixed、stricky时元素显示详细介绍

No Position 不设置position时显示,以红色元素做测试: Static 元素根据界面正常流进行定位。top、right、bottom、left 和 z-index 属性不起作用。这是默认值。 红色元素设置position: static,显示如下: Relative 元素根据界面正常流进行定位。以元素当前位置为基准,根…

g2o--ba代码解析

概要 g2o是常用的图优化理论c库&#xff0c;其自带了很多example讲解如何使用该库文件&#xff0c;本文分析其中ba的示例代码。 所谓的图优化&#xff0c;就是把一个常规的优化问题&#xff0c;以图&#xff08;Graph&#xff09;的形式来表述。 在图中&#xff0c;以顶点表…

单片机介绍

本文为博主 日月同辉&#xff0c;与我共生&#xff0c;csdn原创首发。希望看完后能对你有所帮助&#xff0c;不足之处请指正&#xff01;一起交流学习&#xff0c;共同进步&#xff01; > 发布人&#xff1a;日月同辉,与我共生_单片机-CSDN博客 > 欢迎你为独创博主日月同…

Spring Boot 模块工程(通过 Maven Archetype)建立

前言 看到我身边的朋友反馈说&#xff0c;IDEA 新建项目时&#xff0c;如果通过 Spring Initializr 来创建 Spring Boot , 已经无法选择 Java 8 版本&#xff0c;通过上小节的教程&#xff0c;不知道该如何创建 Spring Boot 模块工程。如下图所示&#xff1a; 一.IDEA 搭建 …

记录一下uniapp 集成腾讯im特别卡(已解决)

uniapp的项目运行在微信小程序 , 安卓 , ios手机三端 , 之前这个项目集成过im,不过版本太老了,0.x的版本, 现在需要添加客服功能,所以就升级了 由于是二开 , 也为了方便 , 沿用之前的webview嵌套腾讯IM的方案 , 选用uniapp集成ui ,升级之后所有安卓用户反馈点击进去特别卡,几…

【深度学习】CodeFormer训练过程,如何训练人脸修复模型CodeFormer

文章目录 BasicSR介绍环境数据阶段 I - VQGAN阶段 II - CodeFormer (w0)阶段 III - CodeFormer (w1) 代码地址&#xff1a;https://github.com/sczhou/CodeFormer/releases/tag/v0.1.0 论文的一些简略介绍&#xff1a; https://qq742971636.blog.csdn.net/article/details/134…

Mysql索引相关学习笔记:B+ Tree、索引分类、索引优化、索引失效场景及其他常见面试题

前言 索引是Mysql中常用到的一个功能&#xff0c;可以大大加快查询速度&#xff0c;同时面试中也是经常碰到。本文是学习Mysql索引的归纳总结。 索引采用的数据结构——B 树 本部分主要是参考自小林Coding B树的由来 二分查找可以每次缩减一半&#xff0c;从而提高查找效率…

【mongoDB】数据库的创建和删除

目录 1. 查看所有数据库 2.创建数据库 3.查看当前连接的数据库 4.删除数据库 1. 查看所有数据库 show dbs 2.创建数据库 use 数据库名 例如创建一个名为 aaa 的数据库 3.查看当前连接的数据库 db 4.删除数据库 use 数据库名 db.dropDataBase() 比如删除数据库 aaa

1.25号c++

1.引用 引用就是给变量起别名 格式&#xff1a; 数据类型 &引用名 同类型的变量名 &#xff08;& 引用符号&#xff09; eg: int a 10; int &b a; //b引用a,或者给a变量取个别名叫b int *p; //指针可以先定义 后指向 p &a; //int &a…

【MySQL】如何通过DDL去创建和修改员工信息表

&#x1f308;个人主页: Aileen_0v0 &#x1f525;热门专栏: 华为鸿蒙系统学习|计算机网络|数据结构与算法 ​&#x1f4ab;个人格言:“没有罗马,那就自己创造罗马~” #mermaid-svg-fmKISDBsFq74ab2Z {font-family:"trebuchet ms",verdana,arial,sans-serif;font-siz…

docker(第二部分)

来自尚硅谷杨哥 少一点胡思乱想&#xff0c;心中无女人&#xff0c;编码自然神&#xff0c;忘掉心上人&#xff0c;抬手灭红尘。人间清醒&#xff0c;赚钱第一。好好学习&#xff0c;天天向上。听懂六六六。 7.Dokcer容器数据卷 1,&#xff09;坑&#xff1a;容器卷记得加入 …

shared_ptr 与 unique_ptr 的转换 笔记

推荐B站文章&#xff1a; 6.shared_ptr与unique_ptr_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV18B4y187uL?p6&vd_sourcea934d7fc6f47698a29dac90a922ba5a3我的往期文章&#xff1a; 独占指针&#xff1a;unique_ptr 与 函数调用-CSDN博客https://blog.csdn.n…

银行数据仓库体系实践(5)--数据转换

数据转换作业主要是指在数据仓库内的结构化数据批量加工&#xff0c;对于非结构化数据以及在线查询接口、数据流的开发主要是遵循代码开发规范以及各中间件的开发规范&#xff0c;如使用java来开发遵守java开发规范&#xff0c;使用Kafka需要遵循Kafka的使用和设计规范。同时做…

对话泛能网程路:能源产业互联网,行至中程

泛能网的能源产业互联网的标杆价值还不仅于此。其在产业互联之外&#xff0c;也更大的特殊性在于其也更在成为整个碳市场的“辅助运营商”&#xff0c;包括电力、碳等一系列被泛能网帮助企业改造和沉淀的要素资产&#xff0c;都在构成着碳交易市场的未来底层。 这恰是产业互联…

有关Quick BI中Case子句中多次使用lod函数返回空值问题分析

一、Quick BI中的lod_ include函数 lod_ include {维度1[,维度2]...:聚合表达式[:过滤条件]} 作用&#xff1a;将表达式中的维度一起作为分组依据进行订算。其中&#xff0c; 1) 维度1[,维度2]... &#xff1a;声明维度&#xff0c;指定聚合表达式要连接到的一个或多个维…

开源项目Git Commit规范与ChangeLog

一&#xff0c;conventional commit(约定式提交) Conventional Commits 是一种用于给提交信息增加人机可读含义的规范。它提供了一组用于创建清晰的提交历史的简单规则。 1.1 作用 自动化生成 CHANGELOG基于提交类型&#xff0c;自动决定语义化的版本变更向项目相关合作开发…

OpenCV书签 #互信息的原理与相似图片搜索实验

1. 介绍 互信息&#xff08;Mutual Information&#xff09; 是信息论中的一个概念&#xff0c;用于衡量两个随机变量之间的关联程度。在图像处理和计算机视觉中&#xff0c;互信息常被用来度量两幅图像之间的相似性。 互信息可以看成是一个随机变量中包含的关于另一个随机变…

【网站项目】基于SSM的251国外摇滚乐队交流和周边售卖系统

&#x1f64a;作者简介&#xff1a;拥有多年开发工作经验&#xff0c;分享技术代码帮助学生学习&#xff0c;独立完成自己的项目或者毕业设计。 代码可以私聊博主获取。&#x1f339;赠送计算机毕业设计600个选题excel文件&#xff0c;帮助大学选题。赠送开题报告模板&#xff…

DAY30:回溯算法332\51\37基本思路了解+总结

Leetcode: 332 重新安排行程 代码随想录 这道题目有几个难点&#xff1a; 一个行程中&#xff0c;如果航班处理不好容易变成一个圈&#xff0c;成为死循环&#xff0c;容易出现环路。有多种解法&#xff0c;字母序靠前排在前面&#xff0c;让很多同学望而退步&#xff0c;如…

yolov8上使用gpu教程

yolov8上使用gpu教程 安装Cuda和Cudnnyolov8上使用gpu 安装Cuda和Cudnn 1.查看支持的cuda版本&#xff0c;并去官网下载。 nvidia-smi2.网址&#xff1a;https://developer.nvidia.com/cuda-toolkit-archive 3.安装细节 安装的前提基础是&#xff0c;有vs的C环境。我电脑有…