【高阶数据结构】红黑树

文章目录

    • 1. 使用场景
    • 2. 性质
    • 3. 结点定义
    • 4. 结点旋转
    • 5. 结点插入

1. 使用场景

  • Linux进程调度CFS
  • Nginx Timer事件管理
  • Epoll事件块的管理

2. 性质

  • 每一个节点是红色或者黑色
  • 根节点一定是黑色
  • 每个叶子节点是黑色
  • 如果一个节点是红色,那么它的两个儿子节点都是黑色
  • 从任意一个节点到其每个叶子节点的所有路径都包含相同数目的黑色节点

3. 结点定义

typedef int KEY_TYPE;

typedef struct _rbtree_node
{
    unsigned char color;
    struct _rbtree_node *left;
    struct _rbtree_node *right;
    struct _rbtree_node *parent;

    KEY_TYPE key;
    void *value;
}rbtree_node;

4. 结点旋转

在这里插入图片描述

左旋实现

void _left_rotate(rbtree *T, rbtree_node *x)
{
    rbtree_node *y = x->right;

    x->right = y->left;
    if (y->left != T->nil)
    {
        y->left->parent = x;
    }

    y->parent = x->parent;
    if (x->parent == T->nil)
    {
        T->root == y;
    }
    else if (x == x->parent->left)
    {
        x->parent->left = y;
    }
    else if (x == x->parent->right)
    {
        x->parent->right = y;
    }

    y->left = x;
    x->parent = y;
}

右旋实现

void _right_rotate(rbtree *T, rbtree_node *y)
{
    rbtree_node *x = y->left;

    y->left = x->right;
    if (x->right != T->nil)
    {
        x->right->parent = y;
    }

    x->parent = y->parent;
    if (y->parent == T->nil)
    {
        T->root = x;
    }
    else if (y == y->parent->left)
    {
         y->parent->left = x;
    }
    else if (y == y->parent->right)
    {
        y->parent->right = x;
    }

    x->right = y;
    y->parent = x;
}

5. 结点插入

  1. 将新节点的颜色设为红色,然后按照二叉查找树的规则插入到合适的位置

    如果设置成黑色的话,则必定会违反上述五条性质中的第五条

  2. 如果新节点是根节点,那么将其颜色改为黑色,结束

  3. 如果新节点的父节点是黑色,那么不需要做任何调整,结束

  4. 如果新节点的父节点和叔叔节点(父节点的兄弟节点)都是红色,那么将它们的颜色改为黑色,将祖父节点(父节点的父节点)的颜色改为红色,然后把祖父节点作为新的当前节点,重复步骤2和3

  5. 如果新节点的父节点是红色,但叔叔节点是黑色或不存在,那么分四种情况进行旋转和变色操作:

    • 新节点是父节点的左子节点,且父节点是祖父节点的左子节点(左左情况),那么对祖父节点进行右旋,并交换祖父和父亲的颜色
    • 新节点是父节点的右子节点,且父节点是祖父节点的左子节点(左右情况),那么对父亲节点进行左旋,并交换新节点和父亲节点的颜色,然后把新节点作为当前节点,转化为左左情况处理
    • 新节点是父亲节点的右子节点,且父亲节点是祖父节点的右子节点(右右情况),那么对祖父节点进行左旋,并交换祖父和父亲的颜色
    • 新节点是父亲节点的左子节点,且父亲节点是祖父节点的右子节点(右左情况),那么对父亲节点进行右旋,并交换新节点和父亲节点的颜色,然后把新节点作为当前节点,转化为右右情况处理
int key_compare(KEY_TYPE *a, KEY_TYPE *b)
{
    //TODO
}

void rbtree_insert_fixup(rbtree *T, rbtree_node *z)
{
    while (z->parent->color == RED)
    {
        if (z->parent == z->parent->parent->left)
        {
            rbtree_node *y = z->parent->parent->right;
            if (y->color == RED)
            {
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;

                z = z->parent->parent;
            }
            else
            {
                if (z == z->parent->right)
                {
                    z = z->parent;
                    _left_rotate(T, z);
                }

                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                _right_rotate(T, z->parent->parent);
            }
        }
    }
    T->root->color = BLACK;
}

