红黑树(数据结构篇)

数据结构之红黑树

红黑树(RB-tree)

概念：

  • 红黑树是AVL树的变种，它是每一个节点或者着成红色，或者着成黑色的一棵二叉查找树。
  • 对红黑树的操作在最坏情形下花费O(logN)时间，它的插入操作使用的是非递归形式实现
  • 红黑树的高度最多是2log(N+1)

特性：

  • 红黑树是具有着色性质的二叉查找树，也就意味着树的节点值是有序的，且每个节点只可能是红色或者黑色
  • 红黑树的根是黑色的
  • 如果一个节点是红色的，那么它的子节点必须是黑色的
  • 从一个节点到一个空指针的每一条路径必须包含相同数目的黑色节点

自顶向下插入操作：

  1. 如果使用自底向上插入的话还需要进行逐步递归是他们保证满足红黑树特性，效率就降低了。

  2. 令X为新插入节点(在下面的第三操作中为当前节点)，P为X的父节点，G为P的父节点(也就是X的祖父节点)，GP为G的父节点(也就是P的祖父节点，X的曾祖父节点)

  3. 因为红黑树是一颗二叉查找树，因此在插入时需要查找要插入的值的正确位置，在这个查找路径中，如果遇到节点(X)为黑色而子节点全部为红色，我们就进行翻转操作，也就是将该节点(X)着成红色，子节点全部着成黑色。翻转后:

    如果翻转后发现P和X节点都是红色就需要根据树的结构进行旋转操作

    1. 如果X，P，G形成"一字形"，则对P的父节点G(也就是X的祖父节点)与P进行单旋转，并将新根也就是P着成黑色，新根的子节点都着成红色。
    2. 如果X，P，G形成"之字形"，则对G与X节点进行双旋转，并将新根着成黑色(也就是X节点)，然后将新根的子节点着成红色

  4. 如果该节点(X)是黑色则继续将X下降，直到找到红色节点继续翻转，或者找到指定插入位置，找到指定位置也就是当前节点位置X就进行插入，新节点也是红色，需要重新判断其父节点是否为红色，为红色又需要进行翻转操作来调整。

自顶向下删除操作

  1. 自顶向下删除也需要保证红黑树的性质，插入是插入一片红色的叶子节点，那么反过来我们删除一个红色叶子节点就不会破坏红黑树性质，自顶向下插入的翻转操作是将红色节点减少，并将红色节点上浮，因为删除是插入的逆过程，因此删除的翻转操作就是要将树中的红色节点增多，并将红色节点下沉，这样我们删除红色叶子节点的概率更大，并且不会破坏红黑树性质

  2. 删除操作一共有5种情况需要解决

    1. 要删除节点cur跟其兄弟节点s原本颜色为黑色，父亲节点p为红色
    2. s的两个儿子都是红色，这样双旋转和单旋转都可以，这里优先选择ps单选转调整，情况1-case4
    3. s的左儿子为红色，需要ps.l双旋转调整(s.l为s的左儿子)，情况2-case1
    4. s的右儿子为红色，需要ps单旋转调整，情况3-case2
    5. s有两个黑色儿子，直接cur,p,s颜色翻转操作调整，情况4-case3
    6. p和cur为黑色，s为红色，需要交换sp节点的颜色，并且sp单旋转调整，情况5-case5
    7. cur为红色，可以继续将cur下降，也就是当前cur指向原本cur的子节点，如果为红色继续下降，如果为黑色就判断是否需要操作

  3. tomove指向要删除节点也就是目标节点，而p指向真正要删除的叶子节点，cur则while循环完后则是指向nil节点，因为将tomove标记完，就进行cur和p就查找tomove右子树的最小值节点进行删除，而while循环终止条件为cur==nil情况，因此p指向真正要删除的节点

  4. 找到tomove和p后，将tomove的data等于p的data，将p删除，因为p为叶子节点，将p的父节点指向nil。

image 情况2-case1

