手撕红黑树（map和set底层结构）（2）

2024-04-23 14:52
文章标签 set 底层 结构 map 黑树 撕红

本文主要是介绍手撕红黑树（map和set底层结构）（2），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

@[TOC]红黑树

一 红黑树概念

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

简单来说红黑树通过了对颜色的控制进而对树的长度做出了限制，不再需要平衡因子。
红黑树性质

  1. 每个节点不是红色就是黑色
  2. 根节点为黑色
  3. 如果一个节点是红色，那么他的孩子节点就是黑色。没有连续的红色节点
  4. 对于每个节点，他的所以路径上的黑色节点的数量是相同的。
  5. 每个叶子节点都是黑色的（注意：这里的叶子节点指的是空节点）

红黑树通过这些性质保证了他的高度是合法的。
在这里插入图片描述
红黑树保证的是：最长路径不超过最短路径的两倍

二 红黑树的实现

2.1 红黑树的结构

enum Color
{Red,Black,
};template<class K, class V>
struct RBTreeNode
{RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Color _color;pair<K, V> _kv;RBTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _color(Red), _kv(kv){}
};
template<class K,class V>
class RBtree
{typedef RBTreeNode<K, V> Node;private:Node* _node=nullptr;
}

2.2 红黑树的插入

在这里插入图片描述
我们要注意：我们在插入新节点的时候，默认插入元素的颜色为红色，（黑色节点不好控制，因为要保证全部的路径的黑色节点数量是相同的，插入了一个黑色节点，就不能保证这一原则了）
然后插入元素对整棵树的影响我们就要从局部开始看，

  1. 如果插入元素的父亲为黑色那就不用在变化了；
  2. 插入元素的父亲为红色，此时就出翔了连续的红色节点，我们就要对这颗树进行处理；

我们对第二种情况分类讨论（用上述的图片为例）

第一种：cur为红，p为红，g为黑，u存在且为红

把p和u变为黑色，再把g变成红色；
到这里就要继续分类讨论：

  1. g为根节点，那就把g再变成黑色。
  2. 如果不是根节点，就把g=c，向上继续处理
    注意（p/u是g的左还是右都不影响，同样cur是p的左还是右也不影响）

第二种: cur为红，p为红，g为黑，u不存在/u存在且为黑
（i）u不存在在这里插入图片描述
这里cur一定是新插入的节点，如果cur不是新插入的节点，cur和p一定有一个是黑色的。
（ii）u存在且为黑色在这里插入图片描述
这里的cur就不是新插入的节点，u是黑色那么，每个路径下黑色节点数量一定相同，所以cur原本一定是黑色的，是因为新插入的原因被变成了红色。
以上这两个情况本质上是一种。
这里就要用到旋转，旋转和前面AVL树的旋转一模一样

p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反，
p为g的右孩子，cur为p的右孩子，则进行左单旋转
旋转完：p、g变色–p变黑，g变红。

参考下面的图，进一步理解
在这里插入图片描述
在这里插入图片描述
第三种 cur为红，p为红，g为黑，u不存在/u存在且为黑，但这里的左右位置不同

(i) p为g的左，cur为p的右
在这里插入图片描述
在这里插入图片描述
可以看到这里就变回了情况二，根据上面的我们再进行右单旋即可。
在这里插入图片描述
(i) p为g的右，cur为p的左

这个就是先右旋+左旋即可。这个图留个大家去完成。

2.3代码

bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);_root->_color = 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);//红色if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;while (parent && parent->_color == Red){Node* grandfather = parent->_parent;if (parent == grandfather->_left){Node* uncle = grandfather->_right;//情况一：存在且为红if (uncle && uncle->_color == Red){//变色parent->_color = Black;uncle->_color = Black;grandfather->_color = Red;//向上处理cur = grandfather;parent = cur->_parent;}//情况二：不存在or存在且为黑else{//旋转+变色//    g//  p    u//cif (cur == parent->_left){RotateR(grandfather);parent->_color = Black;grandfather->_color = Red;}else{//情况三//    g//  p    u//     c  RotateL(parent);RotateR(grandfather);cur->_color = Black;grandfather->_color = Red;}break;}}else//p是g的右孩子{Node* uncle = grandfather->_left;//情况一：存在且为红if (uncle && uncle->_color == Red){//变色parent->_color = Black;uncle->_color = Black;grandfather->_color = Red;//向上处理cur = grandfather;parent = cur->_parent;}//情况二：不存在or存在且为黑else{//旋转+变色//    g//  u   p//        cif (cur == parent->_right){RotateL(grandfather);parent->_color = Black;grandfather->_color = Red;}else{//情况三//    g//  u   p//     cRotateR(parent);RotateL(grandfather);cur->_color = Black;grandfather->_color = Red;}break;}}}_root->_color = Black;return true;}

