带你手撕红黑树！ c++实现 带源码

2024-05-13 01:52
文章标签 c++ 实现 源码 黑树 撕红

本文主要是介绍带你手撕红黑树！ c++实现 带源码，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

一、概念

二、特性

三、接口实现

1、插入

情况一：p为黑，结束

情况二：p为红

1）叔叔存在且为红色

2）u不存在/u存在且为黑色

（1）p在左，u在右

（2）u在左，p在右

2、检查平衡

四、对红黑树的理解

五、原码

一、概念

红黑树：AVL树不好控制（严格平衡），所以推出了红黑树
不用高度控制平衡，用颜色
最长路径<= 最短路径*2
红黑树是近似平衡

二、特性

1、每个节点不是红色就是黑色
2、根节点是黑色的
3、如果一个节点是红色的，则他的两个孩子是黑色的（不存在连续的红色节点）
4、如果对于每个节点，从该节点到其后代节点的简单路径上，均包含相同数目的黑色节点（每条路径的黑色节点数量相等）
5、每个叶子节点都是黑色的（叶子节点指的是空节点）

最短路径：全黑
最长路径：一黑一红

三、接口实现

1、插入

说明：p为父，cur为当前节点，u为叔叔节点，g为祖父节点

情况一：p为黑，结束

情况二：p为红

1）叔叔存在且为红色

怎么办？
将p和u变黑，g变红    
    （1）如果g是根节点，再变为黑色


    （2）如果g不是根，继续往上调整 g变cur, parent = g->parent


        有可能会一路更新到根节点，即父节点不存在
        c++库内部的处理是，直接将parent作为while循环条件之一
        然后，在单次数循环结束位置将parent置为黑
        保证parent为黑

2）u不存在/u存在且为黑色

p改黑，g改红,再旋转

（1）p在左，u在右

情况1
//        g
//      p          u
//  c
//
p在左，u在右：以g进行右单旋
p变黑，g变红
 
情况2
//        g
//      p          u
//            c
//
c在右：以p进行左单旋变为情况1
//        g
//      c          u
//  p
//
需修改p和c位置
//        g
//      p          u
//  c
//
再以g右单旋转
p变黑，g变红

（2）u在左，p在右

情况1
//        g
//      u          p
//                  c
//
以g进行左单旋
p变黑，g变红
 


情况2
//        g
//      u          p
//                   c
//
以p进行右单旋变为情况1
//        g
//      u          c
//                p
//
需修改p和c位置
//        g
//      u          p
//                 c
//
再以g右单旋转
p变黑，g变红

2、检查平衡


计算每一条路径的黑色节点的个数
检查是否有连续红色节点
递归
走到空的时候，说明该路径走到头了


p为红之后，就要判断p是左边还是右边
即：u在左，p在右 和 u在右，p在左
就是在p为红色的同时话要细分为两种大情况
然后对于内部还要进行u的判断

四、对红黑树的理解

红黑树的核心，是保证最长路径的长度不超过最短路径的两倍
怎么做到整个特性呢？
通过维持其四个特性
尤其是特性三和特性四
所以，在插入的时候，就要考虑不能打破特性3和特性4
特性3是不能有连续的红色节点
特性4是所有路径的黑色节点个数相同
相比之下，维持特性4明显要比特性3更加严格
维持成本更高，同时也更加难以控制
所以，在插入的时候，为了便于控制和成本
我们选择插入红色节点
剩下的问题，就是要怎么避免出现连续两个红色节点
如果插入的时候，父节点就已经是一个黑色节点
那么，直接插入，此时不会出现连续两个红色节点
同时，这个条路径的黑色节点个数也没有发生变化
但是，如果插入的父节点是一个红色节点呢？
问题来了
怎么办？
父节点是红色，插入的也是红色
只能有一个变黑色
谁变？
新插入节点吗？
如果新插入节点是黑色，那么插入路径黑色节点个数就增大了
就要去维护其他的所有路径的
何其恐怖
所以，只能父节点变黑色
同时，如果父亲有兄弟，就是叔叔节点存在
父节节点变为黑色，父亲节点的路径黑色节点多了一个
那么作为另外一条路径的叔叔节点，也必须变为黑色，也增加一个黑色节点，才能保持
而，父节点的父节点，即祖父节点一定存在且为黑色
因为父节点和叔叔节点（如果存在）已经变为黑色
那么，对于祖父作为根节点的这课子树来说，多了一个黑色节点
因此，祖父节点必须变为红色
以保持平衡
如此，以祖父节点作为根节点的这棵子树已经保持了黑色节点数量不变
但是因为祖父节点已经变为了红色，需要继续往上更改颜色

