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

相关文章

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心： 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数，若返回值为正，qsort 函数判定a>b ；为负，a<b；为0，a==b； int milkcmp(const void *va,c
阅读更多...
poj 3050 dfs + set的妙用

poj 3050 dfs + set的妙用

题意: 给一个5x5的矩阵，求由多少个由连续6个元素组成的不一样的字符的个数。 解析： dfs + set去重搞定。 代码： #include <iostream>#include <cstdio>#include <set>#include <cstdlib>#include <algorithm>#include <cstring>#include <cm
阅读更多...
自定义类型：结构体(续)

自定义类型：结构体(续)

目录 一. 结构体的内存对齐 1.1 为什么存在内存对齐？ 1.2 修改默认对齐数 二. 结构体传参 三. 结构体实现位段 一. 结构体的内存对齐 在前面的文章里我们已经讲过一部分的内存对齐的知识，并举出了两个例子，我们再举出两个例子继续说明： struct S3{double a;int b;char c;};int mian(){printf("%zd\n",s
阅读更多...
【编程底层思考】垃圾收集机制，GC算法，垃圾收集器类型概述

【编程底层思考】垃圾收集机制，GC算法，垃圾收集器类型概述

Java的垃圾收集（Garbage Collection，GC）机制是Java语言的一大特色，它负责自动管理内存的回收，释放不再使用的对象所占用的内存。以下是对Java垃圾收集机制的详细介绍： 一、垃圾收集机制概述： 对象存活判断：垃圾收集器定期检查堆内存中的对象，判断哪些对象是“垃圾”，即不再被任何引用链直接或间接引用的对象。内存回收：将判断为垃圾的对象占用的内存进行回收，以便重新使用。
阅读更多...
Collection List Set Map的区别和联系

Collection List Set Map的区别和联系

Collection List Set Map的区别和联系 这些都代表了Java中的集合，这里主要从其元素是否有序，是否可重复来进行区别记忆，以便恰当地使用，当然还存在同步方面的差异，见上一篇相关文章。 有序否 允许元素重复否 Collection 否 是 List 是 是 Set AbstractSet 否
阅读更多...
哈希表的底层实现(1)---C++版

哈希表的底层实现(1)---C++版

目录 哈希表的基本原理 哈希表的优点 哈希表的缺点 应用场景 闭散列法 开散列法 开放定值法Open Addressing——线性探测的模拟实现 超大重点部分评析 链地址法Separate Chaining——哈希桶的模拟实现 哈希表（Hash Table）是一种数据结构，它通过将键（Key）映射到值（Value）的方式来实现快速的数据存储与查找。哈希表的核心概念是哈希
阅读更多...
OpenCV结构分析与形状描述符（11）椭圆拟合函数fitEllipse()的使用

OpenCV结构分析与形状描述符（11）椭圆拟合函数fitEllipse()的使用

操作系统：ubuntu22.04 OpenCV版本：OpenCV4.9 IDE:Visual Studio Code 编程语言：C++11 算法描述 围绕一组2D点拟合一个椭圆。 该函数计算出一个椭圆，该椭圆在最小二乘意义上最好地拟合一组2D点。它返回一个内切椭圆的旋转矩形。使用了由[90]描述的第一个算法。开发者应该注意，由于数据点靠近包含的 Mat 元素的边界，返回的椭圆/旋转矩形数据
阅读更多...
论文翻译：ICLR-2024 PROVING TEST SET CONTAMINATION IN BLACK BOX LANGUAGE MODELS

论文翻译：ICLR-2024 PROVING TEST SET CONTAMINATION IN BLACK BOX LANGUAGE MODELS

PROVING TEST SET CONTAMINATION IN BLACK BOX LANGUAGE MODELS https://openreview.net/forum?id=KS8mIvetg2 验证测试集污染在黑盒语言模型中 文章目录 验证测试集污染在黑盒语言模型中摘要1 引言 摘要 大型语言模型是在大量互联网数据上训练的，这引发了人们的担忧和猜测，即它们可能已
阅读更多...
多路转接之select(fd_set介绍,参数详细介绍),实现非阻塞式网络通信

多路转接之select(fd_set介绍,参数详细介绍),实现非阻塞式网络通信

目录 多路转接之select 引入 介绍 fd_set 函数原型 nfds readfds / writefds / exceptfds readfds  总结  fd_set操作接口  timeout timevalue 结构体 传入值 返回值 代码 注意点 -- 调用函数 select的参数填充  获取新连接 注意点 -- 通信时的调用函数 添加新fd到
阅读更多...
TL-Tomcat中长连接的底层源码原理实现

TL-Tomcat中长连接的底层源码原理实现

长连接：浏览器告诉tomcat不要将请求关掉。  如果不是长连接，tomcat响应后会告诉浏览器把这个连接关掉。    tomcat中有一个缓冲区  如果发送大批量数据后 又不处理  那么会堆积缓冲区 后面的请求会越来越慢。
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2