红黑树

一、红黑树用在哪里

  • HashMap。
  • Linux 进程调度 CFS。
  • Epoll 事件块的管理。
  • Nginx Timer 事件管理。
  • （key，value）的形式，并且中序遍历是顺序的，红黑树是二叉排序树。

二、红黑树性质

  • 每个节点是红色或者黑色。
  • 根节点是黑色的。
  • 所有叶子节点都隐藏，并且为黑色。
  • 如果一个节点是红色的，则它的两个儿子都是黑色的 → 红色节点不相邻。
  • 对每个节点，从该节点到其子孙节点的所有路径上的包含相同数目的黑节点 → 黑色节点高度一样。
    • 从根节点到叶子节点的最大深度和最小深度的关系是 2n - 1 : n

在这里插入图片描述

三、红黑树代码

typedef struct _rbtree_node {
    int key;
    void *value;
    
    struct _rbtree_node *right;
    struct _rbtree_node *left;
    struct _rbtree_node *parent;
    
    unsigned char color;
} rbtree_node;

struct _rbtree {
    struct _rbtree_node root;
    struct _rbtree_node *nil; // 所有叶子节点都隐藏，并且为黑色
} rbtree;

// 改进（如果一个结构体里有多棵红黑树）
// 减少冗余代码
#define RBTREE_ENTRY(name, type) 
    struct name {
        struct type *right;
        struct type *left;
        struct type *parent;
        unsigned char color;
    }
    
typedef int KEY_TYPE;

typedef struct _my_thread{
     KEY_TYPE key;
     void *value;
     
     RBTREE_ENTRY(, _my_thread) ready;
     RBTREE_ENTRY(, _my_thread) wait;
     RBTREE_ENTRY(, _my_thread) sleep;
     RBTREE_ENTRY(, _my_thread) exit;
} my_thread;

四、红黑树旋转

  • 当红黑树性质被破坏的时候，需要调整 → 左旋，右旋。
  • 红黑树的插入或者删除最多旋转树的高度次就可以达到平衡。

在这里插入图片描述
在这里插入图片描述

void rbtree_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){ // x 为根节点
        T->root = y;
    } else if (x == x->parent->left) {
        x->parent->left = y;
    } else {
        x->parent->right = y;
    }
    // 第三步
    y->left = x;
    x->parent = y;
}

void rbtree_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->parentl;
    if (y->parent == T->nil) { // y 为根节点
        T->root = x;
    } else if (y == y->parent->right) {
        y->parent->right= x; 
    } else {
        y->parent->left= x;
    }
    
    x->right = y;
    y->parent = x;
}

五、红黑树插入

  • 红黑树在插入节点以前，它已经是一棵红黑树了。
  • 插入节点上色为红色，因为不会改变黑色节点高度
  • 父节点是祖父节点的左子树

    • 叔节点是红色的。
      在这里插入图片描述

    • 叔节点是黑色的，并且当前节点是右子树。
      在这里插入图片描述

    • 叔节点是黑色的，并且当前节点是左子树。
      在这里插入图片描述

#define RED 0
#define BLACK 1