五、原码

#pragma once
#include<vector>
#include<iostream>
using namespace std;enum Colour{BLACK,RED};template<class K, class V>struct BRTreeNode{BRTreeNode<K, V>* _parent;BRTreeNode<K, V>* _right;BRTreeNode<K, V>* _left;pair<K, V> _kv;Colour _col;BRTreeNode(const pair<K, V>& kv):_parent(nullptr), _right(nullptr), _left(nullptr), _kv(kv), _col(RED){}};template<class K, class V>class BRTree{typedef BRTreeNode<K, V> Node;public:bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else//找到相等key{return false;}}cur = new Node(kv);cur->_col = RED;if (kv.first < parent->_kv.first)//插入左{parent->_left = cur;}else //插入右{parent->_right = cur;}cur->_parent = parent;//插入之后，要进行颜色调整while (parent && parent->_col == RED)//如果为空/黑色节点，直接结束{//Node* grandfather = parent->_parent;if (parent == grandfather->_left)//p为左，u为右{Node* uncle = grandfather->_right;//如果叔叔存在，且为红色if (uncle && uncle->_col == RED){//修改颜色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//向上更新cur = grandfather;parent = cur->_parent;}else//叔叔不存在/叔叔存在且为黑色{if (cur == parent->_left){//		   g//	   p      u//  c//RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//		   g//	   p      u//      c//RotateL(parent);//		   g//	   c      u//  p//RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else//p为右，u为左{Node* uncle = grandfather->_left;//如果叔叔存在，且为红色if (uncle && uncle->_col == RED){//修改颜色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//向上更新cur = grandfather;parent = cur->_parent;}else//叔叔不存在/叔叔存在且为黑色{if (cur == parent->_right){//		   g//	   u      p//					c//RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//		   g//	   u      p//          c//RotateR(parent);//		   g//	   u      c//  				p//RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}//右旋void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)//subLR可能为空{subLR->_parent = parent;}subL->_right = parent;Node* ppNode = parent->_parent;parent->_parent = subL;//注意修改顺序if (parent == _root){_root = subL;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}}//左旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL){subRL->_parent = parent;}subR->_left = parent;Node* ppNode = parent->_parent;parent->_parent = subR;if (parent == _root){_root = subR;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}}//检查平衡bool isBalance(){if (_root->_col == RED){return false;}//找到任意一条路黑色节点个数Node* cur = _root;int refNum = 0;while (cur){if (cur->_col == BLACK){refNum++;}cur = cur->_left;}return Check(_root, 0,  refNum);return 1;}void Inoder(){_Inoder(_root);cout << endl;}private:bool Check(Node* root,int blackNum,const int refNum){//到路径结束位置检查黑色节点if (root == nullptr){if (blackNum != refNum){cout << "黑色节点不相等" << endl;return false;}// << blackNum << endl;return true;}//检查红色节点if (root->_col == RED && root->_parent->_col == RED){cout << root->_kv.first << "连续红节点" << endl;return false;}if (root->_col == BLACK){blackNum++;}return Check(root->_left, blackNum, refNum)&& Check(root->_right, blackNum, refNum);}void _Inoder(const Node* root){if (root == nullptr){return;}_Inoder(root->_left);cout << root->_kv.first << ":" << _root->_kv.second << endl;_Inoder(root->_right);}private:Node* _root = nullptr;};void BRTreeTest1(){int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };int b[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14,8, 3, 1, 10, 6, 4, 7, 14, 13 };BRTree<int, int> t;for (auto e : b){t.Insert({ e,e });}t.Inoder();int ret = t.isBalance();cout << ret << endl;}void BRTreeTest2(){int n = 10000000;//1000万个节点进行测试srand(time(0));vector<int> v;v.reserve(n);for (int i = 0; i < n; ++i){v.push_back(rand() + i);}size_t T1 = clock();BRTree<int, int> t;for (auto e : v){t.Insert(make_pair(e, e));}size_t T2 = clock();cout << "insert:" << T2 - T1 << endl;int ret = t.isBalance();cout << ret << endl;}

这篇关于带你手撕红黑树！ c++实现 带源码的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/984358。

相关文章

python使用watchdog实现文件资源监控

python使用watchdog实现文件资源监控

《python使用watchdog实现文件资源监控》watchdog支持跨平台文件资源监控,可以检测指定文件夹下文件及文件夹变动,下面我们来看看Python如何使用watchdog实现文件资源监控吧... python文件监控库watchdogs简介随着Python在各种应用领域中的广泛使用，其生态环境也
阅读更多...
el-select下拉选择缓存的实现

el-select下拉选择缓存的实现

《el-select下拉选择缓存的实现》本文主要介绍了在使用el-select实现下拉选择缓存时遇到的问题及解决方案,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录项目场景：问题描述解决方案：项目场景：从左侧列表中选取字段填入右侧下拉多选框，用户可以对右侧
阅读更多...
深入理解C++ 空类大小

深入理解C++ 空类大小

《深入理解C++空类大小》本文主要介绍了C++空类大小,规定空类大小为1字节,主要是为了保证对象的唯一性和可区分性,满足数组元素地址连续的要求,下面就来了解一下... 目录1. 保证对象的唯一性和可区分性2. 满足数组元素地址连续的要求3. 与C++的对象模型和内存管理机制相适配查看类对象内存在C++中，规
阅读更多...
Python pyinstaller实现图形化打包工具

Python pyinstaller实现图形化打包工具

《Pythonpyinstaller实现图形化打包工具》：本文主要介绍一个使用PythonPYQT5制作的关于pyinstaller打包工具,代替传统的cmd黑窗口模式打包页面,实现更快捷方便的... 目录1.简介2.运行效果3.相关源码1.简介一个使用python PYQT5制作的关于pyinstall
阅读更多...
使用Python实现大文件切片上传及断点续传的方法

使用Python实现大文件切片上传及断点续传的方法

《使用Python实现大文件切片上传及断点续传的方法》本文介绍了使用Python实现大文件切片上传及断点续传的方法,包括功能模块划分（获取上传文件接口状态、临时文件夹状态信息、切片上传、切片合并）、整... 目录概要整体架构流程技术细节获取上传文件状态接口获取临时文件夹状态信息接口切片上传功能文件合并功能小
阅读更多...
python实现自动登录12306自动抢票功能

python实现自动登录12306自动抢票功能

《python实现自动登录12306自动抢票功能》随着互联网技术的发展,越来越多的人选择通过网络平台购票,特别是在中国,12306作为官方火车票预订平台,承担了巨大的访问量,对于热门线路或者节假日出行... 目录一、遇到的问题？二、改进三、进阶–展望总结一、遇到的问题？1.url-正确的表头：就是首先ur
阅读更多...
C#实现文件读写到SQLite数据库

C#实现文件读写到SQLite数据库

《C#实现文件读写到SQLite数据库》这篇文章主要为大家详细介绍了使用C#将文件读写到SQLite数据库的几种方法,文中的示例代码讲解详细,感兴趣的小伙伴可以参考一下... 目录1. 使用 BLOB 存储文件2. 存储文件路径3. 分块存储文件《文件读写到SQLite数据库China编程的方法》博客中，介绍了文
阅读更多...
Java汇编源码如何查看环境搭建

Java汇编源码如何查看环境搭建

《Java汇编源码如何查看环境搭建》：本文主要介绍如何在IntelliJIDEA开发环境中搭建字节码和汇编环境,以便更好地进行代码调优和JVM学习,首先,介绍了如何配置IntelliJIDEA以方... 目录一、简介二、在IDEA开发环境中搭建汇编环境2.1 在IDEA中搭建字节码查看环境2.1.1 搭建步
阅读更多...
Redis主从复制实现原理分析

Redis主从复制实现原理分析

《Redis主从复制实现原理分析》Redis主从复制通过Sync和CommandPropagate阶段实现数据同步,2.8版本后引入Psync指令,根据复制偏移量进行全量或部分同步,优化了数据传输效率... 目录Redis主DodMIK从复制实现原理实现原理Psync: 2.8版本后总结Redis主从复制实
阅读更多...
JAVA利用顺序表实现“杨辉三角”的思路及代码示例

JAVA利用顺序表实现“杨辉三角”的思路及代码示例

《JAVA利用顺序表实现“杨辉三角”的思路及代码示例》杨辉三角形是中国古代数学的杰出研究成果之一,是我国北宋数学家贾宪于1050年首先发现并使用的,：本文主要介绍JAVA利用顺序表实现杨辉三角的思... 目录一：“杨辉三角”题目链接二：题解代码：三：题解思路：总结一：“杨辉三角”题目链接题目链接：点击这里
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2