C++手撕红黑树

文章目录

    • 红黑树
      • 概念
      • 性质(条件限制)
      • 节点的定义
      • 红黑树的结构
      • 红黑树的插入
        • cur为红,p为红,g为黑,u存在且为红
        • cur为红,p为红,g为黑,u不存在或u为黑,插入到p对应的一边
        • cur为红,p为红,g为黑,u不存在或u存在且为黑,插入到与p相反的一边
        • 示例代码
      • 红黑树的验证
      • 红黑树与AVL树的比较
    • 完整代码

红黑树

概念

和AVL树一样,红黑树也是一种二叉搜索树,是解决二叉搜索树不平衡的另一种方案,他在每个节点上增加一个存储位,用于表示节点的颜色,是Red或者Black

红黑树的核心思想是通过一些着色的条件限制,达到一种最长路径不超过最短路径的两倍的状态

所以说红黑树并不是严格平衡的树,而是一种近似平衡

例如

 2024-04-08 134510.png

性质(条件限制)

红黑树一共有五条性质,由此来保证最长路径不超过最短路径的两倍

  1. 每个节点都有颜色,不是黑色就是红色
  2. 根节点是黑色的
  3. 如果一共节点是红色,那么他的子节点一定是黑色(不会出现两个红色节点连接的情况)
  4. 对于每个节点,以这个节点到所有后代的任意路径上,均包含相同数目的黑色节点
  5. 每个叶子节点(空节点)是黑色的(为了满足第四条性质,某些情况下如果没有第五条第四条会失效)

节点的定义

// 颜色
enum Color {
	RED,
	BLACK
};

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

	T _data;

	Color _col;

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

我们定义颜色时,使用枚举类型,可以方便且明了的看到颜色

除此之外我们默认插入节点是红色的,因为一旦插入节点是黑色,就会违反第四条规则,如果要满足的话,就要走到每一条路径上插入对应的黑色节点,代价巨大

当插入节点是红色时,有可能会违反第三条规则,但是我们可以通过变色,旋转等操作在局部进行改变,这样就能使之仍然满足条件

红黑树的结构

为了后续利用红黑树封装map和set,我们对红黑树增加一个头节点,为了和根节点进行区分,我们将头节点赋为黑色,并且让头节点的parent指向根节点,left指向红黑树的最小节点,right指向最大节点,如图

image.png

红黑树的插入

红黑树插入时也是按照二叉搜索树的规则进行插入,并在此基础上加上平衡条件,因此插入也就分为两步

  1. 按照二叉搜索树的规则插入新节点
  2. 插入节点后检测规则是否被破坏

因为插入红节点时只有可能破坏第三条规则,因此我们只需要判断父节点是否为红色即可

然后我们分情况讨论

为了方便叙述,我们约定cur为插入节点,p为父节点,g为祖父节点,u为叔叔节点

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

画出来是这样的

image.png

这时我们需要将g改为红色,p和u改为黑色即可,这样既能保证红色不连续,黑色数量一致,如图

image.png

但是如果g是是子树,那么g一定有父节点,当g的父节点也是红色时,也就同样需要向上调整了

cur为红,p为红,g为黑,u不存在或u为黑,插入到p对应的一边

画出来是这样的

image.png

u的情况有两种

  1. u节点不存在,说明cur一定是新插入的节点,因为要保证左右两个路径的黑色节点的数量相同
  2. u节点存在,说明cur节点是由下至上调整的红色,原因也是左右路径的黑色节点要相同

对于这两种情况的调整方法是相同的,如果p是g的左节点,cur为p的左节点,则右单旋,如果p是g的右节点,cur为p的右节点,则左单旋

同时p要变成黑色,g要变成红色

变成如下状态

image.png

那么因为最上面的根节点颜色没有变化,也就不需要继续向上调整了

cur为红,p为红,g为黑,u不存在或u存在且为黑,插入到与p相反的一边

如图

image.png

这种情况需要针对p进行单旋,如果p为g的左节点,cur为p的右节点,则对p左单旋,反之则为右单旋,此时就会变成第二种情况,再继续处理即可

