手撕红黑树（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。

相关文章

使用Java实现通用树形结构构建工具类

使用Java实现通用树形结构构建工具类

《使用Java实现通用树形结构构建工具类》这篇文章主要为大家详细介绍了如何使用Java实现通用树形结构构建工具类,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录完整代码一、设计思想与核心功能二、核心实现原理1. 数据结构准备阶段2. 循环依赖检测算法3. 树形结构构建4. 搜索子
阅读更多...
利用Python开发Markdown表格结构转换为Excel工具

利用Python开发Markdown表格结构转换为Excel工具

《利用Python开发Markdown表格结构转换为Excel工具》在数据管理和文档编写过程中,我们经常使用Markdown来记录表格数据,但它没有Excel使用方便,所以本文将使用Python编写一... 目录1.完整代码2. 项目概述3. 代码解析3.1 依赖库3.2 GUI 设计3.3 解析 Mark
阅读更多...
SpringBoot如何通过Map实现策略模式

SpringBoot如何通过Map实现策略模式

《SpringBoot如何通过Map实现策略模式》策略模式是一种行为设计模式,它允许在运行时选择算法的行为,在Spring框架中,我们可以利用@Resource注解和Map集合来优雅地实现策略模式,这... 目录前言底层机制解析Spring的集合类型自动装配@Resource注解的行为实现原理使用直接使用M
阅读更多...
Nginx指令add_header和proxy_set_header的区别及说明

Nginx指令add_header和proxy_set_header的区别及说明

《Nginx指令add_header和proxy_set_header的区别及说明》：本文主要介绍Nginx指令add_header和proxy_set_header的区别及说明,具有很好的参考价... 目录Nginx指令add_header和proxy_set_header区别如何理解反向代理？proxy
阅读更多...
C++ 各种map特点对比分析

C++ 各种map特点对比分析

《C++各种map特点对比分析》文章比较了C++中不同类型的map（如std::map,std::unordered_map,std::multimap,std::unordered_multima... 目录特点比较C++ 示例代码 ​​​​​​代码解释特点比较1. std::map底层实现：基于红黑
阅读更多...
Java的volatile和sychronized底层实现原理解析

Java的volatile和sychronized底层实现原理解析

《Java的volatile和sychronized底层实现原理解析》文章详细介绍了Java中的synchronized和volatile关键字的底层实现原理,包括字节码层面、JVM层面的实现细节,以... 目录1. 概览2. Synchronized2.1 字节码层面2.2 JVM层面2.2.1 ente
阅读更多...
JavaScript中的Map用法完全指南

JavaScript中的Map用法完全指南

《JavaScript中的Map用法完全指南》：本文主要介绍JavaScript中Map用法的相关资料,通过实例讲解了Map的创建、常用方法和迭代方式,还探讨了Map与对象的区别,并通过一个例子展... 目录引言1. 创建 Map2. Map 和对象的对比3. Map 的常用方法3.1 set(key, v
阅读更多...
MySQL中Next-Key Lock底层原理实现

MySQL中Next-Key Lock底层原理实现

《MySQL中Next-KeyLock底层原理实现》Next-KeyLock是MySQLInnoDB存储引擎中的一种锁机制,结合记录锁和间隙锁,用于高效并发控制并避免幻读,本文主要介绍了MySQL中... 目录一、Next-Key Lock 的定义与作用二、底层原理三、源代码解析四、总结Next-Key L
阅读更多...
Golang中map缩容的实现

Golang中map缩容的实现

《Golang中map缩容的实现》本文主要介绍了Go语言中map的扩缩容机制,包括grow和hashGrow方法的处理,具有一定的参考价值,感兴趣的可以了解一下... 目录基本分析带来的隐患为什么不支持缩容基本分析在 Go 底层源码 src/runtime/map.go 中，扩缩容的处理方法是 grow
阅读更多...
mysql通过frm和ibd文件恢复表_mysql5.7根据.frm和.ibd文件恢复表结构和数据

mysql通过frm和ibd文件恢复表_mysql5.7根据.frm和.ibd文件恢复表结构和数据

《mysql通过frm和ibd文件恢复表_mysql5.7根据.frm和.ibd文件恢复表结构和数据》文章主要介绍了如何从.frm和.ibd文件恢复MySQLInnoDB表结构和数据,需要的朋友可以参... 目录一、恢复表结构二、恢复表数据补充方法一、恢复表结构（从 .frm 文件）方法 1：使用 mysq
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2