void rbtree_insert_fixup(rbtree *T, rbtree_node *z) {
    while (z->parent->color == RED) { //z ---> 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; //z --> RED
            } else {

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

                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                rbtree_right_rotate(T, z->parent->parent);
            }
        } else {
            rbtree_node *y = z->parent->parent->left;
            if (y->color == RED) {
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;

                z = z->parent->parent; //z --> RED
            } else {
                if (z == z->parent->left) {
                    z = z->parent;
                    rbtree_right_rotate(T, z);
                }

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

    T->root->color = BLACK;
}

void rbtree_insert(rbtree *T, rbtree_node *z) {

    rbtree_node *y = T->nil;
    rbtree_node *x = T->root;

    while (x != T->nil) {
        y = x;
        if (z->key < x->key) {
            x = x->left;
        } else if (z->key > x->key) {
            x = x->right;
        } else { //Exist 由业务场景决定
            return ;
        }
    }

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

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

    rbtree_insert_fixup(T, z);
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define RED             1
#define BLACK           2

typedef int KEY_TYPE;

typedef struct _rbtree_node {
    unsigned char color;
    struct _rbtree_node *right;
    struct _rbtree_node *left;
    struct _rbtree_node *parent;
    KEY_TYPE key;
    void *value;
} rbtree_node;

typedef struct _rbtree {
    rbtree_node *root;
    rbtree_node *nil;
} rbtree;

rbtree_node *rbtree_mini(rbtree *T, rbtree_node *x) {
    while (x->left != T->nil) {
        x = x->left;
    }
    return x;
}

rbtree_node *rbtree_maxi(rbtree *T, rbtree_node *x) {
    while (x->right != T->nil) {
        x = x->right;
    }
    return x;
}

rbtree_node *rbtree_successor(rbtree *T, rbtree_node *x) {
    rbtree_node *y = x->parent;

    if (x->right != T->nil) {
        return rbtree_mini(T, x->right);
    }

    while ((y != T->nil) && (x == y->right)) {
        x = y;
        y = y->parent;
    }
    return y;
}

void rbtree_left_rotate(rbtree *T, rbtree_node *x) {

    rbtree_node *y = x->right;  // x  --> y  ,  y --> x,   right --> left,  left --> right

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

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

    y->left = x; //1 5
    x->parent = y; //1 6
}

void rbtree_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->right) {
        y->parent->right = x;
    } else {
        y->parent->left = x;
    }

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

void rbtree_insert_fixup(rbtree *T, rbtree_node *z) {

    while (z->parent->color == RED) { //z ---> 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; //z --> RED
            } else {

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

                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                rbtree_right_rotate(T, z->parent->parent);
            }
        }else {
            rbtree_node *y = z->parent->parent->left;
            if (y->color == RED) {
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;

                z = z->parent->parent; //z --> RED
            } else {
                if (z == z->parent->left) {
                    z = z->parent;
                    rbtree_right_rotate(T, z);
                }

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

    T->root->color = BLACK;
}

void rbtree_insert(rbtree *T, rbtree_node *z) {

    rbtree_node *y = T->nil;
    rbtree_node *x = T->root;

    while (x != T->nil) {
        y = x;
        if (z->key < x->key) {
            x = x->left;
        } else if (z->key > x->key) {
            x = x->right;
        } else { //Exist
            return ;
        }
    }

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

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

    rbtree_insert_fixup(T, z);
}

void rbtree_delete_fixup(rbtree *T, rbtree_node *x) {

    while ((x != T->root) && (x->color == BLACK)) {
        if (x == x->parent->left) {

            rbtree_node *w= x->parent->right;
            if (w->color == RED) {
                w->color = BLACK;
                x->parent->color = RED;

                rbtree_left_rotate(T, x->parent);
                w = x->parent->right;
            }

            if ((w->left->color == BLACK) && (w->right->color == BLACK)) {
                w->color = RED;
                x = x->parent;
            } else {

                if (w->right->color == BLACK) {
                    w->left->color = BLACK;
                    w->color = RED;
                    rbtree_right_rotate(T, w);
                    w = x->parent->right;
                }

                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->right->color = BLACK;
                rbtree_left_rotate(T, x->parent);

                x = T->root;
            }

        } else {

            rbtree_node *w = x->parent->left;
            if (w->color == RED) {
                w->color = BLACK;
                x->parent->color = RED;
                rbtree_right_rotate(T, x->parent);
                w = x->parent->left;
            }

            if ((w->left->color == BLACK) && (w->right->color == BLACK)) {
                w->color = RED;
                x = x->parent;
            } else {

                if (w->left->color == BLACK) {
                    w->right->color = BLACK;
                    w->color = RED;
                    rbtree_left_rotate(T, w);
                    w = x->parent->left;
                }

                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->left->color = BLACK;
                rbtree_right_rotate(T, x->parent);

                x = T->root;
            }

        }
    }

    x->color = BLACK;
}

rbtree_node *rbtree_delete(rbtree *T, rbtree_node *z) {

    rbtree_node *y = T->nil;
    rbtree_node *x = T->nil;

    if ((z->left == T->nil) || (z->right == T->nil)) {
        y = z;
    } else {
        y = rbtree_successor(T, z);
    }

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

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

    if (y != z) {
        z->key = y->key;
        z->value = y->value;
    }

    if (y->color == BLACK) {
        rbtree_delete_fixup(T, x);
    }

    return y;
}

rbtree_node *rbtree_search(rbtree *T, KEY_TYPE key) {

    rbtree_node *node = T->root;
    while (node != T->nil) {
        if (key < node->key) {
            node = node->left;
        } else if (key > node->key) {
            node = node->right;
        } else {
            return node;
        }   
    }
    return T->nil;
}

void rbtree_traversal(rbtree *T, rbtree_node *node) {
    if (node != T->nil) {
        rbtree_traversal(T, node->left);
        printf("key:%d, color:%d\n", node->key, node->color);
        rbtree_traversal(T, node->right);
    }
}

int main() {

    int keyArray[20] = {24,25,13,35,23, 26,67,47,38,98, 20,19,17,49,12, 21,9,18,14,15};

    rbtree *T = (rbtree *)malloc(sizeof(rbtree));
    if (T == NULL) {
        printf("malloc failed\n");
        return -1;
    }
    
    T->nil = (rbtree_node*)malloc(sizeof(rbtree_node));
    T->nil->color = BLACK;
    T->root = T->nil;

    rbtree_node *node = T->nil;
    int i = 0;
    for (i = 0;i < 20;i ++) {
        node = (rbtree_node*)malloc(sizeof(rbtree_node));
        node->key = keyArray[i];
        node->value = NULL;

        rbtree_insert(T, node);
        
    }

    rbtree_traversal(T, T->root);
    printf("----------------------------------------\n");

    for (i = 0;i < 20;i ++) {

        rbtree_node *node = rbtree_search(T, keyArray[i]);
        rbtree_node *cur = rbtree_delete(T, node);
        free(cur);

        rbtree_traversal(T, T->root);
        printf("----------------------------------------\n");
    }
}

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

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

相关文章

Mybatis进阶3--注解开发

Mybatis进阶3--注解开发

先看&#xff1a; Mybatis进阶1-CSDN博客 Mybatis进阶2-CSDN博客 mybatis注解开发 前置&#xff1a;不需要xxxMapper..xml文件&#xff08;映射文件&#xff09; 在核心配置文件中&#xff1a;<mappers>标签只能使用&#xff1a;<package name"扫描的包&quo…
阅读更多...
open-webui+ollama本地部署Llama3

open-webui+ollama本地部署Llama3

前言 Meta Llama 3 是由 Meta 公司发布的下一代大型语言模型&#xff0c;拥有 80 亿和 700 亿参数两种版本&#xff0c;号称是最强大的开源语言模型。它在多个基准测试中超越了谷歌的 Gemma 7B 和 Mistral 7B Instruct 模型。 安装 1.gpt4all https://github.com/nomic-ai/…
阅读更多...
记一次动态规划的采坑之旅， 741摘樱桃 https://leetcode.cn/problems/cherry-pickup/description/

记一次动态规划的采坑之旅， 741摘樱桃 https://leetcode.cn/problems/cherry-pickup/description/

首次看题目时&#xff0c;发现是困难。立马想到了&#xff0c;动态规划。 再看题目&#xff0c; 摘樱桃&#xff0c;还要返回摘两次&#xff0c;求摘最多的樱桃。 大脑第一反应就是&#xff1a; 先使用动态规划&#xff0c;找到 0 0 到 n-1 n-1处走过的最大樱桃&#xff0c; 并…
阅读更多...
【码银送书第十九期】《图算法：行业应用与实践》

【码银送书第十九期】《图算法：行业应用与实践》

作者&#xff1a;嬴图团队 01 前言 在当今工业领域&#xff0c;图思维方式与图数据技术的应用日益广泛&#xff0c;成为图数据探索、挖掘与应用的坚实基础。本文旨在分享嬴图团队在算法实践应用中的宝贵经验与深刻思考&#xff0c;不仅促进业界爱好者之间的交流&#xff0c;…
阅读更多...
AI不只是技术，更是一种思维方式

AI不只是技术，更是一种思维方式

一、AI思维 1.个人&#xff1a;提升自己的综合能力&#xff0c;成为一名懂技术、懂设计、懂硬件、懂市场运营等知识的综合型人才 2.数据&#xff1a;从全局视角看数据流向&#xff0c;挖掘数据价值 3.产品&#xff1a;运用新技术&#xff0c;发掘新需求点&#xff0c;探索产…
阅读更多...
AI智体的分级：从基于规则到基于LLM

AI智体的分级：从基于规则到基于LLM

摘要&#xff1a; AI智体被定义为感知环境、做出决策和采取行动的人工实体。受SAE&#xff08;汽车工程师学会&#xff09;自动驾驶6个级别的启发&#xff0c;AI智体也根据效用和强度进行分类&#xff0c;分为以下几个级别&#xff1a;L0——无AI&#xff0c;有工具&#xff0…
阅读更多...
马常旭新歌《如愿》：音乐界的“旭日”再现

马常旭新歌《如愿》：音乐界的“旭日”再现

在这个春暖花开的季节&#xff0c;音乐界又迎来了一股清新的“旭日”气息。是的&#xff0c;就在2024年4月17日&#xff0c;马常旭的新歌《如愿》&#xff08;旭日版&#xff09;在网易云音乐上线了&#xff01;一年的等待&#xff0c;终于迎来了他的音乐回归&#xff0c;给我们…
阅读更多...
C语言知识点补充——ASCLL码表

C语言知识点补充——ASCLL码表

1、ASCLL码表 ASCII码表&#xff08;American Standard Code for Information Interchange&#xff09;是一种用于将字符编码为数字的标准。它定义了128个字符的编码方式&#xff0c;包括数字、字母、标点符号和控制字符等。每个字符都对应一个唯一的7位或8位二进制数 2、Ascl…
阅读更多...
贪吃蛇项目（小白保姆级教程）

贪吃蛇项目（小白保姆级教程）

游戏介绍 游戏背景&#xff1a; 贪吃蛇游戏是经典的游戏项目之一&#xff0c;也是很简单的小游戏 实现背景&#xff1a; 这里我们是基于32位的Win32_API进行实现的 需要的知识点&#xff1a; C语言函数、枚举、结构体、动态内存管理、预处理指令、链表、Win32_API等 适合人群&a…
阅读更多...
java中的字符串（String）常量池理解

java中的字符串（String）常量池理解

下面创建String对象的方式一样吗&#xff1f; 上述程序创建对象类似&#xff0c;为什么s1和s2引用对象一样&#xff0c;但是s3和s4不一样呢&#xff1f; 在java程序中&#xff0c;许多基本类型的字面常量会经常用到&#xff0c;例如2,3.11&#xff0c;“hyy”等。为了提升程序…
阅读更多...
C语言动态内存管理malloc、calloc、realloc、free函数、内存泄漏、动态内存开辟的位置等的介绍

C语言动态内存管理malloc、calloc、realloc、free函数、内存泄漏、动态内存开辟的位置等的介绍

文章目录 前言一、为什么存在动态内存管理二、动态内存函数的介绍1. malloc函数2. 内存泄漏3. 动态内存开辟位置4. free函数5. calloc 函数6. realloc 函数7. realloc 传空指针 总结 前言 C语言动态内存管理malloc、calloc、realloc、free函数、内存泄漏、动态内存开辟的位置等…
阅读更多...
25.哀家要长脑子了---哈希表

25.哀家要长脑子了---哈希表

1.525. 连续数组 - 力扣&#xff08;LeetCode&#xff09; 在我对通义千问的一番折磨下&#xff0c;终于弄清楚一点点了。哈希表存储前缀和数组值 用一个counter来记录nums中0、1数量差值的变化。 哈希表map存储某个特定的counter值首次出现的位置。counter的计算&#xff1a;…
阅读更多...
【LeetCode 121】买卖股票的最佳时机

【LeetCode 121】买卖股票的最佳时机

思路 思路&#xff1a; 所谓代码的复杂性来源于业务的复杂性&#xff0c;如果能够想清楚业务实现逻辑&#xff0c;就能够轻松写出代码&#xff1b; 假设当前是第i天&#xff0c;如何在第i天赚到最多的钱&#xff1f;需要在第i天之前以最低价买入股票&#xff1b; 所以需要求…
阅读更多...
13 【PS作图】人物绘画理论-脸型

13 【PS作图】人物绘画理论-脸型

三庭五眼 三庭&#xff1a;脸的长度比例 &#xff08;1&#xff09;发际线到眉毛 &#xff08;2&#xff09;眉毛到鼻底 &#xff08;3&#xff09;鼻底到下巴 三个部分大致为三等分 五眼&#xff1a;脸的宽度比例 以眼睛长度为单位&#xff0c;把脸的宽度分成五等分&#x…
阅读更多...
[极客大挑战 2019]PHP

[极客大挑战 2019]PHP

1.通过目录扫描找到它的备份文件&#xff0c;这里的备份文件是它的源码。 2.源码当中涉及到的关键点就是魔术函数以及序列化与反序列化。 我们提交的select参数会被进行反序列化&#xff0c;我们要构造符合输出flag条件的序列化数据。 但是&#xff0c;这里要注意的就是我们提…
阅读更多...
求解亲和数

求解亲和数

【问题描述】 古希腊数学家毕达哥拉斯在自然数研究中发现&#xff0c;220的所有真约数&#xff08;即不是自身 的约数&#xff09;之和为&#xff1a; 1245101120224455110284。而284的所有真约数为1、2、4、71、142&#xff0c;加起来恰好为220。人 们对这样的数感到很惊奇&am…
阅读更多...
五种主流数据库：窗口函数

五种主流数据库：窗口函数

SQL 窗口函数为在线分析系统&#xff08;OLAP&#xff09;和商业智能&#xff08;BI&#xff09;提供了复杂分析和报表统计的功能&#xff0c;例如产品的累计销量统计、分类排名、同比/环比分析等。这些功能通常很难通过聚合函数和分组操作来实现。 本文比较了五种主流数据库实…
阅读更多...
嵌入式学习67-C++（多线程，自定义信号合槽，串口通信）

嵌入式学习67-C++（多线程，自定义信号合槽，串口通信）

知识零碎&#xff1a; QmessageBox 报错提示框 GPS传感器获取到的 经纬度信息并不是真实的物理坐标&#xff0c;还需要转换 signals&#xff1a; …
阅读更多...
【JAVA入门】Day03 - 数组

【JAVA入门】Day03 - 数组

【JAVA入门】Day03 - 数组 文章目录 【JAVA入门】Day03 - 数组一、数组的概念二、数组的定义2.1 数组的静态初始化2.2 数组的地址值2.3 数组元素的访问2.4 数组遍历2.5 数组的动态初始化2.6 数组的常见操作2.7 数组的内存分配2.7.1 Java内存分配2.7.2 数组的内存图 一、数组的概…
阅读更多...
234234235

234234235

c语言中的小小白-CSDN博客c语言中的小小白关注算法,c,c语言,贪心算法,链表,mysql,动态规划,后端,线性回归,数据结构,排序算法领域.https://blog.csdn.net/bhbcdxb123?spm1001.2014.3001.5343 给大家分享一句我很喜欢我话&#xff1a; 知不足而奋进&#xff0c;望远山而前行&am…
阅读更多...
最新文章

Copyright @ 2022~2023