第一次处理的结果如下

image.png

示例代码
template<class K, class T, class KeyOfT>
class RBTree {
	typedef RBTreeNode<T> Node;
public:
	pair<Node*, bool> Insert(const T& data) {
		// 插入根节点直接返回
		if (_root == nullptr) {
			_root = new Node(data);
			_root->_col = BLACK;
			return make_pair(_root, true);
		}

		Node* parent = nullptr;
		Node* cur = _root;
		KeyOfT kot;

		// 平衡二叉树找到插入位置
		while (cur) {
			if (kot(cur->_data) < kot(data)) {
				parent = cur;
				cur = cur->_right;
			} else if (kot(cur->_data) > kot(data)) {
				parent = cur;
				cur = cur->_left;
			} else {
				return make_pair(cur, false);
			}
		}

		// 新建节点
		cur = new Node(data);
		Node* newnode = cur;
		cur->_col = RED;

		// 连接父节点
		if (kot(parent->_data) < kot(data)) {
			parent->_right = cur;
			cur->_parent = parent;
		} else {
			parent->_left = cur;
			cur->_parent = parent;
		}

		// 如果父节点存在且父节点为红色则需要调整
		while (parent && parent->_col == RED) {
			Node* grandfather = parent->_parent;
			if (parent == grandfather->_left) {
				//     g
				//   p   u
				// c 
				// 判断u是否存在和他的颜色
				Node* uncle = grandfather->_right;
				// 如果存在且为红色
				if (uncle && uncle->_col == RED) {
					// 变色
					parent->_col = BLACK;
					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 { // p = g->r
				Node* uncle = grandfather->_left;
				//     g
				//   u   p
				//         c
				// 判断u是否存在和他的颜色
				// 如果存在且为红色
				if (uncle && uncle->_col == RED) {
					// 变色
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;

					// 向上调整
					cur = grandfather;
					parent = cur->_parent;
				} else {
					if (cur == parent->_right) {
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					} else {
						//     g
						//   u   p 
						//     c
						//
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
		}

		_root->_col = BLACK;

		return make_pair(newnode, true);


	}

	void RotateL(Node* parent) {
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

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

		Node* parentParent = parent->_parent;

		parent->_parent = subR;
		if (subRL)
			subRL->_parent = parent;
		else {
			if (parentParent->_left == parent) {
				parentParent->_left = subR;
			} else {
				parentParent->_right = subR;
			}

			subR->_parent = parentParent;
		}
	}

	void RotateR(Node* parent) {
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

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

		Node* parentParent = parent->_parent;

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

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

			subL->_parent = parentParent;
		}
	}
private:
	Node* _root = nullptr;
};

红黑树的验证

红黑树要验证需要验证两个部分

  1. 检测是否中序遍历是有序序列
  2. 检测是否满足红黑树的性质

这里我们就不讲红黑树的删除了,完成红黑树的验证之后就算作已经完成了任务,接下来会使用红黑树模拟实现map和set

红黑树与AVL树的比较

红黑树和AVL树都是高效的平衡二叉树,但是红黑树不追求绝对的平衡,降低了插入和旋转的次数,因此性能比AVL更优,而且红黑树比AVL树的实现更加简单,所以实际中运用红黑树更多

完整代码

#pragma once
#include<utility>
#include<iostream>
using namespace std;
// 颜色
enum Color {
	RED,
	BLACK
};

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

	T _data;

	Color _col;

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


template<class K, class T, class KeyOfT>
class RBTree {
	typedef RBTreeNode<T> Node;
public:
	pair<Node*, bool> Insert(const T& data) {
		
		if (_root == nullptr) {
			_root = new Node(data);
			_root->_col = BLACK;
			return make_pair(_root, true);
		}

		Node* parent = nullptr;
		Node* cur = _root;
		KeyOfT kot;

		// 平衡二叉树找到插入位置
		while (cur) {
			if (kot(cur->_data) < kot(data)) {
				parent = cur;
				cur = cur->_right;
			} else if (kot(cur->_data) > kot(data)) {
				parent = cur;
				cur = cur->_left;
			} else {
				return make_pair(cur, false);
			}
		}

		// 新建节点
		cur = new Node(data);
		Node* newnode = cur;
		cur->_col = RED;

		// 连接父节点
		if (kot(parent->_data) < kot(data)) {
			parent->_right = cur;
			cur->_parent = parent;
		} else {
			parent->_left = cur;
			cur->_parent = parent;
		}

		// 如果父节点存在且父节点为红色则需要调整
		while (parent && parent->_col == RED) {
			Node* grandfather = parent->_parent;
			if (parent == grandfather->_left) {
				//     g
				//   p   u
				// c 
				// 判断u是否存在和他的颜色
				Node* uncle = grandfather->_right;
				// 如果存在且为红色
				if (uncle && uncle->_col == RED) {
					// 变色
					parent->_col = BLACK;
					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 { // p = g->r
				Node* uncle = grandfather->_left;
				//     g
				//   u   p
				//         c
				// 判断u是否存在和他的颜色
				// 如果存在且为红色
				if (uncle && uncle->_col == RED) {
					// 变色
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;

					// 向上调整
					cur = grandfather;
					parent = cur->_parent;
				} else {
					if (cur == parent->_right) {
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					} else {
						//     g
						//   u   p 
						//     c
						//
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
		}

		_root->_col = BLACK;

		return make_pair(newnode, true);


	}

	void RotateL(Node* parent) {
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

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

		Node* parentParent = parent->_parent;

		parent->_parent = subR;
		if (subRL)
			subRL->_parent = parent;
		else {
			if (parentParent->_left == parent) {
				parentParent->_left = subR;
			} else {
				parentParent->_right = subR;
			}

			subR->_parent = parentParent;
		}
	}

	void RotateR(Node* parent) {
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

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

		Node* parentParent = parent->_parent;

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

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

			subL->_parent = parentParent;
		}
	}

	void InOrder() {
		_InOrder(_root);
		cout << endl;
	}

	void _InOrder(Node* root) {
		if (root == nullptr)
			return;
		_InOrder(root->_left);
		cout << root->_data << ' ';
		_InOrder(root->_right);
	}

	bool Check(Node* root, int blacknum, const int refVal) {
		if (root == nullptr) {
			if (blacknum != refVal) {
				cout << "存在黑色节点数量不相等的路径" << endl;
				return false;
			}
			return true;
		}

		if (root->_col == RED && root->_parent->_col == RED) {
			cout << "存在连续的红节点" << endl;
			return false;
		}

		if (root->_col == BLACK) {
			++blacknum;
		}
		
		return Check(root->_left, blacknum, refVal) && Check(root->_right, blacknum, refVal);
	}

	bool IsBalance() {
		if (_root == nullptr)
			return true;

		if (_root->_col == RED)
			return false;

		int refVal = 0; // 参考值
		Node* cur = _root;
		while (cur) {
			if (cur->_col == BLACK) {
				++refVal;
			}
			cur = cur->_left;
		}

		int blacknum = 0;
		return Check(_root, blacknum, refVal);
	}

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

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

		int leftH = _Height(root->_left);
		int rightH = _Height(root->_right);

		return leftH + rightH;
	}

	size_t Size() {
		return _Size(_root);
	}

	size_t _Size(Node* root) {
		if (root == nullptr)
			return 0;
		return _Size(root->_left) + _Size(root->_right) + 1;
	}

	Node* Find(const K& key) {
		Node* cur = _root;
		while (cur) {
			if (cur->_data < key) {
				cur = cur->_right;
			}
			else if (cur->_data > key) {
				cur = cur->_left;
			}
			else {
				return cur;
			}
		}
		return nullptr;
	}

private:
	Node* _root = nullptr;
};

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

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

相关文章

Vue3报错:‘defineProps‘ is not defined no-undef

解决方法 在package.json中添加 "vue/setup-compiler-macros": true 记得在上面的 "node": true 后面加一个逗号 "eslintConfig": {"root": true,"env": {"node": true,"vue/setup-compiler-macros": t…

考PMP一定要培训吗?PMP备考可不是说着玩的

想要考项目管理认证一定要培训吗&#xff1f;其实这是必要的也是必须的啦&#xff0c;不仅仅是因为自学的难度大&#xff0c;个人自学很难总结学习技巧&#xff0c;另一个原因就是考试前还必须要有授权培训机构提供的35学时培训证明&#xff0c;没有这个培训证明也就直接意味着…

【C++11】initializer_list | 右值引用 | 完美转发

一切皆可列表{ }初始化 在C98,允许花括号{ } 对数组、结构体类型初始化。 class Data { public:Data(int y, int m, int d):_y(y), _m(m), _d(d){} private:int _y;int _m;int _d; };int arr[4]{0,1,2,3};//列表初始化 Data d1{2024,03,21};//列表初始化 C11允许通过{ } 初始化…

LangChain教程 | 实践过程报错集 | 持续更新

这是本人最近在做langchain教程过程中的遇到的报错&#xff0c;不分先后顺序。 报错&#xff1a;TypeError: NoneType object is not iterable 这个报错很常见&#xff0c;咱们要看原始报错的位置是哪里&#xff0c;下面是我的截图&#xff1a; 找到源头之后&#xff0c;就在源…

使用idea运行程序,发现控制台的中文出现乱码

修改UTF-8发现没有效果&#xff0c;寻找.idea文件夹的encodings.xml文件&#xff0c;将里面的UTF-8全部变成GBK.

(一)基于IDEA的JAVA基础12

一维数组 为什么使用数组: 当我们需要存储一系列数据的时候&#xff0c;就需要用到数组&#xff0c;如果不使用数组&#xff0c;我们就要需要一个一个的去声明变量&#xff0c;这样浪费内存空间&#xff0c;同时效率低下。 什么是数组: 数组本身就是一个变量&#xff0c;只…

爱普生新一代可编程振荡器系列SG-8018

频率范围: 0.67 MHz-170 MHZ 温度范围: -40C to 105C 精度: 50 ppm including aging(包括老化) 供电电压: 1.8V, 2.5V, 3.3V(1.62V-3.63V) 低功耗: 3.2 mA-8.1 mA maximum 单端输出模式: LVCMOS 可编程上升/下降时间&#xff1a;输出使用(OE)或待机功能(ST) 4种封装尺寸…

testng接口自动化2@Test常见参数

接下来是Test注解里的一些常用参数 1,enabled 是否执行此用例&#xff0c;若enabled false&#xff0c;则不执行此方法&#xff0c;若enabled true 则此方法执行&#xff0c;如图test1的testDemo3设置为true&#xff0c;testDemo2设置为false,则testDemo2没执行 2,expecte…

蓝桥杯 历届真题 时间显示【第十二届】【省赛】【C组】

资源限制 内存限制&#xff1a;256.0MB C/C时间限制&#xff1a;1.0s Java时间限制&#xff1a;3.0s Python时间限制&#xff1a;5.0s #include<bits/stdc.h> #define int long long using namespace std; const int N 1e510; int n,m,t,d; int a[2][N],b[N]; //…

Nuxt3 实战 (三):使用 release-it 自动管理版本号和生成 CHANGELOG

release-it 能做什么&#xff1f; 增加版本号并提交 Git生成变更日志&#xff08;Changelog&#xff09;并提交到 Git创建 Git 标签并推送到远程仓库发布到 npm 等软件仓库在 GitHub、GitLab 等平台创建发行版 前置知识 在看这篇文章之前&#xff0c;我们有必要了解一下 Sem…

深入了解iOS内存(WWDC 2018)笔记-内存诊断

主要记录下用于分析iOS/macOS 内存问题的笔记。 主要分析命令&#xff1a; vmmap, leaks, malloc_history 一&#xff1a;前言 有 3 种思考方式 你想看到对象的创建吗&#xff1f;你想要查看内存中引用对象或地址的内容吗&#xff1f;或者你只是想看看 一个实例有多大&#…

构建第一个ArkTS之页面和自定义组件生命周期

在开始之前&#xff0c;我们先明确自定义组件和页面的关系&#xff1a; 自定义组件&#xff1a;Component装饰的UI单元&#xff0c;可以组合多个系统组件实现UI的复用&#xff0c;可以调用组件的生命周期。页面&#xff1a;即应用的UI页面。可以由一个或者多个自定义组件组成&…

nginx到底是怎么工作的

工作流程 用户通过域名发出访问Web服务器的请求&#xff0c;该域名被DNS服务器解析为反向代理服务器的IP地址反向代理服务器接受用户的请求反向代理服务器在本地缓存中查找请求的内容&#xff0c;找到后直接把内容发送给用户如果本地缓存里没有用户所请求的信息内容&#xff0…

【Java】Java中类的初始化顺序(静态方法,静态块,非静态块,最后有流程图)

&#x1f4dd;个人主页&#xff1a;哈__ 期待您的关注 在日常使用Java的时候&#xff0c;我们都接触过new这个关键字&#xff0c;那你是否知道在我们的对象真正创建出来之前都做了哪些事情呢&#xff1f; 实际上要去判断一个类的初始化的顺序&#xff0c;需要分一下情况&…

Qt使用QWidget重绘实现圆环形渐变色进度条(支持不确定进度模式)

效果如下&#xff1a; 从纯竖直方向顶部蓝色到底部青色的渐变。 从左上角偏左45到右下角偏右45的蓝色到青色渐变。 从左上角偏左22.5到右下角偏右22.5的蓝色到青色渐变。&#xff08;这个角度渐变最好看&#xff09; 可以选择添加背景图片 支持两种模式&#xff1a;正常进度模…

媒体邀约专访如何深入的做一篇专访报道?流程分享

传媒如春雨&#xff0c;润物细无声&#xff0c;大家好&#xff0c;我是51媒体网胡老师。 进行媒体邀约专访并深入撰写一篇专访报道是一个系统性工作&#xff0c;涉及多个环节。以下是一个详细的流程分享&#xff1a; 一、前期准备 确定专访目的与主题&#xff1a;明确专访希…

Training - 使用 WandB 配置管理模型训练过程

欢迎关注我的CSDN&#xff1a;https://spike.blog.csdn.net/ 本文地址&#xff1a;https://blog.csdn.net/caroline_wendy/article/details/137529140 WandB (Weights&Biases) 是轻量级的在线模型训练可视化工具&#xff0c;类似于 TensorBoard&#xff0c;可以帮助用户跟踪…

可编程网关:如何助力智慧工厂实现智能化管理

一个具体的实际案例&#xff0c;详细说明可编程网关在某汽车零部件智慧工厂中的应用细节&#xff1a; 案例背景&#xff1a; 某大型汽车零部件制造企业&#xff0c;致力于提升生产效率、降低运营成本、确保产品质量&#xff0c;决定对其传统工厂进行全面数字化改造&#xff0…

从零开始:一步步学习爬虫技术的实用指南(一)

从零开始&#xff1a;一步步学习爬虫技术的实用指南&#xff08;一&#xff09; Urllib1.什么是互联网爬虫2.爬虫核心3.爬虫的用途4.爬虫的分类4.1 通用爬虫&#xff1a;4.1 聚焦爬虫&#xff1a; 5.反爬手段5.1 User‐Agent&#xff1a;5.2.代理IP5.3.验证码访问5.4.动态加载网…

深入理解JVM后端优化技术-逃逸分析(Escape Analysis)

相关系统 深入理解jvm执行引擎-CSDN博客 深入理解JVM后端优化技术-方法内联-CSDN博客 定义 当一个对象在方法里面被定义后,它可能让外部方法所引用,作为调用参数传递到其它的方法中,这种称为方法逃逸;还有可能被外部线程访问到,赋值给可以在其它线程中访问的实例数量,这…