image 情况3-case2

image 情况4-case3

image-20240502001308851 情况1-case4

image 情况5-case5

计算红黑树层数：

  • 需要对log2(树中总共节点数+1)向上取整

代码：

int Height(const int count){
    return std::ceil(std::log2(count+1));
}

代码实现：

#include <iostream>
#include <queue>
#include <math.h>
#include <limits.h>
using namespace std;

typedef enum {red,black} colortype;

struct RBNode{
    int data;
    RBNode *left,*right,*parent;
    colortype color;   //颜色
    RBNode(const int val,RBNode* l,RBNode* r,RBNode* p,colortype c=red):data(val),
                                                                        left(l),right(r),parent(p),color(c){};
};

class RBtree{
public:
    RBtree(){
        nil=new RBNode(INT_MAX, nullptr, nullptr, nullptr,black);
        root= nullptr;
        t=new RBNode(INT_MIN,nil,nil,nil,black);
        size=0;
    }

    ~RBtree(){
        clear();
        delete t;
        delete nil;
    };
    void insert(const int val);      //插入操作
    void del(const int val);       //删除操作
    RBNode* find(const int val);   //查找操作
    void print();     //打印操作,层序遍历
    //清空操作
    void clear(){
        clear(root);
        root= nullptr;
        t->right=nil;
        size=0;
    }

protected:
    void overturnred(const int val,RBNode* &cur);    //翻转操作,将当前节点变成红色，子节点变成黑色
    void overturnblack(int val,RBNode* &cur);   //翻转操作，将当前节点变成黑色，子节点变成红色
    RBNode* SingleRotatewithleft(RBNode* &k1);
    RBNode* SingleRotatewithright(RBNode* &k1);
    RBNode* Rotate(const int val,RBNode* &k1){
        if(val<k1->data){
            return k1->left=val<k1->left->data? SingleRotatewithleft(k1->left): SingleRotatewithright(k1->left);
        }else{
            return k1->right=val<k1->right->data? SingleRotatewithleft(k1->right): SingleRotatewithright(k1->right);
        }
    }
    void clear(RBNode* &rt);
    // 计算红黑树层数
    int Height(int nodeCount) {
        // 红黑树的层数为 log2(nodeCount+1)
        return (int)std::ceil(std::log2(nodeCount+1));
    }
private:
    RBNode* root;
    RBNode* nil;   //空节点，color为黑色
    RBNode* t;  //根标记，用于删除操作的便捷
    int size;
};

RBNode* RBtree::SingleRotatewithleft(RBNode *&k1) {
    RBNode* k2;
    k2=k1->left;
    k1->left=k2->right;
    k2->right=k1;
    return k2;
}

RBNode* RBtree::SingleRotatewithright(RBNode *&k1) {
    RBNode* k2;
    k2=k1->right;
    k1->right=k2->left;
    k2->left=k1;
    return k2;
}

//翻转操作
void RBtree::overturnred(const int val,RBNode* &cur) {
    cur->color=red;
    cur->left->color=cur->right->color=black;
    RBNode* p=cur->parent;
    if(p->color==red){
        RBNode* g=p->parent;
        g->color=red;
        if((val<g->data)!=(val<p->data)){     //双旋转
            p= Rotate(val,g);
        }
        cur= Rotate(val,g->parent);
        cur->color=black;
    }
    root->color=black;
}


//插入操作
void RBtree::insert(const int val) {
    if(root== nullptr){
        root=new RBNode(val,nil,nil, t,black);
        t->right=root;
        size++;
        return;
    }
    RBNode *cur,*p;
    cur=p=root;
    while (cur!=nil){
        p=cur;
        if(cur->left->color==red&&cur->right->color==red){
            overturnred(val,cur);
        }
        cur=val<p->data?p->left:p->right;
    }
    if(cur!=nil){
        return;
    }
    cur=new RBNode(val, nil, nil, p);
    if(val<p->data){
        p->left=cur;
    }else{
        p->right=cur;
    }
    overturnred(val,cur);
    size++;
}