三 检查函数

	bool Check(Node* cur, int BlackNum, int refBlackNum){if (cur == nullptr){if (BlackNum != refBlackNum){cout << "黑色节点的数量不匹配" << endl;return false;}elsereturn true;}if (cur->_color == Red && cur->_parent->_color == Red){cout << "出现了连续的红色节点" << endl;return false;}if (cur->_color == Black)++BlackNum;return Check(cur->_left, BlackNum, refBlackNum) &&Check(cur->_right, BlackNum, refBlackNum);}bool IsBalance(){if (_root == nullptr || _root->_color == Red)return false;//给一个基准值，和其他的黑色节点去比较int refBlackNum = 0;Node* cur = _root;while (cur){if (cur->_color == Black)++refBlackNum;cur = cur->_left;}return Check(_root, 0, refBlackNum);}

四 总结

总的来说红黑树的实现和AVL树非常像，他们就是兄弟，红黑树就是把考虑的因素从平衡因子转变成了颜色。

五 完整代码

#pragma once
#include<assert.h>
#include<vector>
enum Color
{Red,Black,
};template<class K, class V>
struct RBTreeNode
{RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Color _color;pair<K, V> _kv;RBTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _color(Red), _kv(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->_color = 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);//红色if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;while (parent && parent->_color == Red){Node* grandfather = parent->_parent;if (parent == grandfather->_left){Node* uncle = grandfather->_right;//情况一：存在且为红if (uncle && uncle->_color == Red){//变色parent->_color = Black;uncle->_color = Black;grandfather->_color = Red;//向上处理cur = grandfather;parent = cur->_parent;}//情况二：不存在or存在且为黑else{//旋转+变色//    g//  p    u//cif (cur == parent->_left){RotateR(grandfather);parent->_color = Black;grandfather->_color = Red;}else{//情况三//    g//  p    u//     c  RotateL(parent);RotateR(grandfather);cur->_color = Black;grandfather->_color = Red;}break;}}else//p是g的右孩子{Node* uncle = grandfather->_left;//情况一：存在且为红if (uncle && uncle->_color == Red){//变色parent->_color = Black;uncle->_color = Black;grandfather->_color = Red;//向上处理cur = grandfather;parent = cur->_parent;}//情况二：不存在or存在且为黑else{//旋转+变色//    g//  u   p//        cif (cur == parent->_right){RotateL(grandfather);parent->_color = Black;grandfather->_color = Red;}else{//情况三//    g//  u   p//     cRotateR(parent);RotateL(grandfather);cur->_color = Black;grandfather->_color = Red;}break;}}}_root->_color = Black;return true;}void RotateL(Node* parent){//++rotateSize;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;subR->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subR;}else{ppnode->_right = subR;}subR->_parent = ppnode;}}void RotateR(Node* parent){//++rotateSize;Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;Node* ppnode = parent->_parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subL;}else{ppnode->_right = subL;}subL->_parent = ppnode;}}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << endl;_InOrder(root->_right);}void InOrder(){_InOrder(_root);}/////检查函数bool Check(Node* cur, int BlackNum, int refBlackNum){if (cur == nullptr){if (BlackNum != refBlackNum){cout << "黑色节点的数量不匹配" << endl;return false;}elsereturn true;}if (cur->_color == Red && cur->_parent->_color == Red){cout << "出现了连续的红色节点" << endl;return false;}if (cur->_color == Black)++BlackNum;return Check(cur->_left, BlackNum, refBlackNum) &&Check(cur->_right, BlackNum, refBlackNum);}bool IsBalance(){if (_root == nullptr || _root->_color == Red)return false;//给一个基准值，和其他的黑色节点去比较int refBlackNum = 0;Node* cur = _root;while (cur){if (cur->_color == Black)++refBlackNum;cur = cur->_left;}return Check(_root, 0, refBlackNum);}
private:Node* _root = nullptr;
};void TestRBTree1()
{//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };int a[] = { 4, 2, 6, 1, 14,16};RBTree<int, int> t;for (auto e : a){if (e == 16){int x = 0;}t.Insert(make_pair(e, e));// 1、先看是插入谁导致出现的问题// 2、打条件断点，画出插入前的树// 3、单步跟踪，对比图一一分析细节原因cout << e << "->" << t.IsBalance() << endl;}t.InOrder();cout << t.IsBalance() << endl;
}

这篇关于手撕红黑树（map和set底层结构）（2）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


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

相关文章

Vite 打包目录结构自定义配置小结

Vite 打包目录结构自定义配置小结

《Vite打包目录结构自定义配置小结》在Vite工程开发中,默认打包后的dist目录资源常集中在asset目录下,不利于资源管理,本文基于Rollup配置原理,本文就来介绍一下通过Vite配置自定义... 目录一、实现原理二、具体配置步骤1. 基础配置文件2. 配置说明（1）js 资源分离（2）非 JS 资
阅读更多...
深入解析C++ 中std::map内存管理

深入解析C++ 中std::map内存管理

《深入解析C++中std::map内存管理》文章详解C++std::map内存管理,指出clear()仅删除元素可能不释放底层内存,建议用swap()与空map交换以彻底释放,针对指针类型需手动de... 目录1️、基本清空std::map2️、使用 swap 彻底释放内存3️、map 中存储指针类型的对象
阅读更多...
C++ STL-string类底层实现过程

C++ STL-string类底层实现过程

《C++STL-string类底层实现过程》本文实现了一个简易的string类,涵盖动态数组存储、深拷贝机制、迭代器支持、容量调整、字符串修改、运算符重载等功能,模拟标准string核心特性,重点强... 目录实现框架一、默认成员函数1.默认构造函数2.构造函数3.拷贝构造函数(重点)4.赋值运算符重载函数
阅读更多...
Java集合中的链表与结构详解

Java集合中的链表与结构详解

《Java集合中的链表与结构详解》链表是一种物理存储结构上非连续的存储结构,数据元素的逻辑顺序的通过链表中的引用链接次序实现,文章对比ArrayList与LinkedList的结构差异,详细讲解了链表... 目录一、链表概念与结构二、当向单链表的实现2.1 准备工作2.2 初始化链表2.3 打印数据、链表长
阅读更多...
Redis分布式锁中Redission底层实现方式

Redis分布式锁中Redission底层实现方式

《Redis分布式锁中Redission底层实现方式》Redission基于Redis原子操作和Lua脚本实现分布式锁,通过SETNX命令、看门狗续期、可重入机制及异常处理,确保锁的可靠性和一致性,是... 目录Redis分布式锁中Redission底层实现一、Redission分布式锁的基本使用二、Red
阅读更多...
创建springBoot模块没有目录结构的解决方案

创建springBoot模块没有目录结构的解决方案

《创建springBoot模块没有目录结构的解决方案》2023版IntelliJIDEA创建模块时可能出现目录结构识别错误,导致文件显示异常,解决方法为选择模块后点击确认,重新校准项目结构设置,确保源... 目录创建spChina编程ringBoot模块没有目录结构解决方案总结创建springBoot模块没有目录
阅读更多...
SpringBoot利用树形结构优化查询速度

SpringBoot利用树形结构优化查询速度

《SpringBoot利用树形结构优化查询速度》这篇文章主要为大家详细介绍了SpringBoot利用树形结构优化查询速度,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一个真实的性能灾难传统方案为什么这么慢N+1查询灾难性能测试数据对比核心解决方案：一次查询 + O(n)算法解决
阅读更多...
Oracle查询表结构建表语句索引等方式

Oracle查询表结构建表语句索引等方式

《Oracle查询表结构建表语句索引等方式》使用USER_TAB_COLUMNS查询表结构可避免系统隐藏字段（如LISTUSER的CLOB与VARCHAR2同名字段）,这些字段可能为dbms_lob.... 目录oracle查询表结构建表语句索引1.用“USER_TAB_COLUMNS”查询表结构2.用“a
阅读更多...
在MySQL中实现冷热数据分离的方法及使用场景底层原理解析

在MySQL中实现冷热数据分离的方法及使用场景底层原理解析

《在MySQL中实现冷热数据分离的方法及使用场景底层原理解析》MySQL冷热数据分离通过分表/分区策略、数据归档和索引优化,将频繁访问的热数据与冷数据分开存储,提升查询效率并降低存储成本,适用于高并发... 目录实现冷热数据分离1. 分表策略2. 使用分区表3. 数据归档与迁移在mysql中实现冷热数据分
阅读更多...
Kotlin Map映射转换问题小结

Kotlin Map映射转换问题小结

《KotlinMap映射转换问题小结》文章介绍了Kotlin集合转换的多种方法,包括map（一对一转换）、mapIndexed（带索引）、mapNotNull（过滤null）、mapKeys/map... 目录Kotlin 集合转换：map、mapIndexed、mapNotNull、mapKeys、map
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2