数据结构—(链表，栈，队列，树)

链表（Linked List） 是一种线性数据结构，由一系列节点（Node）通过指针链接而成。与数组不同，链表的元素在内存中非连续存储，每个节点独立分配内存

类型 方向性 内存开销 适用场景
单向链表单向低简单数据管理（如栈、队列）
双向链表双向高（2指针）频繁双向遍历（如浏览器历史记录）
循环链表环状同单向/双向轮询任务、循环缓冲区
静态链表单向/双向固定数组无动态内存环境（如嵌入式开发）

单向链表：

实现栈（LIFO）、队列（FIFO）。

轻量级数据集合管理（如学生成绩表）。

双向链表：

浏览器前进/后退功能。

文本编辑器的撤销/重做操作。

循环链表：

操作系统进程调度（时间片轮转）。

音乐播放器的循环播放列表。

静态链表：

内存受限的嵌入式系统。

预分配固定内存池的实时系统。

（此处重点且详细的说双向列表，双向列表会了之后，其余两个也就差不多了）

类型	方向性	内存开销	适用场景
单向链表	单向	低	简单数据管理（如栈、队列）
双向链表	双向	高（2指针）	频繁双向遍历（如浏览器历史记录）
循环链表	环状	同单向/双向	轮询任务、循环缓冲区
静态链表	单向/双向	固定数组	无动态内存环境（如嵌入式开发）

1. 单向链表

结构定义

每个节点包含 数据域 和 指向下一个节点的指针。

C语言结构体：
typedef struct SNode {
    int data;               // 数据域
    struct SNode *next;     // 指向下一节点的指针
} SNode;
特点：

单向遍历，只能从头节点开始访问后续节点。

插入/删除操作需定位前驱节点。

示例操作：
// 在头节点后插入新节点
void insertAtHead(SNode **head, int val) {
    SNode *newNode = (SNode*)malloc(sizeof(SNode));
    newNode->data = val;
    newNode->next = *head;
    *head = newNode;
}

2. 双向链表

结构定义

每个节点包含 数据域、指向前驱节点的指针 和 指向后继节点的指针。

C语言结构体：
typedef struct linked_list_node
{
  // 节点数据
  void *data; // 8位
  // pre节点指针，指向的是前一个节点 8位
  struct linked_list_node *prev;

  // next指针指向的是下一个节点 8位
  struct linked_list_node *next;

} node;

// 2.定义链表-结构体,此结构点表示的是
typedef struct
{
  // 头结点
  node *head;
  // 尾节点
  node *tail;
  // 节点的个数
  int size;

} linked_list;
特点：

支持双向遍历（从头到尾或从尾到头）。

插入/删除操作更高效（可直接访问前驱和后继）。

双向链表的操作（c语言）

包含了前插插入，后插插入，中间插入，删除，查找等等

1. linked_list_common.h

#ifndef LINKED_LIST_COMMON
#define LINKED_LIST_COMMON

/*
  双向链表结构

  节点表示

  首节点  前去节点 数据 后区节点

*/

// 节点声明，数据在次结构体，总体长度为24
typedef struct linked_list_node
{
  // 节点数据
  void *data; // 8位
  // pre节点指针，指向的是前一个节点 8位
  struct linked_list_node *prev;

  // next指针指向的是下一个节点 8位
  struct linked_list_node *next;

} node;

// 2.定义链表-结构体,此结构点表示的是
typedef struct
{
  // 头结点
  node *head;
  // 尾节点
  node *tail;
  // 节点的个数
  int size;

} linked_list;

// 3.创建一个节点需要自己开辟空间，即使用上的nide指针的
node *create_node(void *data);

// 4.初始化链表
void init_linked_list(linked_list *list);

// 中间插入
void insert_after(linked_list *list, node *prev, void *data);

// 人为规定当前案例 都放入int类型数据
// 整数int类型比较函数
int compare_int(void *a, void *b);

// 添加 prepend 和 append 的声明
void prepend(linked_list *list, void *data);
void append(linked_list *list, void *data);

// 在链表中查找特定数据的节点，插入必须先查找对应的节点
node *search_node(linked_list *list, void *data, int (*compare)(void *, void *));

// 示例：打印int数据链表的内容
void print_int_linked_list(linked_list *list);

// 删除节点，进行三次判断，判断是否为头节点，判断是否为节点，否则就是中间节点，然后写出每个删除的逻辑
// 逻辑结束后，释放所被删除的内存空间
void delete_node(linked_list *linked, node *node);

// last.清空链表
void clean_linked_list(linked_list *list);

#endif

2. link.c

#include <stdio.h>
#include <stdlib.h>
#include "../inc/linked_list_common1.h"

/*
   在此处定义
*/
// 1.创建一个节点需要自己开辟空间，即使用上的nide指针的
node *create_node(void *data)
{
    // 创建空间，准备存取数据，别忘记了释放空间
    // calloc(1, sizeof(node))由于calloc创建的是一个没有类型的类型的数据，需要给强转成相对应的类型嗯
    node *new_node = (node *)calloc(1, sizeof(node));
    // 如果内存无法开辟，即没有足够大的空间，会导致开辟失败
    if (new_node == NULL)
    {
        printf("内存溢出，创建节点失败\n");
        exit(EXIT_FAILURE); // 异常退出
    }
    // 如果空间可以开辟，则使用结构体指针将其赋初始值
    new_node->data = data;
    new_node->prev = NULL;
    new_node->next = NULL;

    return new_node;
}