void RBtree::overturnblack(int val, RBNode *&cur) {
    cur->color=red;
    RBNode* p=cur->parent;
    RBNode* s=val<p->data?p->left:p->right;
    //case4:要删除节点cur跟其兄弟节点s原本颜色为黑色，父亲节点p为红色，s的两个儿子都是红色，这样双旋转和单旋转都可以，这里优先选择ps单选转
    //case2:要删除节点cur跟其兄弟节点s原本颜色为黑色，父亲节点p为红色，s的右儿子为红色情况，需要ps单旋转调整
    if(s->right->color==red){
        val=s->right->data;
    }
    //case1:要删除节点cur跟其兄弟节点s原本颜色为黑色，父亲节点p为红色，s的左儿子为红色的情况,需要ps.l双旋转调整
    else if(s->left->color==red){
        val=s->left->data;
    }
        //case3:要删除节点cur跟其兄弟节点s原本颜色为黑色，父亲节点p为红色，s有两个黑儿子(nil节点也是黑色),直接将颜色翻转即可
    else{
        //翻转操作
        if(s!=nil){
            s->color=red;
        }
        p->color=black;
        return;
    }
    if((val<s->data)!=(val<p->data)){
        Rotate(val,p);
    }
    RBNode* g=p->parent;
    Rotate(val,g);
    //将调整完的cur的新祖父也就是s或者s的左儿子变成红色，也就是删除完cur后将颜色调整到之前cur在翻转前的情况
    g->color=red;
    g->left->color=g->right->color=black;
}


void RBtree::del(const int val) {
    RBNode* tomove=nil;  //找到删除节点
    RBNode *g,*p,*s,*cur;
    g=p=t,s=t->left,cur=root;
    while (cur!=nil){
        //翻转颜色
        if(cur->left->color==black&&cur->right->color==black){
            overturnblack(val,cur);
        }else{
            g=p;p=cur;
            if(val<p->data){
                cur=p->left,s=p->right;
            }else{
                tomove=cur,cur=p->right,s=p->left;
            }
            //case5:此时肯定p和cur都为黑色，因为如果p为红色早就翻转了，s肯定是红色，将s变成黑色，p变为红色，sp单旋转调整
            if(cur->color==black){
                s->color=black;
                p->color=red;
                //单旋转完，cur新祖父变为s,将s重新更改
                g= Rotate(val,g);
                s=val<p->data?p->left:p->right;
                //调整完该情况就重新检查上述操作
                continue;
            }
            //else，cur一定为红色，则可以直接继续将cur继续下降
        }
        g=p;p=cur;
        if(val<p->data){
            cur=p->left,s=p->right;
        }else{
            tomove=cur,cur=p->right,s=p->left;
        }
    }
    root->color=black;   //保证红黑树性质2不被破坏，也就是根一定为黑色

    //判断是否找到真正要删除的节点，如果找不到就退出
    if(tomove==nil&&tomove->data!=val){
        cout<<"未找到要删除对应值的节点";
        return;
    }

    //tomove是要删除的节点，而p指向的是真正要删除的节点
    tomove->data=p->data;
    if(g->left==p) g->left=nil;
    else g->right=nil;
    delete p;
    size--;
}

RBNode* RBtree::find(const int val) {
    if(root!= nullptr){
        RBNode* cur=root;
        while (cur!=nil){
            if(cur->data==val) return cur;
            cur=val<cur->data?cur->left:cur->right;
        }
        if(cur==nil){
            cout<<"树中没有指定值节点"<<endl;
        }
    }
    return root;
}