void rbtree_insert(rbtree *T, rbtree_node *z)
{
    rbtree_node *x = T->root;
    rbtree_node *y = T->nil;

    while (x != T->nil)
    {
        y = x;
        // 如果是自定义类型,可以实现key_compare接口来进行比较
        if (x->key > z->key)
        {
            x = x->right;
        }
        else if (x->key < z->key)
        {
            x = x->left;
        }
        else
        {
            return;
        }
    }

    z->parent = y;
    if (y == T->nil)
    {
        T->root = z;
    }
    else if (z->key > y->key)
    {
        y->right = z;
    }
    else
    {
        y->left = z;
    }

    z->left = T->nil;
    z->right = T->nil;
    z->color = RED;

    rbtree_insert_fixup(T, z);
}

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

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

相关文章

【基础算法】单链表的OJ练习(6) # 复制带随机指针的链表 #

文章目录&#x1f347;前言&#x1f34e;复制带随机指针的链表&#x1f351;写在最后&#x1f347;前言 本章的链表OJ练习&#xff0c;是最后的也是最难的。对于本题&#xff0c;我们不仅要学会解题的思路&#xff0c;还要能够通过这个思路正确的写出代码&#xff0c;也就是思路…

20230314整理

1.JVM内存区域 程序计数器&#xff1a;字节码解释器通过改变程序计数器来依次读取指令&#xff0c;在多线程的情况下&#xff0c;程序计数器用于记录当前线程执行的位置&#xff0c;从而当线程被切换回来的时候能够知道该线程上次运行到哪儿了。它的生命周期随着线程的创建而创…

基于Java+SpringBoot+vue的学生成绩管理系统设计和实现【源码+论文+演示视频+包运行成功】

博主介绍&#xff1a;专注于Java技术领域和毕业项目实战 &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;&#x1f3fb; 不然下次找不到哟 Java项目精品实战案例&#xff08;200套&#xff09; 目录 一、效果演示 二、…

扯什么 try-catch 性能问题?

“yes&#xff0c;你看着这鬼代码&#xff0c;竟然在 for 循环里面搞了个 try-catch&#xff0c;不知道try-catch有性能损耗吗&#xff1f;”老陈煞有其事地指着屏幕里的代码&#xff1a; for (int i 0; i < 5000; i) {try {dosth} catch (Exception e) {e.printStackTrace…

如何测试一个AI系统?

最近AI大火&#xff0c;chatgpt、GPT-4、文心一言不断的在轰炸着我们的生活、工作&#xff0c;很多时候我们都在感叹这智能化来的太快了。对于一个测试工程师&#xff0c;如何开始测试一个AI系统呢&#xff0c;今天我们就一起来聊聊相关的内容。 智能系统对测试工程师提出的新问…

2023年网络安全比赛--网络安全事件响应中职组(超详细)

一、竞赛时间 180分钟 共计3小时 二、竞赛阶段 1.找出黑客植入到系统中的二进制木马程序,并将木马程序的名称作为Flag值(若存在多个提交时使用英文逗号隔开,例如bin,sbin,…)提交; 2.找出被黑客修改的系统默认指令,并将被修改的指令里最后一个单词作为Flag值提交; 3.找出…

React 用一个简单案例体验一遍 React-dom React-router React-redux 全家桶

一、准备工作 本文略长&#xff0c;建议耐心读完&#xff0c;每一节的内容与上一节的内容存在关联&#xff0c;最好跟着案例过一遍&#xff0c;加深记忆。 1.1 创建项目 第一步&#xff0c;执行下面的命令来创建一个 React 项目。 npx create-react-app react-example cd rea…

Springboot集成Swagger

一、Swagger简介注意点&#xff01; 在正式发布的时候要关闭swagger&#xff08;出于安全考虑&#xff0c;而且节省内存空间&#xff09;之前开发的时候&#xff0c;前端只用管理静态页面&#xff0c; http请求到后端&#xff0c; 模板引擎JSP&#xff0c;故后端是主力如今是前…

【宝塔面板部署nodeJs项目】网易云nodeJs部署在云服务器上,保姆级教程,写网易云接口用自己的接口不受制于人

看了很多部署的&#xff0c;要么少步骤&#xff0c;要么就是写的太简洁&#xff0c;对新手不友好 文章目录前言一、下载网易云nodejs项目1. git clone下载&#xff0c;两种方式2. 运行项目二、使用步骤1. 先在本地运行2.测试接口三、部署服务器1. 在宝塔面板安装pm2管理器2. 压…

字符函数和字符串函数【上篇】