// 2.初始化链表，因为暂时没有数据
void init_linked_list(linked_list *list)
{
    // 头结点
    list->head = NULL;
    // 尾节点
    list->tail = NULL;
    // 链表的节点个数
    list->size = 0;
}
// 7.在链表的中间插入节点。三个参数，即为，列表，前驱节点为参数，和数据
void insert_after(linked_list *list, node *prev, void *data)
{
    // 上一个节点的pre指向上上个数据，next指向下一个数据，要在中间插入一个数据的话，既要改变上一个节点的next，也要改变下一个节点的prev
    // 即在于找到一个prev即可找到上一个节点的next
    //  7.1判断要插入的prev的节点是否为null，没有的话，找不到前一个数据，无法插入
    if (prev == NULL)
    {
        printf("前驱节点不能为NULL...\n");
        return; // 结束程序
    }
    // 7.2创建新节点 ，此节点就是要被插入的节点，
    node *new_node = create_node(data);
    // 7.3 修改新节点的prev和next指针，修改新节点的直接前驱指针，新节点的直接后继指针为 直接前驱的next
    new_node->prev = prev;
    new_node->next = prev->next;
    // 7.4 prev为尾节点，更新新节点为新的尾节点
    if (prev->next == NULL)
    {
        list->tail = new_node;
    }
    else
    {
        // prev不是尾节点,更新prev旧的后继节点的prev指针指向新节点
        prev->next->prev = new_node;
    }
    // 设置prev的next指针指向新节点
    prev->next = new_node;
    // 链表节点个数+1
    list->size++;
}

// 在链表头部插入数据
void prepend(linked_list *list, void *data)
{
    node *new_node = create_node(data);
    if (list->head == NULL)
    {
        // 如果链表为空，头尾节点都指向新节点
        list->head = new_node;
        list->tail = new_node;
    }
    else
    {
        // 链表非空，更新头节点
        new_node->next = list->head;
        list->head->prev = new_node;
        list->head = new_node;
    }
    list->size++;
}

// 在链表尾部插入数据
void append(linked_list *list, void *data)
{
    node *new_node = create_node(data);
    if (list->tail == NULL)
    {
        // 如果链表为空，头尾节点都指向新节点
        list->head = new_node;
        list->tail = new_node;
    }
    else
    {
        // 链表非空，更新尾节点
        new_node->prev = list->tail;
        list->tail->next = new_node;
        list->tail = new_node;
    }
    list->size++;
}

// 人为规定当前案例 都放入int类型数据
// 整数int类型比较函数
int compare_int(void *a, void *b)
{
    // 比较数值相减是否为0，0则表示相同
    return *(int *)a - *(int *)b;
}

// 在链表中查找特定数据的节点，插入必须先查找对应的节点,容纳后才能执行中间插入操作，
// 即必须要知道前一个节点的位置，即他的prev
node *search_node(linked_list *list, void *data, int (*compare)(void *, void *))
{
    // 首先必须要从list的head开始遍历，此处名称为迭代,先获取list的head的节点
    node *current = list->head;
    // 遍历列表，查找节点
    while (current != NULL)
    {
        // 比较函数返回0，表示两个值相等
        if (compare(current->data, data) == 0)
        {
            // 返回找到的节点
            return current;
        }
        // 继续比较下一个节点
        current = current->next;
    }
    // 如果循环结束都没有找到数据对应的节点，说明该链表不存在该数据
    return NULL;
}

// 示例：打印int数据链表的内容，全部内容，其作用与查找节点一样
void print_int_linked_list(linked_list *list)
{
    // 获取头结点
    node *current = list->head;
    printf("双向链表内容：\n");
    // 迭代器遍历
    while (current != NULL)
    {
        printf("%d ", *(int *)current->data);
        // 继续下一个
        current = current->next;
    }
    printf("\n");
    printf("此时链表总共有%d个节点\n", list->size);
}

// 删除节点，此处有带商榷
void delete_node(linked_list *list, node *node)
{
    // 判断节点不能为空
    if (node == NULL)
    {
        printf("节点不能为空\n");
        return;
    }

    // 判断是否为头节点
    if (node == list->head)
    { // 如果是头节点，则使其下一个节点的
        list->head = node->next;
        if (list->head != NULL)
        {
            list->head->prev = NULL;
        }
        else
        {
            // 如果删除后链表为空，更新尾节点
            list->tail = NULL;
            printf("本次删除的为头节点%d\n", *(int *)node->data);
        }
    }
    // 判断是否为尾节点
    else if (node == list->tail)
    {
        list->tail = node->prev;

        if (list->tail != NULL)
        {
            list->tail->next = NULL;
        }
        else
        {
            // 如果删除后链表为空，更新头节点
            list->head = NULL;
            printf("本次删除的为尾节点%d\n", *(int *)node->data);
        }
    }
    // 中间节点
    else
    {
        node->prev->next = node->next;
        node->next->prev = node->prev;
        printf("本次删除的为中部节点%d\n", *(int *)node->data);
    }

    // 释放节点内存
    free(node);
    list->size--;
}

// last.清空链表
void clean_linked_list(linked_list *list)
{
    // 获取头结点，先用上一个节点找到下一个节点，然后删除上一个节点
    node *current = list->head;
    // 迭代器  获取节点，释放节点空间 利用迭代循环找到节点释放空间
    while (current != NULL)
    {
        // 头结点不为Null
        node *temp = current;
        // 获取下一个节点
        current = current->next;
        // 释放节点的内存空间
        free(temp);
    }
    // 头结点
    list->head = NULL;
    // 尾节点
    list->tail = NULL;
    // 链表的节点个数
    list->size = 0;
}