void RBtree::print() {
    if(root== nullptr){
        cout<<"树为空"<<endl;
        return;
    }
    queue<RBNode*>q;
    q.push(root);
    int cnt=1;
    int ans=0;
    int h= Height(size);
    while (!q.empty()){
        if(ans==h+1) break;
        RBNode* cur=q.front();
        q.pop();
        if(cur== nullptr){
            cout<<"null"<<" ";
            continue;
        }
        q.push(cur->left);
        q.push(cur->right);
        if(cur->color==red){
            cout<<"\033[31m"<<cur->data<<"\033[0m"<<" ";
        }else if(cur==nil) cout<<"nil"<<" ";
        else cout<<cur->data<<" ";
        if(cnt==pow(2,ans)){
            cout<<endl;
            cnt=0,ans++;
        }
        cnt++;
    }
    return;
}


void RBtree::clear(RBNode* &rt) {
    if(rt!=nil){
        clear(rt->left);
        clear(rt->right);
        delete rt;
        rt=nil;
    }
    return;
}

int main() {
    RBtree rBtree;
    rBtree.insert(30);
    rBtree.insert(15);
    rBtree.insert(65);
    rBtree.insert(10);
    rBtree.insert(20);
    rBtree.insert(5);
    rBtree.insert(60);
    rBtree.insert(70);
    rBtree.insert(50);
    rBtree.insert(64);
    rBtree.insert(66);
    rBtree.insert(85);
    rBtree.insert(40);
    rBtree.insert(55);
    rBtree.insert(63);
    rBtree.insert(80);
    rBtree.insert(90);
    rBtree.insert(45);
    rBtree.del(65);
    rBtree.del(50);
    rBtree.del(30);
    rBtree.print();
    return 0;
}

尾言

完整版笔记也就是数据结构与算法专栏完整版可到我的博客进行查看，或者在github库中自取(包含源代码)

  • 博客1： codebooks.xyz
  • 博客2：moonfordream.github.io
  • github项目地址：Data-Structure-and-Algorithms

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

视频融合共享平台LntonCVS视频监控安防系统运用多视频协议建设智慧园区方案

视频融合共享平台LntonCVS视频监控安防系统运用多视频协议建设智慧园区方案

智慧园区&#xff0c;作为现代化城市发展的重要组成部分&#xff0c;不仅推动了产业的升级转型&#xff0c;也成为了智慧城市建设的核心力量。随着产业园区之间的竞争日益激烈&#xff0c;如何打造一个功能完善、智能化程度高的智慧园区&#xff0c;已经成为了业界广泛关注的焦…
阅读更多...
软考高级论文真题“论大数据lambda架构”

软考高级论文真题“论大数据lambda架构”

论文真题 大数据处理架构是专门用于处理和分析巨量复杂数据集的软件架构。它通常包括数据收集、存储、处理、分析和可视化等多个层面&#xff0c;旨在从海量、多样化的数据中提取有价值的信息。Lambda架构是大数据平台里最成熟、最稳定的架构&#xff0c;它是一种将批处理和流…
阅读更多...
怎么将几段音频合并在一起，试试这几个音频拼接小妙招

怎么将几段音频合并在一起，试试这几个音频拼接小妙招

怎么将多个音频合并在一起呢&#xff1f;音频是我们日常工作生活中常见的文件&#xff0c;音频与我们息息相关&#xff0c;无论你是音乐爱好者&#xff0c;还是喜欢记录生活中的声音&#xff0c;都离不开音频。因此我们会遇到关于很多音频剪辑的难题&#xff0c;就像今天小编给…
阅读更多...
某棋牌渗透测试

某棋牌渗透测试

前言 由于传播、利用此文所提供的信息而造成的任何直接或者间接的后果及损失&#xff0c;均由使用者本人负责&#xff0c;文章作者不为此承担任何责任。 一、信息收集 这里通过fofa进行收集&#xff0c;语法为&#xff1a;body某棋牌 && titlexxx 图1-1 fofa资产收集 …
阅读更多...
第 402 场 LeetCode 周赛题解

第 402 场 LeetCode 周赛题解

