佛山做网站建设/中国十大搜索引擎排名
1.红黑树的概念
红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或 Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路 径会比其他路径长出俩倍,因而是接近平衡的。
2.红黑树的性质!!!!!
1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的,则它的两个孩子结点是黑色的
4. 对于每个结点,从该结点到其所有后代叶结点的简单路径上,均 包含相同数目的黑色结点
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
3.红黑树节点的定义
enum color
{RED,BLACK
}; //列举color的各种可能情况template<class K, class V>
struct RBTtreenode
{RBTtreenode<K, V>* _left;RBTtreenode<K, V>* _right;RBTtreenode<K, V>* _parent;pair<K, V> kv;color col;RBTtreenode(const pair<K, V>& _kv):_left(nullptr) //左孩子, _right(nullptr) //右孩子, _parent(nullptr) //父亲, kv(_kv), col(RED){}
};
4.红黑树结构
为了后续实现关联式容器简单,红黑树的实现中增加一个头结点,因为跟节点必须为黑色,为了 与根节点进行区分,将头结点给成黑色,并且让头结点的 pParent 域指向红黑树的根节点,pLeft 域指向红黑树中最小的节点,_pRight域指向红黑树中最大的节点,如下:
5.红黑树的插入!!!!
红黑树是在二叉搜索树的基础上加上其平衡限制条件,因此红黑树的插入可分为两步:
5.1按照二叉搜索的树规则插入新节点
if (root == nullptr)
{root = new node(_kv);root->col = BLACK;//规定根必须是黑的return true;
}
node* parent = nullptr; //比bst多了一个parent
node* cur = root; while (cur)
{parent = cur;if (cur->kv.first < _kv.first){cur = cur->_right;}else if (cur->kv.first > _kv.first){cur = cur->_left;}else{return false;}
}cur = new node(_kv);
cur->col = RED;//因为如果插入黑色的会使很多节点的一条路径上的黑色节点增多(相当于得罪了所有人),而插入红色则有可能只得罪父亲(如果父亲是红色的话)
if (parent->kv.first < _kv.first)
{parent->_right = cur;
}
else
{parent->_left = cur;
}
cur->_parent = parent;
5.2 检测新节点插入后,红黑树的性质是否造到破坏
因为新节点的默认颜色是红色,因此:如果其双亲节点的颜色是黑色,没有违反红黑树任何 性质,则不需要调整;但当新插入节点的双亲节点颜色为红色时,就违反了性质三不能有连 在一起的红色节点,此时需要对红黑树分情况来讨论:
约定:cur为当前节点,p为父节点,g为祖父节点,u为叔叔节点
1. 情况一: cur为红,p为红,g为黑,u存在且为红
解决方式:将p,u改为黑,g改为红,然后把g当成cur,继续向上调整。
2.情况二(单旋+变色): cur为红,p为红,g为黑,u不存在/u存在且为黑 (左左和右右)
细分就是:(1)g->left==p,p->left==cur;左左
(2)g->right==p,p->right==cur;右右
p为g的左孩子,cur为p的左孩子,则进行右单旋转;
相反, p为g的右孩子,cur为p的右孩子,则进行左单旋转
p、g变色--p变黑,g变红
3.情况三(双旋+变色): cur为红,p为红,g为黑,u不存在/u存在且为黑 (左右和右左)
细分就是:(1)g->left==p,p->right==cur;左右
(2)g->right==p,p->left==cur;右左
p为g的左孩子,cur为p的右孩子,则针对p做左单旋转;
相反, p为g的右孩子,cur为p的左孩子,则针对p做右单旋转
则转换成了情况2!!!!!,然后再用情况2的旋转处理一下就行了
针对每种情况进行相应的处理即可。
while (parent&&parent->col == RED)//parent为黑不需要调整,如果cur变成root,parent就不存在退出循环
{node* grandparent = parent->_parent;//祖父一定存在,因为只有根节点是没有祖父的,而根节点一定是黑色的if (parent==grandparent->_left){// g// p unode* uncle = grandparent->_right; //父亲在左则叔叔在右if (uncle && uncle->col == RED) //情况一.如果叔叔存在且为红色{//变色parent->col = uncle->col = BLACK;grandparent->col = RED;//重置cur,parent,继续向上处理cur = grandparent;//变为祖父parent = cur->_parent;}else //叔叔不存在或为黑色,旋转加变色{// g// p// cif (cur == parent->_left) //情况二.单旋{rotateR(grandparent);parent->col = BLACK;grandparent->col = RED;}// g// p// celse //情况三.cur==parent->_right,双旋{rotateL(parent);//经历一次左旋后变成情况二!!!!!!!!!!!(cur和parent换位置)rotateR(grandparent);cur->col = BLACK;grandparent->col = RED;}break;//调整一次就结束了,所以经历过旋转后不需要重置cur,parent,grandparent}}else{// g// u p//node* uncle = grandparent->_left; //父亲在右则叔叔在左if (uncle && uncle->col == RED){parent->col = uncle->col = BLACK;grandparent->col = RED;//cur = grandparent;parent = cur->_parent;}else{// g// u p// cif (cur == parent->_right){rotateL(grandparent);parent->col = BLACK;grandparent->col = RED;}else{// g// u p// crotateR(parent);rotateL(grandparent);cur->col = BLACK;grandparent->col = RED;}break;//调整一次就结束了,所以经历过旋转后不需要重置cur,parent,grandparent}}
6.红黑树的验证
红黑树的检测分为两步:
1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)
2. 检测其是否满足红黑树的性质
1.中序输出
void inorder()
{_inorder(root);
}void _inorder(node* root)
{if (root == nullptr)return;_inorder(root->_left);cout << root->kv.first << " ";_inorder(root->_right);
}
2.判断性质 (性质3和性质4)
bool check(node* it,int blacknum,int flag)
{if (it == nullptr){if (blacknum == flag)return true;elsereturn false;}else if (it->col == RED && it->_parent->col == RED)//十分巧妙,因为孩子的情况有很多,但父亲不是红就是黑,所以判断父亲更合适return false;else if (it->col == BLACK)blacknum++;return check(it->_left,blacknum,flag) && check(it->_right,blacknum,flag);
}bool isbalance()
{return _isbalance(root);
}bool _isbalance(node* root)
{if (root == nullptr)return true;else if (root->col == RED)return false;int blacknum = 0;int flag = 0;node* k = root;while (k){if (k->col == BLACK)flag++;k = k->_left;//这里十分巧妙,因为如果为红黑树,从某一节点到空的所有路径上的黑节点数量是一致的,所以可以先随便选一条路径,算出这一条路径上的黑节点数作为基准值,在由递归去和其他路径比较}return check(root,blacknum,flag);
}
7.红黑树的删除
可参考:《算法导论》或者《STL源码剖析》
红黑树 - _Never_ - 博客园
8 红黑树与AVL树的比较
红黑树和AVL树都是高效的平衡二叉树,增删改查的时间复杂度都是O(log_2 N),红黑树不追 求绝对平衡,其只需保证最长路径不超过最短路径的2倍,相对而言,降低了插入和旋转的次数, 所以在经常进行增删的结构中性能比AVL树更优,而且红黑树实现比较简单,所以实际运用中红 黑树更多。
9 红黑树的应用
1. C++ STL库 -- map/set
2. Java 库
3. linux内核
4. 其他一些库
10.代码全览
rbt.h:
enum color
{RED,BLACK
}; //列举color的各种可能情况template<class K, class V>
struct RBTtreenode
{RBTtreenode<K, V>* _left;RBTtreenode<K, V>* _right;RBTtreenode<K, V>* _parent;pair<K, V> kv;color col;RBTtreenode(const pair<K, V>& _kv):_left(nullptr), _right(nullptr), _parent(nullptr), kv(_kv), col(RED){}
};template<class K, class V>
class RBTtree
{
public:typedef RBTtreenode<K, V> node;bool insert(const pair<K, V>& _kv){if (root == nullptr){root = new node(_kv);root->col = BLACK;//规定根必须是黑的return true;}node* parent = nullptr; //比bst多了一个parentnode* cur = root; while (cur){parent = cur;if (cur->kv.first < _kv.first){cur = cur->_right;}else if (cur->kv.first > _kv.first){cur = cur->_left;}else{return false;}}cur = new node(_kv);cur->col = RED;//因为如果插入黑色的会使很多节点的一条路径上的黑色节点增多(相当于得罪了所有人),而插入红色则有可能只得罪父亲(如果父亲是红色的话)if (parent->kv.first < _kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//开始调整while (parent&&parent->col == RED)//parent为黑不需要调整,如果cur变成root,parent就不存在退出循环{node* grandparent = parent->_parent;//祖父一定存在,因为只有根节点是没有祖父的,而根节点一定是黑色的if (parent==grandparent->_left){// g// p unode* uncle = grandparent->_right; //父亲在左则叔叔在右if (uncle && uncle->col == RED) //情况一.如果叔叔存在且为红色{//变色parent->col = uncle->col = BLACK;grandparent->col = RED;//重置cur,parent,继续向上处理cur = grandparent;//变为祖父parent = cur->_parent;}else //叔叔不存在或为黑色,旋转加变色{// g// p// cif (cur == parent->_left) //情况二.单旋{rotateR(grandparent);parent->col = BLACK;grandparent->col = RED;}// g// p// celse //情况三.cur==parent->_right,双旋{rotateL(parent);//经历一次左旋后变成情况二!!!!!!!!!!!(cur和parent换位置)rotateR(grandparent);cur->col = BLACK;grandparent->col = RED;}break;//调整一次就结束了,所以经历过旋转后不需要重置cur,parent,grandparent}}else{// g// u p//node* uncle = grandparent->_left; //父亲在右则叔叔在左if (uncle && uncle->col == RED){parent->col = uncle->col = BLACK;grandparent->col = RED;//cur = grandparent;parent = cur->_parent;}else{// g// u p// cif (cur == parent->_right){rotateL(grandparent);parent->col = BLACK;grandparent->col = RED;}else{// g// u p// crotateR(parent);rotateL(grandparent);cur->col = BLACK;grandparent->col = RED;}break;//调整一次就结束了,所以经历过旋转后不需要重置cur,parent,grandparent}}}//1.如果parent和uncle都为RED,则可以一起变黑// 2.parent为黑不处理// 3.uncle为黑或不存在,parent为红,旋转+变色root->col = BLACK;//最后以防万一让根变为黑return true;}void rotateL(node* parent)//左旋,(新节点插入到较高右子树的右侧)// 1.右右{node* subr = parent->_right;node* subrl = subr->_left;parent->_right = subrl;subr->_left = parent;node* ppnode = parent->_parent;parent->_parent = subr;if (subrl) //subrl可能为空!!!!!!!{subrl->_parent = parent;}if (parent == root) //即如果parent->_parent==nullptr{root = subr;subr->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subr;}else if (ppnode->_right == parent){ppnode->_right = subr;}subr->_parent = ppnode;}}void rotateR(node* parent)//右旋,(新节点插入到较高左子树的左侧)// 2.左左{node* subl = parent->_left;node* sublr = subl->_right;parent->_left = sublr;if (sublr) //sublr可能为空!!!!!!!sublr->_parent = parent;node* ppnode = parent->_parent;subl->_right = parent;parent->_parent = subl;if (root == parent){root = subl;subl->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subl;}else if (ppnode->_right == parent){ppnode->_right = subl;}subl->_parent = ppnode;}}void inorder(){_inorder(root);}void _inorder(node* root){if (root == nullptr)return;_inorder(root->_left);cout << root->kv.first << " ";_inorder(root->_right);}bool check(node* it,int blacknum,int flag){if (it == nullptr){if (blacknum == flag)return true;elsereturn false;}else if (it->col == RED && it->_parent->col == RED)//十分巧妙,因为孩子的情况有很多,但父亲不是红就是黑,所以判断父亲更合适return false;else if (it->col == BLACK)blacknum++;return check(it->_left,blacknum,flag) && check(it->_right,blacknum,flag);}bool isbalance(){return _isbalance(root);}bool _isbalance(node* root){if (root == nullptr)return true;else if (root->col == RED)return false;int blacknum = 0;int flag = 0;node* k = root;while (k){if (k->col == BLACK)flag++;k = k->_left;//这里十分巧妙,因为如果为红黑树,从某一节点到空的所有路径上的黑节点数量是一致的,所以可以先随便选一条路径,算出这一条路径上的黑节点数作为基准值,在由递归去和其他路径比较}return check(root,blacknum,flag);}private:node* root = nullptr;
};
test.cpp:
#include<iostream>
using namespace std;#include"RBT.h"int main()
{int arr[] = { 790,760,969,270,31,424,377,24,702 };//int arr[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };RBTtree<int, int> it;for (auto i : arr){it.insert(make_pair(i, i));}it.inorder();cout << endl << it.isbalance() << endl;return 0;
}
相关文章:

移情别恋c++ ദ്ദി˶ー̀֊ー́ ) ——15.红黑树
1.红黑树的概念 红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或 Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路 径会比其他路径长出俩倍,…...

【C++】Eclipse技巧汇总
Eclipse C/C调试无法输入 在debug C/C程序时,Eclipse自带的窗口,无法读取cin等输入 解决办法: 参考:https://blog.csdn.net/sagjhdj/article/details/123271383 思路是调用外部console: 依次点击Debug>Debug Conf…...

Golang | Leetcode Golang题解之第430题扁平化多级双向链表
题目: 题解: func dfs(node *Node) (last *Node) {cur : nodefor cur ! nil {next : cur.Next// 如果有子节点,那么首先处理子节点if cur.Child ! nil {childLast : dfs(cur.Child)next cur.Next// 将 node 与 child 相连cur.Next cur.Chi…...

Java实现找色和找图功能
某天,张三接到一个任务需求,将一个Excel表格里面的员工信息,录入到员工系统里面,由于数据量非常大,操作起来巨慢。经过一段时间的操作和观察,他发现这种操作,非常有规律,基本就是一些…...

linux脚本工具
目录 shell工具查看Nvidia GPU状态查看某个监听端口是否存在设置局部代理查找关键字相关进程根据日常所需,持续更新 shell工具 减少重复性工作,简化工作流程,提高工作效率 将所编写的shell脚本赋予可执行权限 chmod x <脚本文件> 在…...

MySQL之基础篇
数据库操作 1.查看当前的数据库版本 select version(); 2.显示所有数据库 show databases; 3.创建数据库 create [if not exists] database 数据库名 character set 字符编码集 collate 排序规则; 我们这里提前说一下 被方括号括起来的代码 表示可写可不写 示例…...

13年408计算机考研-计算机网络
第一题: 解析:OSI体系结构 OSI参考模型,由下至上依次是:物理层-数据链路层-网络层-运输层-会话层-表示层-应用层。 A.对话管理显然属于会话层, B.数据格式转换,是表示层要解决的问题,很显然答案…...

camera2 + MediaRecorder 实现的分段循环录像功能
硬件设备Android系统 8.1; 硬件设备上开发过程中的问题记录: 问题1. 长时间录像后发现保存的录像文件始终只有4G。 原因及解决:Android 11之前的系统有对保存的文件大小有限制,所以只能修改成分段保存,即录像文件3.…...

LeetCode 每日一题 2024/9/23-2024/9/29
记录了初步解题思路 以及本地实现代码;并不一定为最优 也希望大家能一起探讨 一起进步 目录 9/23 2414. 最长的字母序连续子字符串的长度9/24 2207. 字符串中最多数目的子序列9/25 2306. 公司命名9/26 2535. 数组元素和与数字和的绝对差9/27 2516. 每种字符至少取 K…...

知识付费APP开发指南:基于在线教育系统源码的技术详解
本篇文章,我们将探讨基于在线教育系统源码的知识付费APP开发的技术细节,帮助开发者和企业快速入门。 一、选择合适的在线教育系统源码 选择合适的在线教育系统源码是开发的关键一步。市场上有许多开源和商业化的在线教育系统源码,开发者需要…...

物联网智能项目全面解析
目录 引言 一、物联网概述 1.1 什么是物联网 1.2 物联网的历史与发展 二、物联网智能项目分类 三、关键组件与技术 3.1 传感器和执行器 3.2 连接技术 3.3 数据处理与分析 3.4 用户界面 四、物联网智能项目案例分析 4.1 智能家居 4.2 智慧城市 4.3 工业物联网 4.4…...

【07】纯血鸿蒙HarmonyOS NEXT星河版开发0基础学习笔记-Swiper轮播组件与样式结构重用
序言: 本文详细讲解了关于我们在页面上经常看到的轮播图在鸿蒙开发中如何用Swiper实现,介绍了Swiper的基本用法与属性,及如何面对大段的重复代码进行封装和重用(Extend、Styles、Builder),使代码更加简洁易…...

Springboot3保存日志到数据库
保存日志到数据库 请求日志几乎是所有大型企业级项目的必要的模块,请求日志对于我们来说后期在项目运行上线一段时间用于排除异常、请求分流处理、限制流量等。请求日志一般都会记录请求参数、请求地址、请求状态(Status Code)、SessionId、…...

叉车高位显示器无线摄影,安装更加便捷!
叉车叉货,基本功能,但货叉升降高度确不一定,普通的3米左右,高的十几米,特别是仓储车,仓库叉货空间小,环境昏暗,视线受阻严重,司机叉货升的那么高怎么准确无误的插到货呢&…...

模板的特化
模板的特化 1.概念2.函数模板特化3.类模板的特化3.1 全特化3.2 偏特化3.2.1 部分特化3.2.2 参数更进一步的限制 4.总结 1.概念 在原模板类的基础上,针对特殊类型所进行特殊化的实现方式 2.函数模板特化 步骤 1.必须要先有一个基础的函数模板 2.关键字 template后面接…...

PCIE总线架构
1 概述 PCIe总线(Peripheral Component Interconnect Express)是一种高速串行计算机扩展总线标准,它是基于PCI总线的一种升级版,现在已经被广泛应用于各种高性能的计算机和服务器系统中。 PCIe总线提供更高的数据传输速度和更先进的特性,它主要特点如下: 高带宽:提供比…...

Adobe PR与AE的区别与联系(附网盘地址)
从事视频后期制作的小伙伴,对于PR(Premiere)和AE(After Effects)应该不会陌生。随着短视频的兴起,就连我们普通用户,拍摄完视频,都会去糟取精的剪辑一下,而PR正是一款功能…...

【QT 5 调试软件+Linux下调用脚本shell-无法调度+目录拼写+无法找目录+sudo权限(2)+问题解决方式+后续补充】
【QT 5 调试软件Linux下调用脚本shell-无法调度目录拼写无法找目录sudo权限(2)问题解决方式后续补充】 1、前言2、问题综述:自研qt上位机无法调度脚本(1)可能原因1:无法找到目录情况说明:解决思…...

企业防泄密妙招有哪些?请记住这8招!超实用,学起来!
在古代,有云:“密者,德之高也;事以密成,语以泄败。” 这些谚语不仅是对忠诚守密的高度赞扬,更是对保密工作重要性的深刻阐述。 在现代企业中,数据泄露已成为不容忽视的严峻挑战。 如何有效防止…...

pytorch千问模型源码分析
# 规范化技术,旨在替代传统的 Layer Normalization(LN) # 核心思想是对输入张量的每个样本的每个特征进行规范化,使其均值为 0,方差为 1 class Qwen2RMSNorm(nn.Module): def __init__(self, hidden_size, eps1e-6…...

滚雪球学SpringCloud[1.3]:SpringCloud环境搭建
全文目录: 前言1.3.1 环境要求1. JDK2. Maven3. IDE4. 其他工具 1.3.2 初始化Spring Boot项目方法一:使用Spring Initializr方法二:使用IDE项目结构 1.3.3 引入Spring Cloud依赖1. 更新pom.xml2. 添加Spring Cloud Starter依赖3. 示例完整的p…...

9.28今日错题解析(软考)
目录 前言面向对象技术——UML软件工程——软件能力成熟度模型(CMM)程序设计语言——编译 前言 这是用来记录我备考软考设计师的错题的,今天知识点为UML、软件能力成熟度模型(CMM)和编译,大部分错题摘自希…...

【Vue】以RuoYi框架前端为例,ElementUI封装图片上传组件——将图片信息转成base64后提交到后端保存
RuoYi 框架本身对于图片上传功能,在ElementUI的 <el-upload> 组件的基础装封装了 /components/ImageUpload/index.vue 组件。本组件就是在 RuoYi 自定义的 <ImageUpload> 组件的基础上进行改造,将图片的信息在上传之前处理成 base64 格式&am…...

【Linux】驱动的基本架构和编译
驱动源码 /** Silicon Integrated Co., Ltd haptic sih688x haptic driver file** Copyright (c) 2021 kugua <daokuan.zhusi-in.com>** This program is free software; you can redistribute it and/or modify it* under the terms of the GNU General Public Licen…...

1013. 将数组分成和相等的三个部分 数组切分
1013. 将数组分成和相等的三个部分 已解答 简单 相关标签 相关企业 提示 给你一个整数数组 arr,只有可以将其划分为三个和相等的 非空 部分时才返回 true,否则返回 false。 形式上,如果可以找出索引 i 1 < j 且满足 (arr[0] arr[…...

【深度学习】—— 自动微分、非标量变量的反向传播、 分离计算、 Python控制流的梯度计算
【深度学习】—— 自动微分 自动微分一个简单的例子 非标量变量的反向传播分离计算Python控制流的梯度计算 自动微分 求导是⼏乎所有深度学习优化算法的关键步骤。虽然求导的计算很简单,只需要⼀些基本的微积分。但对于复杂的模型,⼿⼯进⾏更新是⼀件很…...

Java项目实战II基于Java+Spring Boot+MySQL的大学城水电管理系统(源码+数据库+文档)
目录 一、前言 二、技术介绍 三、系统实现 四、文档参考 五、核心代码 六、源码获取 全栈码农以及毕业设计实战开发,CSDN平台Java领域新星创作者 一、前言 随着大学城规模的不断扩大和学生数量的急剧增加,大学城内的水电管理面临着前所未有的挑战…...

Vue 组件的三大组成部分详解
文章目录 模板(template)脚本(script)样式(style)总结 在 Vue.js 中,组件是构建用户界面的重要基石。一个 Vue 组件通常由三个主要部分组成:模板(template)、…...

深入理解Java内部类
一、什么是内部类 内部类是定义在另一个类内部的类。内部类与外部类(Enclosing Class)之间存在着紧密的联系,可以访问外部类的成员变量和方法,这使得它们在某些场景下非常有用。 1.1 内部类的分类 Java中的内部类主要有以下几种…...

fiddler抓包12_篡改请求(请求前断点)
课程大纲 原理 正常“客户端-服务器”通信,即发送请求,接收返回。 Fiddler抓包是「客户端-浏览器」进行交互时,请求和响应都会从Fiddler通过,Fiddler可以捕获并展示。 请求前断点(BreakPoint Before Request࿰…...