3. main.c

#include <stdio.h>
#include <stdlib.h>
#include "../inc/linked_list_common1.h"

int main(int argc, char const *argv[])
{
    // 1.初始化链表
    linked_list list; // 声明开辟内存
    init_linked_list(&list);

    // 2.在链表头部插入数据
    int a = 10, b = 20, c = 30;
    prepend(&list, &a);
    prepend(&list, &b);
    prepend(&list, &c);
    // 打印
    print_int_linked_list(&list);

    // 3.在链表尾部插入数据
    int e = 40, f = 50;
    append(&list, &e);
    append(&list, &f);
    // 打印
    print_int_linked_list(&list);

    // 4.在链表中间插入数据
    // 4.1查找某个节点
    int g = 60;
    node *prev = search_node(&list, &c, compare_int);
    insert_after(&list, prev, &g);
    // 打印
    print_int_linked_list(&list);

    // 删除节点
    // 查找要删除的节点，
    node *target_node = search_node(&list, &a, compare_int);
    if (target_node != NULL)
    {
        delete_node(&list, target_node);
    }
    else
    {
        printf("未找到要删除的节点\n");
    }
    print_int_linked_list(&list);

    // last.清空链表
    clean_linked_list(&list);
    return 0;
}

3. 循环列表

特点：

无明确的头尾界限，适合循环访问场景（如轮询调度）。

1. 单向循环列表

结构定义

单向循环链表：尾节点的 next 指针指向头节点。

2. 双向循环列表

结构定义

双向循环链表：头节点的 prev 指向尾节点，尾节点的 next 指向头节点。

4. 静态链表

结构定义

使用数组模拟链表，节点通过数组下标链接。

特点：

无需动态内存分配，适用于不支持指针的环境（如嵌入式系统）。

内存固定，无法动态扩展。

