[C++随笔录] 红黑树

红黑树

  • 红黑树的特点
  • 红黑树的模拟实现
    • 红黑树的底层结构
    • insert的实现
      • 实现思路
      • 更新黑红比例的逻辑
      • insert的完整代码
    • insert的验证
  • 源码

红黑树的特点

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

  • 红黑树的特点:

    1. 节点颜色不是红色就是黑色
    2. 根节点是黑色的
    3. 每一条路径的黑色节点数目是相同的, (注意: 这里的路径是从根节点到NIL(黑色)节点)
    4. 每一条路径不允许出现连续的红色节点
  • 路径是从根节点 到 NIL节点的

🗨️满足上面的条件, 为啥就能保证 红黑树确保没有一条路径会比其他路径长出俩倍呢?

  • 根据上述的特点, 我们可以得知:
    每条路径的黑色节点数目一定的情况下 , 最短路径是 全黑, 最长路径是 黑红相间的
    如果我们保证 最长路径 不超过 最短路径的二倍就可以了

红黑树的模拟实现

红黑树的底层结构

  1. 颜色类型
// 枚举
enum Color
{RED,BLACK
};
  1. RBTreeNode类
template<class K, class V>
struct RBTreeNode
{
public:RBTreeNode(const pair<K, V> kv):_kv(kv){}public:pair<K, V> _kv;Color _color = BLACK;RBTreeNode<K, V>* _left = nullptr;RBTreeNode<K, V>* _right = nullptr;RBTreeNode<K, V>* _parent = nullptr;
};
  1. RBTree类
template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;public:RBTree(){}private:// 根节点Node*  _root = nullptr;// 记录旋转次数int RotateCount =  0;
}

insert的实现

实现思路

二叉搜索树的插入逻辑 + 更新黑红比例