文章目录&#x1f396;️1.函数介绍&#x1f4ec;1.1. strlen&#x1f4ec;1.2. strcpy&#x1f4ec;1.3. strcat&#x1f4ec;1.4. strcmp&#x1f4ec;1.5. strncpy&#x1f4ec;1.6. strncat&#x1f4ec;1.7. strncmp&#x1f396;️1.函数介绍 &#x1f4ec;1.1. strlen …

入行 5年,跳槽 3次,我终于摸透了软件测试这行(来自过来人的忠告)

目录 前言 第一年 第二年 第三年 第四年 作为过来人的一些忠告 前言 最近几年行业在如火如荼的发展壮大&#xff0c;以及其他传统公司都需要大批量的软件测试人员&#xff0c;但是20年的疫情导致大规模裁员&#xff0c;让人觉得行业寒冬已来&#xff0c;软件测试人员的职…

【YOLOv8/YOLOv7/YOLOv5/YOLOv4/Faster-rcnn系列算法改进NO.60】损失函数改进为wiou

前言作为当前先进的深度学习目标检测算法YOLOv8&#xff0c;已经集合了大量的trick&#xff0c;但是还是有提高和改进的空间&#xff0c;针对具体应用场景下的检测难点&#xff0c;可以不同的改进方法。此后的系列文章&#xff0c;将重点对YOLOv8的如何改进进行详细的介绍&…

css属性学习

css属性 就是我们选择器里面 { } 中的内容 字体样式 font-size 控制字体大小&#xff1a;单位px&#xff08;像素&#xff09; 默认字体占16个像素 <p style"font-size:30px;">font-size&#xff1a;字体大小&#xff0c;单位的话可以用px表示占的像素个数&…

Mini-Xml 经典实例Demo

欢迎小伙伴的点评✨✨&#xff0c;相互学习、博主将自己研发xml微型服务器的经验与之分享&#x1f30f;&#x1f30f;&#x1f642; 文章目录前言一、使用mxml库编写Xml文件1.1 经典实例Demo_11.2、经典实例Demo_21.3、经典实例Demo_3二、总结前言 本章将会给大家带来mini-xml…

在我的MacBook上捣鼓ESP8266

周三是我们的篮球日&#xff0c;打篮球后总是会有些兴奋&#xff0c;然后就容易睡不着&#xff0c;额&#xff0c;睡不着就拿我的ESP8266开发板出来捣鼓一下。先下载编译工具链https://github.com/espressif/ESP8266_RTOS_SDK下载sdkgit clone https://github.com/espressif/ES…

C++程序在内存中的模型

进程&#xff08;Process&#xff09;是计算机中的程序&#xff0c;数据集合在其上运行的一次活动&#xff0c;是系统进行资源分配的基本单位。每个进程都有自己独立的虚拟内存地址空间&#xff0c;这个虚拟的内存地址空间一般是线性连续的&#xff0c;这个内存地址空间是虚拟的…

面试官想看我写一篇关于“原型链”和“构造函数”深入理解的文章

前言&#xff1a; 在参加工作的面试过程中&#xff0c;我搬出了我的个人掘金账号写在了简历里&#xff0c;面试官很感兴趣&#xff0c;他不仅关注了我的账号&#xff0c;还想让我写一篇《原型链》的见解&#xff0c;由于老早就想总结一篇关于原型的文章&#xff0c;奈何自己刚开…

07平衡负载:gRPC是如何进行负载均衡的?

负载均衡(Load Balance),其含义就是指将请求负载进行平衡、分摊到多个负载单元上进行运行,从而协同完成工作任务。 负载均衡的主要作用: 提升并发性能:负载均衡通过算法尽可能均匀的分配集群中各节点的工作量,以此提高集群的整体的吞吐量。 提供可伸缩性:可添加或减少服…

Springboot新手开发 Cloud篇

前言&#xff1a; &#x1f44f;作者简介&#xff1a;我是笑霸final&#xff0c;一名热爱技术的在校学生。 &#x1f4dd;个人主页&#xff1a;个人主页1 || 笑霸final的主页2 &#x1f4d5;系列专栏&#xff1a;后端专栏 &#x1f4e7;如果文章知识点有错误的地方&#xff0c;…

汇编语言与微机原理(1)基础知识

前言&#xff08;1&#xff09;本人使用的是王爽老师的汇编语言第四版和学校发的微机原理教材配合学习。&#xff08;2&#xff09;推荐视频教程通俗易懂的汇编语言&#xff08;王爽老师的书&#xff09;&#xff1b;贺老师C站账号网址&#xff1b;&#xff08;3&#xff09;文…