二栈（stack）(代码暂不演示）

定义：后进先出（LIFO）的线性结构，仅允许在栈顶操作。
核心操作：

push：入栈。

pop：出栈。

peek：查看栈顶元素。

队列，和栈比较相似，特殊的线性表（执行先进先出，谁头谁尾，有待商榷）

循环队列：

链式队列：数据与指针域

需要根据结构图来重新模拟一下结构体的创建的理念

首先明白一点，我大概都懂他们的逻辑结构关系，我也知道他们的指针其什么作用

1.明白队列的物理结构关系

2.根据物理结构关系来定义结构体（结构体为何有两个，两个分别是什么作用，为和不创建一个）

3.根据物理结构来定义这个数据结构，使用函数写出，让这个链表成为队列，即数据结构在c语言中并不是一种真正的结构，而是人为定义的，因为人类需要使用这种结构，例如现实问题，排队进游乐场等等

三队列(queue) (代码暂不演示）

定义：先进先出（FIFO）的线性结构，队尾插入，队头删除。
核心操作：

enqueue：入队。

dequeue：出队。

front：查看队头元素。

重难点：

栈空判断：出栈前必须检查 top 是否为 NULL（否则导致未定义行为）。

内存安全：出栈后必须释放节点内存。

应用场景：

函数调用栈（递归实现）。

括号匹配、表达式求值。

结构体：
// 1.定义队列中节点的
typedef struct queue_node
{
  // 数据域
  void *data;
  // 指针域
  struct queue_node *next;
} node;

// 2.定义队列的结构体
typedef struct
{
  // 对首节点
  node *front;
  // 对尾节点
  node *rear;
  // 队列中节点的个数
  int size;
} queue;

四树（tree）

树（Tree）是一种非线性数据结构，由节点（Node）和边（Edge）组成，满足以下条件：

每个树有且仅有一个根节点（Root）。

除根节点外，每个节点有且仅有一个父节点。

从根节点到任意节点有唯一路径。

1. 二叉树（Binary Tree）

定义：每个节点最多有 2 个子节点（左和右）。

特点：结构简单，适合递归操作。

应用：表达式树、哈夫曼编码。

C 代码结构：
typedef struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

2. 二叉搜索树（BST）

定义：左子树所有节点值 < 根节点值 < 右子树所有节点值。

特点：中序遍历结果为有序序列。

应用：动态数据排序、字典。

插入代码：
TreeNode* insertBST(TreeNode* root, int val) {
    if (root == NULL) {
        TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
        node->data = val;
        node->left = node->right = NULL;
        return node;
    }
    if (val < root->data) 
        root->left = insertBST(root->left, val);
    else 
        root->right = insertBST(root->right, val);
    return root;
}

3. AVL 树

定义：平衡二叉搜索树，任意节点左右子树高度差 ≤ 1。

特点：通过旋转（左旋/右旋）保持平衡。

应用：数据库索引、实时高频查询。

结构扩展：
typedef struct AVLNode {
    int data;
    int height;
    struct AVLNode *left, *right;
} AVLNode;

4. B 树

定义：多路平衡搜索树，每个节点可包含多个键和子节点。

特点：减少磁盘 I/O，适合大规模数据。

应用：文件系统、数据库存储。

5. 红黑树

定义：自平衡二叉搜索树，通过颜色标记和规则保持平衡。

特点：插入/删除效率高，广泛用于库函数（如 C++ STL）。

规则：

节点是红或黑。

根和叶子（NIL）是黑。

红节点的子节点必为黑。（即红不能连续）

任意节点到叶子的路径包含相同数量黑节点。

    1.节点颜色：每个节点都是红色或黑色。
    2.根节点：根节点必须是黑色。
    3.叶子节点：所有的叶子节点（即空节点）都是黑色。
    4.红色节点的约束：红色节点的子节点必须是黑色（即红色节点不能有红色子节点）。
    5.黑色节点的平衡：从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。

这些特性确保了红黑树的平衡性，使得其在最坏情况下的时间复杂度仍然保持在 O(logN)。具体来说，红黑树通过以下方式实现自平衡：

1. red_black_common.h

#ifndef RED_BLACK_COMMON_H
#define RED_BLACK_COMMON_H

// 使用枚举 定义节点颜色
typedef enum
{
    RED,
    BLACK
} node_color;

// 定义树，包含根节点，哨兵节，因为根节点与哨兵节点没有继续分支所以，树的结构体只包含两个数据
// 由于普通的节点，还有数据存在，即为令起一个结构体存放
typedef struct red_black_tree_common
{
    // 根节点
    tree_node *root_node;
    // 哨兵节点
    tree_node *nil_node;

} tree;

// 定义树的节点，普通树节点分为数据，左右子结点，及其这个节点的父节点（父节点有可能是根节点），节点颜色，
typedef struct tree_node
{
    // 1.数据域
    void *data;
    // 2.节点的颜色
    node_color color;
    // 3.父节点
    struct rb_tree_node *parent;
    // 4.左子节点
    struct rb_tree_node *left_child;
    // 5.右子节点
    struct rb_tree_node *right_child;
} tree_node;

// 4.创建一个新的红黑树节点，新节点默认为红色，左右子节点和父节点都指向哨兵节点
// 定义树，返回值为树节点的指针类型，参数为tree指针，与数据指针
tree_node *create_node(tree *tree, void *data);

// 5.初始化一棵空树，根节点为nil，并且哨兵节点颜色为黑色(最下面的叶子节点)
// 创建一个空树，空树只包含根节点与哨兵节点
tree *create_rb_tree();
/*
  左旋右旋，这层代码还是简单的，我想执导的是左右转的目的是什么，或者说在现实世界的应用情况
  在什么情况下可以用到左右旋？----在修复的时候用得到，要维护红黑树的平衡及规则

  左右旋转，先维护x与y的关系，即谁是谁的分支，重新定义x与y的双向关系
  1.先判断子结点
  上升的的节点与源节点的子关系，上升节点的分支与源节点的子关系
  2.判断父关系
（分支节点的的父节点）上升节点的某个分支不为哨兵节点的话，则判断其分支节点的指向为源节点（认爹）y->left_child->parent=x;
  x与y的关系有三种可能性
  1.x（源节点）为根节点，判断(x->parent==tree->nil_node)，则y就等于根节点，即tree->root_node=y;
  2.即x不是根节点，判断x是其父节点的那个位置的节点，然后执行x->parent->left_child=y;
  3.另一个节点一样
*/

// last1.释放节点
// 释放树节点的空间
void free_tree(tree *tree, tree_node *node);

// last2.释放树
// 释放树的空间
void destroy_tree(tree *tree);

#endif

2. red_black_tree.c

#include <stdio.h>
#include <stdlib.h>
#include "../inc/rb_tree_common.h"

// 4.创建一个新的红黑树节点，新节点默认为红色，左右子节点和父节点都指向哨兵节点
rb_tree_node *create_node(rb_tree *tree, void *data)
{
    // 动态分配内存给新节点
    rb_tree_node *node = (rb_tree_node *)calloc(1, sizeof(rb_tree_node));
    if (node == NULL)
    {
        printf("内存溢出，动态分配失败\n");
        exit(EXIT_FAILURE);
    }
    // 设置新节点存储的数据
    node->data = data;
    // 新节点的颜色默认为红色
    node->color = RED;
    // 左右子节点和父节点都指向哨兵节点
    node->parent = tree->nil_node;
    node->left_child = tree->nil_node;
    node->right_child = tree->nil_node;
    // 返回创建的节点
    return node;
}

// 5.初始化一棵空树，根节点为nil，并且哨兵节点颜色为黑色(最下面的叶子节点)
rb_tree *create_rb_tree()
{
    // 动态分配内存给红黑树
    rb_tree *tree = (rb_tree *)calloc(1, sizeof(rb_tree));
    if (tree == NULL)
    {
        printf("内存溢出，动态分配失败\n");
        exit(EXIT_FAILURE);
    }
    // 创建哨兵节点
    tree->nil_node = (rb_tree_node *)calloc(1, sizeof(rb_tree_node));
    if (tree->nil_node == NULL)
    {
        printf("内存溢出，动态分配失败\n");
        exit(EXIT_FAILURE);
    }
    // 哨兵节点默认为黑色
    tree->nil_node->color = BLACK;
    // 初始化红黑树，没有插入任何节点
    // 根节点指向哨兵节点
    tree->root_node = tree->nil_node;
    return tree;
}

/*
红黑树的插入过程和二叉查找时的插入过程基本类似，不同的地方在于红黑树插入新节点后，需要进行调整，以满足红黑树的性质：
    1.节点颜色：每个节点都是红色或黑色。
    2.根节点：根节点必须是黑色。
    3.叶子节点：所有的叶子节点（即空节点）都是黑色。
    4.红色节点的约束：红色节点的子节点必须是黑色（即红色节点不能有红色子节点）。
    5.黑色节点的平衡：从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。
这些特性确保了红黑树的平衡性，使得其在最坏情况下的时间复杂度仍然保持在 O(logN)。具体来说，红黑树通过以下方式实现自平衡：
    旋转操作：包括左旋和右旋，用于调整节点的位置以维持树的平衡。
    变色操作：用于调整节点的颜色以满足红黑树的特性。
*/
// 6.左旋操作：左旋x，将x节点的右子节点提升为其父节点，并将x下移至其右子节点的左子节点的，左旋用于红黑树失衡调整的结构
void left_rotate(rb_tree *tree, rb_tree_node *x)
{
    // 6.1设置y为x的右子节点
    rb_tree_node *y = x->right_child;
    // 6.2将y的左子树作为x的右子树
    x->right_child = y->left_child;

    // 6.3 如果y的左子节点不是哨兵节点，要更改其父节点为x
    if (y->left_child != tree->nil_node)
    {
        y->left_child->parent = x;
    }
    // 6.4让y的父节点指向x的父节点
    y->parent = x->parent;

    // 6.5如果x是根节点，更新y为根节点
    if (x->parent == tree->nil_node)
    {
        // 如果x是根节点，则更新根节点为y
        tree->root_node = y;
    }
    else if (x == x->parent->left_child)
    {
        // x是父节点的左子节点，更新y为其左子节点
        x->parent->left_child = y;
    }
    else
    {
        x->parent->right_child = y;
    }
    // 6.6设置x为y的左子节点
    y->left_child = x;
    // 6.7设置x的父节点为y
    x->parent = y;
}

// 7.右旋操作：右旋y，将y节点的左子节点提升为其父节点，并y下移至其左子节点的右子节点的，右旋用于红黑树失衡调整的结构
void right_rotate(rb_tree *tree, rb_tree_node *y)
{
    // 7.1设置x为y的左子节点
    rb_tree_node *x = y->left_child;
    // 7.2设置x的右子节点为y的左子节点
    y->left_child = x->right_child;
    if (x->right_child != tree->nil_node)
    {
        // 如果x的右子节点不为哨兵节点 ，更新其父节点为y
        x->right_child->parent = y;
    }
    // 7.3让x的父节点指向y的父节点
    x->parent = y->parent;
    if (y->parent == tree->nil_node)
    {
        // 更新x为根节点
        tree->root_node = x;
    }
    else if (y == y->parent->right_child)
    {
        y->parent->right_child = x;
    }
    else
    {
        y->parent->left_child = x;
    }
    // 7.4设置y为x的右子节点
    x->right_child = y;
    // 7.5更新y的父节点为x
    y->parent = x;
}

// last1.释放节点
void free_tree(rb_tree *tree, rb_tree_node *node)
{
    if (node != tree->nil_node)
    {
        // 释放左子节点
        free_tree(tree, node->left_child);
        // 释放右子节点
        free_tree(tree, node->right_child);
        // 释放节点本身
        free(node);
    }
}

// last2.释放树
void destroy_tree(rb_tree *tree)
{
    // 从root节点，根节点开始释放
    free_tree(tree, tree->root_node);
    // 释放哨兵节点
    free(tree->nil_node);
    // 释放红黑树的内存空间
    free(tree);
}

3. main.c

#include <stdio.h>
#include "../inc/rb_tree_common.h"

int main(int argc, char const *argv[])
{
    //1.创建红黑树
    rb_tree *tree=create_rb_tree();

    //last.2 释放红黑树
    destroy_tree(tree);
    return 0;
}

4. 总结

1. 左右旋

左旋右旋，这层代码还是简单的，我想执导的是左右转的目的是什么，或者说在现实世界的应用情况
在什么情况下可以用到左右旋？----在修复的时候用得到，要维护红黑树的平衡及规则

左右旋转，先维护x与y的关系，即谁是谁的分支，重新定义x与y的双向关系

1.先判断子结点
上升的的节点与源节点的子关系，上升节点的分支与源节点的子关系
2.判断父关系
（分支节点的的父节点）上升节点的某个分支不为哨兵节点的话，则判断其分支节点的指向为源节点（认爹）y->left_child->parent=x;
x与y的关系有三种可能性
1.x（源节点）为根节点，判断(x->parent==tree->nil_node)，则y就等于根节点，即tree->root_node=y;
2.即x不是根节点，判断x是其父节点的那个位置的节点，然后执行x->parent->left_child=y;
3.另一个节点一样

2. 修复（变色，左右旋转）

这个我不知道怎么去描述。等有图了继续说

通过颜色翻转，将红色冲突向上传递，保证局部黑高不变，但可能引发更高层的红红冲突，需继续循环处理。

5.代码（包含查找，插入修复，左右旋，插入，查询，比较，遍历）

代码我暂时贴到下方，暂时还未仔细了解，我相信我有时间1会仔细去看。特此标红点，

1. 声名类（自定义头文件）

#ifndef RB_TREE_COMMON_H
#define RB_TREE_COMMON_H

//1.定义节点颜色
typedef enum{RED,BLACK}node_color;

//2.红黑数的节点 -结构体
typedef struct rb_tree_node
{
    //1.数据域
    void *data;
    //2.节点的颜色
    node_color color;
    //3.父节点
    struct rb_tree_node *parent;
    //4.左子节点
    struct rb_tree_node * left_child;
    //5.右子节点
    struct rb_tree_node *right_child;
}rb_tree_node;

//3.红黑树  -结构体
typedef struct rb_tree
{
    //根节点
    rb_tree_node *root_node;
    //哨兵节点
    rb_tree_node *nil_node;
}rb_tree;

//4.创建一个新的红黑树节点，新节点默认为红色，左右子节点和父节点都指向哨兵节点
rb_tree_node* create_node(rb_tree *tree,void *data);

//5.初始化一棵空树，根节点为nil，并且哨兵节点颜色为黑色(最下面的叶子节点)
rb_tree* create_rb_tree();

/*
红黑树的插入过程和二叉查找时的插入过程基本类似，不同的地方在于红黑树插入新节点后，需要进行调整，以满足红黑树的性质：
    1.节点颜色：每个节点都是红色或黑色。
    2.根节点：根节点必须是黑色。
    3.叶子节点：所有的叶子节点（即空节点）都是黑色。
    4.红色节点的约束：红色节点的子节点必须是黑色（即红色节点不能有红色子节点）。
    5.黑色节点的平衡：从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。
这些特性确保了红黑树的平衡性，使得其在最坏情况下的时间复杂度仍然保持在 O(logN)。具体来说，红黑树通过以下方式实现自平衡：
    旋转操作：包括左旋和右旋，用于调整节点的位置以维持树的平衡。
    变色操作：用于调整节点的颜色以满足红黑树的特性。
*/
//6.左旋操作：左旋x，将x节点的右子节点提升为其父节点，并将x下移至其右子节点的左子节点的，左旋用于红黑树失衡调整的结构
void left_rotate(rb_tree *tree,rb_tree_node *x);

//7.右旋操作：右旋y，将y节点的左子节点提升为其父节点，并y下移至其左子节点的右子节点的，右旋用于红黑树失衡调整的结构
void right_rotate(rb_tree *tree,rb_tree_node *y);

//8.插入修复：在红黑树中插入节点时，可能会违反红黑树的特性，触发红黑树的修复机制，维护红黑树的特性达到自平衡的目的
void insert_fixup(rb_tree *tree,rb_tree_node *z);

//9.1比较函数  (int 类型比较)
int compare_int(void *a,void *b);

//9.2插入操作
void insert_rb_tree(rb_tree *tree,void *data,int (*cmp)(void*,void*));

//10.1 打印函数(int 类型)
void print_int(rb_tree_node *node);
//10.2 先序遍历   根 左  右
void  preorder_traversal(rb_tree *tree,rb_tree_node *node,void (*print_data)(rb_tree_node *));
//10.3 中序遍历    左 根 右
void  inorder_traversal(rb_tree *tree,rb_tree_node *node,void (*print_data)(rb_tree_node *));
//10.4 后序遍历    左  右 根
void  postorder_traversal(rb_tree *tree,rb_tree_node *node,void (*print_data)(rb_tree_node *));

//last1.释放节点
void free_tree(rb_tree *tree,rb_tree_node *node);

//last2.释放树
void destroy_tree(rb_tree *tree);



#endif

2. 声名类（函数的实现方法）

#include <stdio.h>
#include <stdlib.h>
#include "../inc/rb_tree_common.h"

//4.创建一个新的红黑树节点，新节点默认为红色，左右子节点和父节点都指向哨兵节点
rb_tree_node* create_node(rb_tree *tree,void *data){
    //动态分配内存给新节点
    rb_tree_node* node=(rb_tree_node*)calloc(1,sizeof(rb_tree_node));
    if (node==NULL)
    {
        printf("内存溢出，动态分配失败\n");
        exit(EXIT_FAILURE);
    }
    //设置新节点存储的数据
    node->data=data;
    //新节点的颜色默认为红色
    node->color=RED;
    //左右子节点和父节点都指向哨兵节点
    node->parent=tree->nil_node;
    node->left_child=tree->nil_node;
    node->right_child=tree->nil_node;
    //返回创建的节点
    return node;
}

//5.初始化一棵空树，根节点为nil，并且哨兵节点颜色为黑色(最下面的叶子节点)
rb_tree* create_rb_tree(){
    //动态分配内存给红黑树
    rb_tree* tree=(rb_tree*)calloc(1,sizeof(rb_tree));
    if (tree==NULL)
    {
        printf("内存溢出，动态分配失败\n");
        exit(EXIT_FAILURE);
    }
    //创建哨兵节点
    tree->nil_node=(rb_tree_node*)calloc(1,sizeof(rb_tree_node));
    if (tree->nil_node==NULL)
    {
        printf("内存溢出，动态分配失败\n");
        exit(EXIT_FAILURE);
    }
    //哨兵节点默认为黑色
    tree->nil_node->color=BLACK;
    //初始化红黑树，没有插入任何节点
    //根节点指向哨兵节点
    tree->root_node=tree->nil_node;
    return tree;
}

/*
红黑树的插入过程和二叉查找时的插入过程基本类似，不同的地方在于红黑树插入新节点后，需要进行调整，以满足红黑树的性质：
    1.节点颜色：每个节点都是红色或黑色。
    2.根节点：根节点必须是黑色。
    3.叶子节点：所有的叶子节点（即空节点）都是黑色。
    4.红色节点的约束：红色节点的子节点必须是黑色（即红色节点不能有红色子节点）。
    5.黑色节点的平衡：从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。
这些特性确保了红黑树的平衡性，使得其在最坏情况下的时间复杂度仍然保持在 O(logN)。具体来说，红黑树通过以下方式实现自平衡：
    旋转操作：包括左旋和右旋，用于调整节点的位置以维持树的平衡。
    变色操作：用于调整节点的颜色以满足红黑树的特性。
*/
//6.左旋操作：左旋x，将x节点的右子节点提升为其父节点，并将x下移至其右子节点的左子节点的，左旋用于红黑树失衡调整的结构
void left_rotate(rb_tree *tree,rb_tree_node *x){
    //6.1设置y为x的右子节点
    rb_tree_node *y=x->right_child;
    //6.2将y的左子树作为x的右子树
    x->right_child=y->left_child;
    //6.3 如果y的左子节点不是哨兵节点，要更改其父节点为x
    if (y->left_child!=tree->nil_node)
    {
        y->left_child->parent=x;
    }
    //6.4让y的父节点指向x的父节点
    y->parent=x->parent;
    //6.5如果x是根节点，更新y为根节点
    if (x->parent==tree->nil_node)
    {
        //如果x是根节点，则更新根节点为y
        tree->root_node=y;
    }else if (x==x->parent->left_child)
    {
        //x是父节点的左子节点，更新y为其左子节点
        x->parent->left_child=y;
    }else
    {
        x->parent->right_child=y;
    }
    //6.6设置x为y的左子节点
    y->left_child=x;
    //6.7设置x的父节点为y
    x->parent=y;
}

//7.右旋操作：右旋y，将y节点的左子节点提升为其父节点，并y下移至其左子节点的右子节点的，右旋用于红黑树失衡调整的结构
void right_rotate(rb_tree *tree,rb_tree_node *y){
    //7.1设置x为y的左子节点
    rb_tree_node *x=y->left_child;
    //7.2设置x的右子节点为y的左子节点
    y->left_child=x->right_child;
    if (x->right_child!=tree->nil_node)
    {   
        //如果x的右子节点不为哨兵节点 ，更新其父节点为y
        x->right_child->parent=y;
    }
    //7.3让x的父节点指向y的父节点
    x->parent=y->parent;
    if (y->parent==tree->nil_node)
    {
        //更新x为根节点
        tree->root_node=x;
    }else if (y==y->parent->right_child)
    {
        y->parent->right_child=x;
    }else
    {
        y->parent->left_child=x;
    }
    //7.4设置y为x的右子节点
    x->right_child=y;
    //7.5更新y的父节点为x
    y->parent=x;    
}

/*
不满足红黑树的性质就需要在插入/删除时修复(我们主要讲插入修复)
1.默认新节点为红色，插入节点为红色，父节点也是红色(违反了红色不能连续)
2.上溢情况：任意节点到叶子节点的黑色节点数量不一致
*/

//8.插入修复：在红黑树中插入节点时，可能会违反红黑树的特性，触发红黑树的修复机制，维护红黑树的特性达到自平衡的目的
void insert_fixup(rb_tree *tree,rb_tree_node *z){
    //新节点默认为红色节点，放插入节点的父节点为红色时，进入修复阶段，因为红黑树不允许连续的红色
    while (z->parent->color==RED)
    {
        //判断父节点的位置
        //父节点时祖父节点的左子树
        if (z->parent==z->parent->parent->left_child)
        {
            //当父节点是组父节点的左子树，考虑叔叔节点的情况
            //叔叔节点为y
            rb_tree_node *y=z->parent->parent->right_child;
            //情况1：父节点为红色，叔叔节点也为红色
            if (y->color==RED)
            {
                //父节点变黑
                z->parent->color=BLACK;
                //叔叔节点变黑
                y->color=BLACK;
                //祖父节点变红
                z->parent->parent->color=RED;
                //继续向上检查祖父节点是否需要修复
                z=z->parent->parent;
            }else
            {
                //叔叔节点为黑色或者为哨兵节点
                //情况2：z是父节点的右子节点
                if (z==z->parent->right_child)
                {
                    z=z->parent;
                    //左旋父节点
                    left_rotate(tree,z);
                }
                //情况2转换为情况3
                //情况3：父节点为红色，祖父节点为黑色，叔叔节点为黑色或者为哨兵节点
                //交换父节点和祖父节点的颜色
                z->parent->color=BLACK;
                z->parent->parent->color=RED;
                //右旋祖父节点
                right_rotate(tree,z->parent->parent);  
            }
        }else
        {
            //父节点为红色，并且为祖父节点的右子节点
            //判断叔叔y节点的情况  
            rb_tree_node *y=z->parent->parent->left_child;
            if (y->color==RED)
            {
                //镜像情况1  叔叔节点也为红色
                //父节点变黑
                z->parent->color=BLACK;
                //叔叔节点变黑
                y->color=BLACK;
                //祖父节点变红
                z->parent->parent->color=RED;
                //继续向上检查祖父节点是否需要修复
                z=z->parent->parent;
            }else
            {
                //叔叔节点为黑色/哨兵节点
                //镜像情况2
                //当前节点为父节点的左子节点
                if (z==z->parent->left_child)
                {
                    z=z->parent;
                    //右旋父节点
                    right_rotate(tree,z);
                }
                //情况2转换为情况3
                //镜像情况3
                z->parent->color=BLACK;
                z->parent->parent->color=RED;
                //左旋祖父节点
                left_rotate(tree,z->parent->parent); 
            }
        }
    }
    //root节点 根节点必须为黑色
    tree->root_node->color=BLACK;
}

//9.1比较函数  (int 类型比较)
int compare_int(void *a,void *b){
    return *(int*)a - *(int*)b;
}

//9.2插入操作
void insert_rb_tree(rb_tree *tree,void *data,int (*cmp)(void*,void*)){
    //创建新节点
    rb_tree_node *z=create_node(tree,data);
    //先找到插入的位置(父节点)，临时变量y
    rb_tree_node *y=tree->nil_node;
    //从根节点开始遍历
    rb_tree_node *x=tree->root_node;

    //寻找插入位置  -插入节点的父节点
    while (x!=tree->nil_node)
    {
        y=x;
        if (cmp(z->data,x->data)<0)
        {
            x=x->left_child;
        }else
        {
            x=x->right_child;
        }
    }
    //将找到的y就是插入节点的父节点
    z->parent=y;
    //如果树是空的，第一次插入 该节点应为root节点
    if (y==tree->nil_node)
    {
        tree->root_node=z;
    }else if (cmp(z->data,y->data)<0)
    {
        //左小
        y->left_child=z;
    }else
    {
        //右大
        y->right_child=z;
    }
    //调用插入修复，维持红黑树的平衡性
    insert_fixup(tree,z);
}

//10.1 打印函数(int 类型)
void print_int(rb_tree_node *node){
    printf("%d(%s) ",*(int*)node->data,node->color?"B":"R");
}
//10.2 先序遍历   根 左  右
void  preorder_traversal(rb_tree *tree,rb_tree_node *node,void (*print_data)(rb_tree_node *)){
    if (node!=tree->nil_node)
    {
        //先访问根节点
        print_data(node);
        //递归遍历左子树
        preorder_traversal(tree,node->left_child,print_data);
        //递归遍历右子树
        preorder_traversal(tree,node->right_child,print_data);
    }
    
}
//10.3 中序遍历    左 根 右
void  inorder_traversal(rb_tree *tree,rb_tree_node *node,void (*print_data)(rb_tree_node *)){
    if (node!=tree->nil_node)
    {
        
        //先递归遍历左子树
        inorder_traversal(tree,node->left_child,print_data);
        //访问根节点
        print_data(node);
        //递归遍历右子树
        inorder_traversal(tree,node->right_child,print_data);
    }
}
//10.4 后序遍历    左  右 根
void  postorder_traversal(rb_tree *tree,rb_tree_node *node,void (*print_data)(rb_tree_node *)){
    if (node!=tree->nil_node)
    {
        
        //先递归遍历左子树
        postorder_traversal(tree,node->left_child,print_data);
        //递归遍历右子树
        postorder_traversal(tree,node->right_child,print_data);
        //访问根节点
        print_data(node);
    }
}

//last1.释放节点
void free_tree(rb_tree *tree,rb_tree_node *node){
    if (node!=tree->nil_node)
    {
        //释放左子节点
        free_tree(tree,node->left_child);
        //释放右子节点
        free_tree(tree,node->right_child);
        //释放节点本身
        free(node);
    }
    
}

//last2.释放树
void destroy_tree(rb_tree *tree){
    //从root节点，根节点开始释放
    free_tree(tree,tree->root_node);
    //释放哨兵节点
    free(tree->nil_node);
    //释放红黑树的内存空间
    free(tree);
}

3.main.c

#include <stdio.h>
#include "../inc/rb_tree_common.h"

int main(int argc, char const *argv[])
{
    //1.创建红黑树
    rb_tree *tree=create_rb_tree();

    //2.插入一些 数据
    int a=20,b=15,c=25,d=10,e=18,f=8;
    insert_rb_tree(tree,&a,compare_int);
    insert_rb_tree(tree,&b,compare_int);
    insert_rb_tree(tree,&c,compare_int);
    insert_rb_tree(tree,&d,compare_int);
    insert_rb_tree(tree,&e,compare_int);
    insert_rb_tree(tree,&f,compare_int);

    //3.先序遍历
    printf("---------------先序遍历----------------------\n");
    preorder_traversal(tree,tree->root_node,print_int);
    printf("\n");

    //4.中序遍历
    printf("---------------中序遍历----------------------\n");
    inorder_traversal(tree,tree->root_node,print_int);
    printf("\n");

    //5.后序遍历
    printf("---------------后序遍历----------------------\n");
    postorder_traversal(tree,tree->root_node,print_int);
    printf("\n");

    //last.2 释放红黑树
    destroy_tree(tree);
    return 0;
}

天工造物局

北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台

更多推荐

deck.gl TripsLayer 出租车轨迹动画示例实战：从示例运行到着色器原理

TripsLayer 是 deck.gl 中用于渲染**随时间流动的轨迹动画**（如出租车行程、物流路径、迁徙路线）的核心图层。本文以仓库中的最小独立示例 [examples/website/trips](https://link.gitcode.com/i/1442af8f442f4cff39ff546e050fceb5) 为骨架，带你完成从安装依赖、启动应用、理解曼哈顿出租车数据格式，到深入

天工造物局

Foundry Anvil 中 eth_simulateV1 的 Blob 交易与 Blob Gas 字段规范化：原理、实现与测试验证

本篇技术指南以 [anvil-simulate-blob-transactions.md](https://link.gitcode.com/i/3d2ebe227262de169335eb290af80da8) 这条 changelog 条目为起点，深入剖析 Foundry Anvil 对 `eth_simulateV1` RPC 返回结果中 blob（EIP-4844）交易与 blob gas

天工造物局

LMCache CLI 实战：用 `lmcache kvcache clear` 管理运行中服务的 KV Cache 状态

本文是一份针对 LMCache 官方 CLI 命令 `lmcache kvcache` 的完整技术指南。该命令用于在**运行中的 LMCache 服务（MP HTTP server）**上管理 KV cache 状态，当前提供 `clear` 子命令，用于清空 L1（CPU 内存）层中缓存的全部 KV 数据。读完本文，你将掌握该命令的完整参数体系、退出码语义、终端/JSON/静默三种输出模式，并能