bool Insert(const pair<K, V> kv)
{if (_root == nullptr){// 根节点是黑色的_root = new Node(kv);_root->_color = BLACK;return true;}Node* parent = _root;Node* cur = _root;while (cur){if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else{return false;}}// 新建一个节点, 默认是红色cur = new Node(kv);cur->_color = RED;// 链接cur 和 parentif (cur->_kv.first > parent->_kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;// 更改黑红比例// ...// ...// 更新完黑红比例后, 就返回truereturn true;
}

🗨️ 不能出现连续的红色节点 ⇒ 我们插入节点给个黑色节点多好, 为啥还要给红色节点冒风险呢?


因为, 我们插入的节点颜色是 红色, 插入的位置就有两种可能:

  1. 插入到黑色节点的后面 — — 正常的情况, 不需要进行更新
  2. 插入到红色节点的后面 — — 出现连续的红色节点, 需要 更新这一条支路 (当前节点到祖宗节点这一条路径)中的黑红比例

更新黑红比例的逻辑

由于 插入前, 是符合红黑树的性质,
插入的节点是红色 ⇒ 插入后才会出现连续的红色节点

⇒ 设插入的新节点为 cur(红色) ,
则父亲节点 paren红色, 祖父节点 grandfather黑色 ⇒ 这才符合 插入前符合红黑树的特点, 插入后才会出现连续的红色节点的情况

其实, 更新 当前节点到 祖宗节点这一条路径的 黑红比例 的本质是 看uncle的情况
首先, 要确定 uncle 位于grandfather的哪一侧 && uncle不一定存在, 但parent一定存在
要确定parent 位于 grandfather的那一侧:

  1. parent 位于 grandfather的左侧
  2. parent 位于 grandfather的右侧

其次, 才是 uncle 的存在情况 以及 颜色情况


  1. uncle存在且为红

  2. uncle不存在
    如果 uncle不存在 ⇒ cur为新增节点

  • 如果cur不是新增节点, 那么 parent后面的节点必定是黑色的, 那么就违反了 每一条路径的黑色节点的个数是相同

  1. uncle存在且为黑

    如果uncle存在, 那么必定是 黑色 ⇒ 那么 cur 也应该是 黑色.
    现在看到的cur 是红色的, 是由下面的更新上来的


通过上面的图示, 我们得出 : 插入时, uncle主要分为两种情况

  1. uncle存在且为红 — — 由于更新后的头结点为红 ⇒ 我们需要继续向上更新下去
  2. uncle不存在 或 uncle存在且为黑 — — 由于更新后的头结点为黑 ⇒ 我们不需要继续向上更新下去

insert的完整代码

bool Insert(const pair<K, V> kv)
{if (_root == nullptr){// 根节点是黑色的_root = new Node(kv);_root->_color = BLACK;return true;}Node* parent = _root;Node* cur = _root;while (cur){if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else{return false;}}// 新建一个节点, 默认是红色cur = new Node(kv);cur->_color = RED;// 链接cur 和 parentif (cur->_kv.first > parent->_kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;// 更改黑红比例// 父亲节点存在且为红, 才有机会继续向上更新下去while (parent && parent->_color == RED){Node* grandfather = parent->_parent;// parent 为 grandfather的左侧if (grandfather->_left == parent){Node* uncle = grandfather->_right;// u存在且为红if (uncle && uncle->_color == RED){// 颜色变化grandfather->_color = RED;parent->_color = uncle->_color = BLACK;// 继续向上调整cur = grandfather;parent = cur->_parent;}else // u不存在 或 u存在且为黑色{if (cur == parent->_left){RotateR(grandfather);grandfather->_color = RED;parent->_color = BLACK;}else{RotateL(parent);RotateR(grandfather);cur->_color = BLACK;grandfather->_color = RED;}// 更新后的头节点为黑色, 不需要继续向上更新break;}}// parent 为 grandfather的右侧else if (grandfather->_right == parent){Node* uncle = grandfather->_left;// u存在且为红if (uncle && uncle->_color == RED){// 颜色变化grandfather->_color = RED;uncle->_color = parent->_color = BLACK;// 继续向上调整cur = grandfather;parent = cur->_parent;}// u不存在 或 u存在且为黑色else{if (parent->_right == cur){RotateL(grandfather);parent->_color = BLACK;grandfather->_color = RED;}else{RotateR(parent);RotateL(grandfather);cur->_color = BLACK;grandfather->_color = RED;}// 更新后的头节点为黑色, 不需要继续向上更新break;}}else{assert("黑红比例失控!");}}// 有可能更新过程中会把 root更新为红色 // && root节点的颜色必须为黑色// -->暴力统一处理根节点的颜色_root->_color = BLACK;return true;
}

insert的验证

  1. 每一条路径的 黑节点个数相同 先找一个 基准值(root的左子树中 黑节点的个数)
    如果后面的路径中 有的黑节点的个数 跟 基准值不同, 那就返回false.
  2. 不能有连续的红节点 ⇒ 当前节点为红节点, 那么父亲节点不能为红节点
  3. root 节点的颜色要为 黑色

验证代码

// 外面调用接口
bool IsBalance()
{return IsBalance(_root);
}bool IsBalance(Node* root)
{if (root == nullptr)return true;// root节点为红, 就直接返回falseif (root->_color != BLACK){return false;}// 基准值 -- root左子树中的黑节点个数int benchmark = 0;Node* cur = _root;while (cur){if (cur->_color == BLACK)++benchmark;cur = cur->_left;}// 检查每条路径中黑节点个数 && 不能出现连续的红节点return CheckColour(root, 0, benchmark);
}bool CheckColour(Node* root, int blacknum, int benchmark)
{// 到叶子节点, 比较路径中黑节点的个数 和 基准值if (root == nullptr){if (blacknum != benchmark)return false;return true;}if (root->_color == BLACK){++blacknum;}// 不能存在连续的红节点if (root->_color == RED && root->_parent && root->_parent->_color == RED){cout << root->_kv.first << "出现连续红色节点" << endl;return false;}return CheckColour(root->_left, blacknum, benchmark)&& CheckColour(root->_right, blacknum, benchmark);
}

Height

// 外面调用接口
int Height()
{return Height(_root);
}int Height(Node* root)
{if (root == nullptr)return 0;int left = Height(root->_left);int right = Height(root->_right);return left > right ? left + 1 : right + 1;
}

GetRotateCount

int GetRoateCount()
{return RotateCount;
}

测试程序

void rbt_test()
{const int N = 10000000;vector<int> v;v.reserve(N);srand((unsigned int)time(NULL));for (size_t i = 0; i < N; i++){int ret = rand();v.push_back(ret);// v.push_back(i);}muyu::RBTree<int, int> rbt;for (auto e : v){rbt.Insert(make_pair(e, e));// cout << "Insert:" << e << "->" << avl.Isbalance() << endl;}cout << "红黑树是否达标-> " << rbt.IsBalance() << endl;cout << "红黑树的高度-> " << rbt.Height() << endl;cout << "红黑树旋转的次数-> " << rbt.GetRoateCount() << endl;
}int main()
{rbt_test();return 0;
}

运行结果:

红黑树是否达标-> 1
红黑树的高度-> 19
红黑树旋转的次数-> 19119

源码

#pragma once#include<iostream>using namespace std;namespace muyu
{// 枚举enum Color{RED,BLACK};template<class K, class V>struct RBTreeNode{public:RBTreeNode(const pair<K, V> kv):_kv(kv){}public:pair<K, V> _kv;Color _color = BLACK;RBTreeNode<K, V>* _left = nullptr;RBTreeNode<K, V>* _right = nullptr;RBTreeNode<K, V>* _parent = nullptr;};template<class K, class V>class RBTree{typedef RBTreeNode<K, V> Node;public:RBTree(){}void RotateL(Node* parent){++RotateCount;Node* cur = parent->_right;Node* grandfather = parent->_parent;Node* curleft = cur->_left;// 旋转核心parent->_right = curleft;cur->_left = parent;// 更新父亲// 1. parent && curleftif (curleft){curleft->_parent = parent;}parent->_parent = cur;// 2.更新curif (grandfather == nullptr){cur->_parent = nullptr;_root = cur;}else{if (grandfather->_left == parent){grandfather->_left = cur;}else{grandfather->_right = cur;}cur->_parent = grandfather;}}void RotateR(Node* parent){++RotateCount;Node* cur = parent->_left;Node* grandfather = parent->_parent;Node* curright = cur->_right;// 旋转核心parent->_left = curright;cur->_right = parent;// 更新链接关系// 1. parent && currightif (curright){curright->_parent = parent;}parent->_parent = cur;// 2.更新curif (grandfather == nullptr){cur->_parent = nullptr;_root = cur;}else{if (grandfather->_left == parent){grandfather->_left = cur;}else{grandfather->_right = cur;}cur->_parent = grandfather;}}bool Insert(const pair<K, V> kv){if (_root == nullptr){// 根节点是黑色的_root = new Node(kv);_root->_color = BLACK;return true;}Node* parent = _root;Node* cur = _root;while (cur){if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else{return false;}}// 新建一个节点, 默认是红色cur = new Node(kv);cur->_color = RED;// 链接cur 和 parentif (cur->_kv.first > parent->_kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;// 更改黑红比例while (parent && parent->_color == RED){Node* grandfather = parent->_parent;if (grandfather->_left == parent){Node* uncle = grandfather->_right;// u存在且为红if (uncle && uncle->_color == RED){// 颜色变化grandfather->_color = RED;parent->_color = uncle->_color = BLACK;// 继续向上调整cur = grandfather;parent = cur->_parent;}else // u不存在 或 u存在且为黑色{if (cur == parent->_left){RotateR(grandfather);grandfather->_color = RED;parent->_color = BLACK;}else{RotateL(parent);RotateR(grandfather);cur->_color = BLACK;grandfather->_color = RED;}break;}}else if (grandfather->_right == parent){Node* uncle = grandfather->_left;// u存在且为红if (uncle && uncle->_color == RED){// 颜色变化grandfather->_color = RED;uncle->_color = parent->_color = BLACK;// 继续向上调整cur = grandfather;parent = cur->_parent;}// u不存在 或 u存在且为黑色else{if (parent->_right == cur){RotateL(grandfather);parent->_color = BLACK;grandfather->_color = RED;}else{RotateR(parent);RotateL(grandfather);cur->_color = BLACK;grandfather->_color = RED;}break;}}else{assert("黑红比例失控!");}}// 暴力统一处理根节点的颜色_root->_color = BLACK;return true;}int Height(){return Height(_root);}int Height(Node* root){if (root == nullptr)return 0;int left = Height(root->_left);int right = Height(root->_right);return left > right ? left + 1 : right + 1;}bool CheckColour(Node* root, int blacknum, int benchmark){if (root == nullptr){if (blacknum != benchmark)return false;return true;}if (root->_color == BLACK){++blacknum;}if (root->_color == RED && root->_parent && root->_parent->_color == RED){cout << root->_kv.first << "出现连续红色节点" << endl;return false;}return CheckColour(root->_left, blacknum, benchmark)&& CheckColour(root->_right, blacknum, benchmark);}bool IsBalance(){return IsBalance(_root);}bool IsBalance(Node* root){if (root == nullptr)return true;if (root->_color != BLACK){return false;}// 基准值int benchmark = 0;Node* cur = _root;while (cur){if (cur->_color == BLACK)++benchmark;cur = cur->_left;}return CheckColour(root, 0, benchmark);}int GetRoateCount(){return RotateCount;}private:Node* _root = nullptr;int RotateCount = 0;};
}

十年磨一剑,霜刃未曾试。
今日把示君,谁有不平事。
— — 贾岛《剑客》

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

FPGA与STM32_FSMC总线通信实验

FPGA与STM32_FSMC总线通信实验 内部存储器IP核的参数设置创建IP核FPGA代码STM32标准库的程序 STM32F407 上自带 FSMC 控制器&#xff0c;通过 FSMC 总线的地址复用模式实现STM32 与 FPGA 之间的通信&#xff0c;FPGA 内部建立 RAM 块&#xff0c;FPGA 桥接 STM32 和 RAM 块&…

机器学习 - 决策树:技术全解与案例实战

目录 一、引言二、决策树基础决策树模型概述构建决策树的关键概念特征选择决策树的生成 决策树的剪枝 三、算法研究进阶提升树和随机森林提升树&#xff08;Boosted Trees&#xff09;随机森林&#xff08;Random Forests&#xff09; 进化算法与决策树决策树结构的进化 多目标…

【图论实战】 Boost学习 03:dijkstra_shortest_paths

文章目录 示例代码 示例 最短路径: A -> C -> D -> F -> E -> G 长度 16 代码 #include <iostream> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/dijkstra_shortest_paths.hpp> #include <boost/graph/graphviz.h…

rust实现quic服务端和客户端

演示如何使用 Quinn 库实现一个简单的 QUIC 客户端和服务器。QUIC 是一种基于 UDP 的协议&#xff0c;用于在互联网上进行快速和安全的通信。 在程序中&#xff0c;使用了 Rust 的标准库中的 error、net 和 sync 模块&#xff0c;以及第三方库 tokio 和 quinn。程序使用了 asy…

[工业自动化-10]:西门子S7-15xxx编程 - PLC主站 - 信号量:数字量

目录 前言&#xff1a; 一、工业现场常见信号的分类 二、IO数字量模块 2.1 概述 2.2 PLC的数字量是24V还是5V电压&#xff1f; 2.2 数字量模块的安装与接线 2.3 数字量模的注意事项 前言&#xff1a; 一、工业现场常见信号的分类 在工业自动化领域&#xff0c;常常需要使…

操作系统 | 编写内核

&#x1f308;个人主页&#xff1a;Sarapines Programmer&#x1f525; 系列专栏&#xff1a;《操作系统实验室》&#x1f516;少年有梦不应止于心动&#xff0c;更要付诸行动。 目录结构 1. 操作系统实验之编写内核 1.1 实验目的 1.2 实验内容 1.3 实验步骤 1.4 实验过程 …

VScode + opencv(cmake编译) + c++ + win配置教程

1、下载opencv 2、下载CMake 3、下载MinGW 放到一个文件夹中 并解压另外两个文件 4、cmake编译opencv 新建文件夹mingw-build 双击cmake-gui 程序会开始自动生成Makefiles等文件配置&#xff0c;需要耐心等待一段时间。 简单总结下&#xff1a;finish->configuring …

轻量日志管理方案-[EFK]

使用FileBeat进行日志文件的数据收集&#xff0c;并发送到ES进行存储&#xff0c;最后Kibana进行查看展示&#xff1b; 这个应该是最简单&#xff0c;轻量的日志收集方案了。 最总方案为&#xff1a;FileBeatESKibana ; 【Kibana过于强大&#xff0c;感觉可以无限扩展】 文章目…

边缘计算多角色智能计量插座:用电监测和资产管理的未来智能化引擎

目前主流的智能插座涵盖了红外遥控&#xff08;控制空调和电视等带有红外标准的电器&#xff09;&#xff0c;配备着测温、测湿等仓库应用场景&#xff0c;配备了人体红外或者毫米波雷达作为联动控制&#xff0c;但是大家有没有思考一个问题&#xff0c;就是随着对接的深入&…

django|报错SQLite 3.8.3 or later is required的解决方案

迁移原同事写的程序&#xff0c;到新服务器上边。运行报错。解决方案有三种 降低django版本升级sqlite3&#xff0c;不低于3.8.3版本修改django源码 方案一、降低django版本 卸载高版本django pip uninstall django安装低版本&#xff0c;如 pip install django2.1.7注意&…

汽车标定技术(八)--MPC57xx是如何支持标定的页切换

目录 1.页切换的概念 1.1 标定常量的理解 1.2 页切换 2.MPC57xx的Overlay模块 3.小结 1.页切换的概念 在汽车标定测量中&#xff0c;有一个概念我想很多人都听过&#xff0c;但是实际上在项目里没有用到过&#xff0c;那就是今天要讲的页切换概念。在讲页切换的时候&#…

python注释(快捷键)

首先介绍以下三种注释方式&#xff1a; # 123&#xff08;单行注释&#xff09; """123"""&#xff08;多行注释&#xff09; 123&#xff08;多行注释&#xff09; 下面介绍一下快捷键&#xff1a; Ctrl/ 注释单行&#xff1a;指针只要在这行代…

Arcgis连接Postgis数据库(Postgre入门十)

效果 步骤 1、矢量数据首先有在postgis数据库中 这个postgis数据库中的一个空间数据&#xff0c;数据库名称是test3&#xff0c;数据表名称是test 2、Arcgis中连接postgis数据库中 3、成功连接 可以将数据拷贝或导入到gdb数据库中

图数据库Neo4j详解

文章目录 第一章 图和Neo4j1.1 图数据库概念1.1.1 图论起源1.1.2 节点-关系及图1.1.3 图数据库1.1.4 图数据库分类1.1.4 图数据库应用场景1.1.5 与关系型数据库对比1.1.6 图数据库优势 1.2 Neo4j介绍1.2.1 Neo4j是什么1.2.2 Neo4j特点1.2.3 Neo4j的优势1.2.4 Neo4j的限制1.2.5 …

机器学习——实践

目录 一、数据集划分 1、交叉验证 2、不平衡数据的处理 代价敏感学习 二、评价指标 三、正则化、偏差和方差 为什么要标准化/归一化&#xff1f; 过拟合的处理——Dropout 过拟合的处理——Early stopping 过拟合的处理——数据增强 偏差和方差 ​编辑 一、数据集划分…

机器学习——奇异值分解案例(图片压缩-代码简洁版)

本想大迈步进入前馈神经网络 但是…唉…瞅了几眼&#xff0c;头晕 然后想到之前梳理的奇异值分解、主成分分析、CBOW都没有实战 如果没有实际操作&#xff0c;会有一种浮在云端的虚无感 但是如果要实际操作&#xff0c;我又不想直接调用库包 可是…如果不直接调包&#xff0c;感…

【计算机网络笔记】Internet网络的网络层——IP协议之IP数据报的结构

系列文章目录 什么是计算机网络&#xff1f; 什么是网络协议&#xff1f; 计算机网络的结构 数据交换之电路交换 数据交换之报文交换和分组交换 分组交换 vs 电路交换 计算机网络性能&#xff08;1&#xff09;——速率、带宽、延迟 计算机网络性能&#xff08;2&#xff09;…

Pytorch实战教程(一)-神经网络与模型训练

0. 前言 人工神经网络 (Artificial Neural Network, ANN) 是一种监督学习算法,其灵感来自人类大脑的运作方式。类似于人脑中神经元连接和激活的方式,神经网络接受输入,通过某些函数在网络中进行传递,导致某些后续神经元被激活,从而产生输出。函数越复杂,网络对于输入的数…

离线视频ocr识别

sudo apt-get install libleptonica-dev libtesseract-dev sudo apt-get install tesseract-ocr-chi-sim python -m pip install video-ocrwindows安装方法&#xff1a; 下载安装 https://digi.bib.uni-mannheim.de/tesseract/tesseract-ocr-w64-setup-5.3.3.20231005.exe 下…

百度智能云千帆大模型平台再升级,SDK版本开源发布!

文章目录 1. SDK的优势2. 千帆SDK&#xff1a;快速落地LLM应用3. 如何快速上手千帆SDK3.1 SDK快速启动3.2 SDK进阶指引3.3 通过Langchain接入千帆SDK 4. 开源社区 百度智能云千帆大模型平台再次升级&#xff01;在原有API基础上&#xff0c;百度智能云正式上线Python SDK&#…