A 构成整天的下标对数目 I 计数&#xff1a;遍历 h o u r s hours hours &#xff0c;记录 h o u r s [ i ] % 24 hours[i]\%24 hours[i]%24 的出现次数 class Solution {public:long long countCompleteDayPairs(vector<int>& hours) {vector<int> cnt(24);…
阅读更多...
图像处理：Python使用OpenCV 减少图片噪音

图像处理：Python使用OpenCV 减少图片噪音

文章目录 1. 均值滤波 (Mean Filtering)2. 高斯滤波 (Gaussian Filtering)3. 中值滤波 (Median Filtering)4.代码实现示例5.效果展示 在图像处理中&#xff0c;均值滤波、高斯滤波和中值滤波是三种常用的降噪方法。它们的实现原理各有不同&#xff1a; 1. 均值滤波 (Mean Filte…
阅读更多...
Paper Reading: EfficientAD：毫秒级延迟的准确视觉异常检测

Paper Reading: EfficientAD：毫秒级延迟的准确视觉异常检测

EfficientAD 简介方法高效的patch描述PDN教师pretraining 轻量级的师生模型逻辑异常检测异常图像的标准化 实验局限性 EfficientAD: Accurate Visual Anomaly Detection at Millisecond-Level Latencies EfficientAD&#xff1a;毫秒级延迟的准确视觉异常检测, WACV 2024 paper…
阅读更多...
贪吃蛇——c语言版

贪吃蛇——c语言版

文章目录 演示效果实现的基本功能技术要点源代码实现功能GameStart打印欢迎界面和功能介绍绘制地图创建蛇创建食物 GameRun打印提示信息蛇每走一步 GameEnd蛇死亡后继续游戏 演示效果 贪吃蛇1.0演示视频 将终端应用程序改为控制台主机 实现的基本功能 贪吃蛇地图绘制蛇吃食物的…
阅读更多...
基于TCAD与紧凑模型结合方法探究陷阱对AlGaN/GaN HEMTs功率附加效率及线性度的影响

基于TCAD与紧凑模型结合方法探究陷阱对AlGaN/GaN HEMTs功率附加效率及线性度的影响

来源&#xff1a;Investigation of Traps Impact on PAE and Linearity of AlGaN/GaN HEMTs Relying on a Combined TCAD–Compact Model Approach&#xff08;TED 24年&#xff09; 摘要 本文提出了一种新型建模方法&#xff0c;用于分析GaN HEMTs的微波功率性能。通过结合工…
阅读更多...
【机器学习 复习】第4章 决策树算法（重点）

【机器学习 复习】第4章 决策树算法（重点）

一、概念 1.原理看图&#xff0c;非常简单&#xff1a; &#xff08;1&#xff09;蓝的是节点&#xff0c;白的是分支&#xff08;条件&#xff0c;或者说是特征&#xff0c;属性&#xff0c;也可以直接写线上&#xff0c;看题目有没有要求&#xff09;&#xff0c; &#xff…
阅读更多...
MySQL 离线安装客户端

MySQL 离线安装客户端

1. 官方网址下载对应架构的安装包。 比如我的是centOs 7 x64。则需下载如图所示的安装包。 2. 安装 使用如下命令依次安装 devel , client-plugins, client. rpm -ivh mysql-community-*.x86_64.rpm --nodeps --force 在Linux系统中&#xff0c;rpm是一个强大的包管理工具&…
阅读更多...
容器基本概念_从虚拟化技术_到容器化技术_开通青云服务器_并远程连接_容器安装---分布式云原生部署架构搭建007

容器基本概念_从虚拟化技术_到容器化技术_开通青云服务器_并远程连接_容器安装---分布式云原生部署架构搭建007

这一部分,属于以前都会用到的,会快速过一遍,对于关键技术问题会加以说明 https://www.yuque.com/leifengyang/oncloud文档地址在这里,可以看,有些命令可以复制使用 可以看到容器的出现就是 目的就是,让你做的所有的软件,都可以一键部署启动 打包就是docker build 然后: 对于…
阅读更多...
spring boot接入nacos 配置中心

