數據結構—(鏈表，棧，隊列，樹)

本文章寫的比較亂，屬于是縫合怪，很多細節沒處理，顯得粗糙，日后完善，今天趕時間了。

1. 紅黑樹的修復篇章

2. 紅黑樹的代碼理解（部分寫道注釋之中了）

3. 隊列與棧的代碼

4. 重要是理解物理邏輯，從而理解代碼邏輯

目錄

一 鏈表

1. 單向鏈表

2. 雙向鏈表

雙向鏈表的操作（c語言）

1. linked_list_common.h

2. link.c

3. main.c

3. 循環列表

1. 單向循環列表

2. 雙向循環列表

4. 靜態鏈表

二 棧（stack）(代碼暫不演示）

三 隊列(queue) (代碼暫不演示）

四 樹（tree）

1. 二叉樹（Binary Tree）

2. 二叉搜索樹（BST）

3. AVL 樹

4. B 樹

5. 紅黑樹

1. red_black_common.h

2.?red_black_tree.c

3. main.c

4. 總結

1. 左右旋

2. 修復（變色，左右旋轉）

一 鏈表

鏈表（Linked List） 是一種線性數據結構，由一系列節點（Node）通過指針鏈接而成。與數組不同，鏈表的元素在內存中非連續存儲，每個節點獨立分配內存

類型方向性內存開銷適用場景
單向鏈表單向低簡單數據管理（如棧、隊列）
雙向鏈表雙向高（2指針）頻繁雙向遍歷（如瀏覽器歷史記錄）
循環鏈表環狀同單向/雙向輪詢任務、循環緩沖區
靜態鏈表單向/雙向固定數組無動態內存環境（如嵌入式開發）

  1. 單向鏈表：

    • 實現棧（LIFO）、隊列（FIFO）。

    • 輕量級數據集合管理（如學生成績表）。

  2. 雙向鏈表：

    • 瀏覽器前進/后退功能。

    • 文本編輯器的撤銷/重做操作。

  3. 循環鏈表：

    • 操作系統進程調度（時間片輪轉）。

    • 音樂播放器的循環播放列表。

  4. 靜態鏈表：

    • 內存受限的嵌入式系統。

    • 預分配固定內存池的實時系統。

（此處重點且詳細的說雙向列表，雙向列表會了之后，其余兩個也就差不多了）

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指針，修改新節點的直接前驅指針，新節點的直接后繼指針為 直接前驅的nextnew_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;// 鏈表節點個數+1list->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){// 頭結點不為Nullnode *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）。

  • 規則：

    1. 節點是紅或黑。

    2. 根和葉子（NIL）是黑。

    3. 紅節點的子節點必為黑。（即紅不能連續）

    4. 任意節點到葉子的路徑包含相同數量黑節點。

??? 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的左子節點不是哨兵節點，要更改其父節點為xif (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是根節點，則更新根節點為ytree->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的父節點為yx->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的右子節點不為哨兵節點 ，更新其父節點為yx->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的父節點為xy->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. 修復（變色，左右旋轉）

這個我不知道怎么去描述。等有圖了繼續說

通過顏色翻轉，將紅色沖突向上傳遞，保證局部黑高不變，但可能引發更高層的紅紅沖突，需繼續循環處理。

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/bicheng/80849.shtml
繁體地址，請注明出處：http://hk.pswp.cn/bicheng/80849.shtml
英文地址，請注明出處：http://en.pswp.cn/bicheng/80849.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

每日Prompt：發光線條解剖圖

每日Prompt：發光線條解剖圖

提示詞 一幅數字插畫&#xff0c;描繪了一個 [SUBJECT]&#xff0c;其結構由一組發光、干凈且純凈的藍色線條勾勒而成。畫面設定在深色背景之上&#xff0c;以突出 [SUBJECT] 的形態與特征。某個特定部位&#xff0c;如 [PART]&#xff0c;通過紅色光暈加以強調&#xff0c;以…
閱讀更多...
【時時三省】(C語言基礎)使用字符串處理函數

【時時三省】(C語言基礎)使用字符串處理函數

山不在高&#xff0c;有仙則名。水不在深&#xff0c;有龍則靈。 ----CSDN 時時三省 在C函數庫中提供了一些用來專門處理字符串的函數&#xff0c;使用方便。幾乎所有版本的C語言編譯系統都提供這些函數。下面介紹幾種常用的函數。 ①puts函數 輸出字符串的函數 其一般形式…
閱讀更多...
構建可信數據空間需要突破技術、規則和生態三大關鍵

構建可信數據空間需要突破技術、規則和生態三大關鍵

構建可信數據空間需要突破技術、規則和生態三大關鍵&#xff1a;技術上要解決"可用不可見"的隱私計算難題&#xff0c;規則上要建立動態確權和跨境流動的治理框架&#xff0c;生態上要形成多方協同的標準體系。他強調&#xff0c;只有實現技術可控、規則可信、生態協…
閱讀更多...
模板的使用

模板的使用

模板 模板的概念&#xff1a;模板就是建立一個通用的模具&#xff0c;大大提高復用性 c中模板機制分為兩類 函數模板 建立一個通用函數&#xff0c;其函數返回值類型和形參類型可以不具體定制&#xff0c;用一個虛擬的類型來代表 template<typename T> //template 聲…
閱讀更多...
YOLOv1：開啟實時目標檢測的新篇章

YOLOv1：開啟實時目標檢測的新篇章

YOLOv1&#xff1a;開啟實時目標檢測的新篇章 在深度學習目標檢測領域&#xff0c;YOLO&#xff08;You Only Look Once&#xff09;系列算法無疑占據著重要地位。其中&#xff0c;YOLOv1作為開山之作&#xff0c;以其獨特的設計理念和高效的檢測速度&#xff0c;為后續的目標…
閱讀更多...
vim中的查找

vim中的查找

在 Vim 中&#xff0c;使用 n 鍵可以按正向&#xff08;向下&#xff09;繼續查找下一個匹配項。若要反向&#xff08;向上&#xff09;查找&#xff0c;可以使用以下方法&#xff1a; 1. 使用 N 鍵反向查找 在查找命令&#xff08;如 /keyword&#xff09;后&#xff0c;按下…
閱讀更多...
卡爾曼濾波通俗理解

卡爾曼濾波通俗理解

卡爾曼濾波器的目的與意義何在&#xff1f; - 陳不陳的回答 - 知乎 https://www.zhihu.com/question/41351736/answer/3057034500 這是一個比較通俗易懂的例子&#xff0c;讀完之后可以對卡爾曼濾波怎么使用有比較直觀的理解。 &#x1f9e0; 一、卡爾曼濾波是什么&#xff1f;…
閱讀更多...
對抗帕金森：在疾病陰影下，如何重掌生活主動權？

對抗帕金森：在疾病陰影下，如何重掌生活主動權？

帕金森病&#xff0c;一種影響全球超 1000 萬人的神經退行性疾病&#xff0c;正無聲地改變著患者的生活軌跡。隨著大腦中多巴胺分泌減少&#xff0c;患者逐漸出現肢體震顫、肌肉僵硬、步態遲緩等癥狀&#xff0c;甚至連扣紐扣、端水杯這類日常動作都變得艱難。更棘手的是&#…
閱讀更多...
黑馬k8s（五）

黑馬k8s（五）

1.Namespace 2.Pod run nginx&#xff1a;nginx是pod控制器的名稱&#xff0c;不是pod的名稱 查看pod更高的參數&#xff1a; 啟動一個不存在的鏡像&#xff1a;pod 查看 dev下面的pod&#xff0c;第二個pod處于容器創建的狀態 查看pod的詳情描述&#xff1a; 通過pod的ip&…
閱讀更多...
推薦算法工程化：ZKmall模板商城的B2C 商城的用戶分層推薦策略

推薦算法工程化：ZKmall模板商城的B2C 商城的用戶分層推薦策略

在 B2C 電商競爭激烈的市場環境中&#xff0c;精準推薦已成為提升用戶體驗、促進商品銷售的關鍵。ZKmall 模板商城通過推薦算法工程化手段&#xff0c;深度挖掘用戶數據價值&#xff0c;制定科學的用戶分層推薦策略&#xff0c;實現 “千人千面” 的個性化推薦&#xff0c;幫助…
閱讀更多...
如何使用 Qwen3 實現 Agentic RAG？

如何使用 Qwen3 實現 Agentic RAG？

今天&#xff0c;我們將學習如何部署由阿里巴巴最新Qwen 3驅動的Agentic RAG。 這里是我們的工具棧&#xff1a; CrewAI用于代理編排。 Firecrawl用于網絡搜索。 LightningAI的LitServe用于部署。 頂部的視頻展示了這一過程。 圖表顯示了我們的Agentic RAG流程&#xff1…
閱讀更多...
【UAP】《Empirical Upper Bound in Object Detection and More》

【UAP】《Empirical Upper Bound in Object Detection and More》

Borji A, Iranmanesh S M. Empirical upper bound in object detection and more[J]. arXiv preprint arXiv:1911.12451, 2019. arXiv-2019 文章目錄 1、Background and Motivation2、Related Work3、Advantages / Contributions4、Experimental Setup4.1、Benchmarks Dataset…
閱讀更多...
LeetCode 941. 有效的山脈數組 java題解

LeetCode 941. 有效的山脈數組 java題解

https://leetcode.cn/problems/valid-mountain-array/description/ 雙指針 class Solution {public boolean validMountainArray(int[] arr) {int lenarr.length;if(len<3) return false;int left0,rightlen-1;while(left1<len&&arr[left]<arr[left1]){left…
閱讀更多...
udp多點通信和心跳包

udp多點通信和心跳包

刷題 # UDP多點通信核心要點## 基礎通信模式### 單播通信- 一對一通信方式- UDP默認通信模式- 地址指向具體目標主機### 廣播通信- 一對多通信機制- 地址范圍&#xff1a;xxx.xxx.xxx.255- 僅限局域網傳輸- 需設置SO_BROADCAST標志### 組播通信- 多對多群組通信- 地址范圍&…
閱讀更多...
文件相關操作

文件相關操作

文本文件 程序運行時產生的數據都屬于臨時數據&#xff0c;程序一旦運行結束都會被釋放 通過文件可以將數據持久化 C的文件操作需要包含頭文件 文件分類 文本文件&#xff1a;文件以文本的ASCII碼形式存儲在計算機中 二進制文件&#xff1a;文件以文本的二進制形式存儲在計算…
閱讀更多...
[論文閱讀]ControlNET: A Firewall for RAG-based LLM System

[論文閱讀]ControlNET: A Firewall for RAG-based LLM System

ControlNET: A Firewall for RAG-based LLM System [2504.09593] ControlNET: A Firewall for RAG-based LLM System RAG存在數據泄露風險和數據投毒風險。相關研究探索了提示注入和投毒攻擊&#xff0c;但是在控制出入查詢流以減輕威脅方面存在不足 文章提出一種ai防火墻CO…
閱讀更多...
C++中的各式類型轉換

C++中的各式類型轉換

隱式轉換&#xff1a; 基本類型的隱式轉換&#xff1a; 當函數參數類型非精確匹配&#xff0c;但是可以轉換的時候發生 如&#xff1a; void func1(double x){cout << x << endl; }void func2(char c){cout << c << endl; }int main(){func1(2);//…
閱讀更多...
2.重建大師輸入輸出數據格式介紹

2.重建大師輸入輸出數據格式介紹

摘要&#xff1a;本文主要介紹重建大師支持的輸入數據格式及輸出數據格式。 1.輸入數據格式 1.1圖像文件 重建大師支持JPG、JPEG和TIFF格式的照片。 不同架次照片放置于同級目錄的不同文件夾&#xff0c;同一架次不同鏡頭拍攝得到的照片存放于不同的子文件夾&#xff0c;可使…
閱讀更多...
我們該如何使用DeepSeek幫我們減負？

我們該如何使用DeepSeek幫我們減負？

在當今信息爆炸的時代&#xff0c;如何快速獲取、篩選和分析信息已經成為各行各業的重要能力。而DeepSeek作為一種先進的智能搜索和信息挖掘工具&#xff0c;能夠幫助用戶快速找到所需的信息&#xff0c;并從海量數據中提取出有用的洞見。在這篇博文中&#xff0c;我們將深入探…
閱讀更多...
抗量子計算攻擊的數據安全體系構建：從理論突破到工程實踐

抗量子計算攻擊的數據安全體系構建：從理論突破到工程實踐

在“端 - 邊 - 云”三級智能協同理論中&#xff0c;端 - 邊、邊 - 云之間要進行數據傳輸&#xff0c;網絡的安全尤為重要&#xff0c;為了實現系統總體的安全可控&#xff0c;將構建安全網絡。 可先了解我的前文&#xff1a;“端 - 邊 - 云”三級智能協同平臺的理論建構與技術實…
閱讀更多...
最新文章

Copyright @ 2022~2023