spring boot接入nacos 配置中心

再接入nacos配置中心时&#xff0c;需要确认几点&#xff1a; 1. spring boot 版本 (spring boot 2.x ) 2. nacos 配置中心 服务端 版本 (1.1.4) 3. nacos client 客户端版本 (1.1.4) 方式一 1. 启动 nacos 服务端&#xff0c;这里不做解释 在配置中心中加入几个配置 2. 在…
阅读更多...
DNS部署与安全

DNS部署与安全

一、DNS 英文全称&#xff1a;Domain Name Service 含义&#xff1a;域名服务 作用&#xff1a;为客户机提供域名解析服务 二、域名组成 域名组成概述 &#xff08;1&#xff09;如"www.sina.com.cn”是一个域名&#xff0c;从严格意义上讲&#xff0c;“sina.com.cn”…
阅读更多...
深度解读爆火国产大模型Kimi（附教程，建议收藏！）_学习kimi

深度解读爆火国产大模型Kimi（附教程，建议收藏！）_学习kimi

如果要问目前最强的大模型是谁&#xff0c;答案毫无疑问还是GPT4。但如果要问最近最火的大模型是谁&#xff0c;国产Kimi表示舍我其谁。 这个由一家初创还不到1年的AI企业做出来的现象级大模型智能助手&#xff0c;体验过的用户都表示惊艳到了&#xff0c;投过的一级机构继续加…
阅读更多...
DS1339C串行实时时钟-国产兼容RS4C1339

DS1339C串行实时时钟-国产兼容RS4C1339

RS4C1339串行实时时钟是一种低功耗的时钟/日期设备&#xff0c;具有两个可编程的一天时间报警器和一个可编程方波输出。地址和数据通过2线双向总线串行传输。时钟/日期提供秒、分钟、小时、天、日期、月份和年份信息。对于少于31天的月份&#xff0c;月末的日期会自动调整&…
阅读更多...
2024年全球架构师峰会(ArchSummit深圳站)

2024年全球架构师峰会(ArchSummit深圳站)

前言 ArchSummit全球架构师峰会是极客邦科技旗下InfoQ中国团队推出的重点面向高端技术管理者、架构师的技术会议&#xff0c;54%参会者拥有8年以上工作经验。 ArchSummit聚焦业界强大的技术成果&#xff0c;秉承“实践第一、案例为主”的原则&#xff0c;展示先进技术在行业中的…
阅读更多...
Java面试八股之JVM永久代会发生垃圾回收吗

Java面试八股之JVM永久代会发生垃圾回收吗

JVM永久代会发生垃圾回收吗 JVM的永久代&#xff08;PermGen&#xff09;在Java 8之前是存在的一部分&#xff0c;主要用于存储类的元数据、常量池、静态变量等。在这些版本中&#xff0c;永久代确实会发生垃圾回收&#xff0c;尤其是在永久代空间不足或超过某个阈值时&#x…
阅读更多...
【C语言】手写学生管理系统丨附源码+教程

【C语言】手写学生管理系统丨附源码+教程

最近感觉大家好多在忙C语言课设~ 我来贡献一下&#xff0c;如果对你有帮助的话谢谢大家的点赞收藏喔&#xff01; 1. 项目分析 小白的神级项目&#xff0c;99%的程序员&#xff0c;都做过这个项目&#xff01; 掌握这个项目&#xff0c;就基本掌握 C 语言了&#xff01; 跳…
阅读更多...
JUC并发编程-第二天：线程高级部分

JUC并发编程-第二天：线程高级部分

线程高级部分 线程不安全原子性可见性有序性&#xff08;指令重排&#xff09; 线程不安全 多线程下并发同时对共享数据进行读写&#xff0c;会造成数据混乱线程不安全 当多线程下并发访问临界资源时&#xff0c;如果破坏其原子性、可见性、有序性&#xff0c;可能会造成数据不…
阅读更多...
最新文章

Copyright @ 2022~2023