前言

??剛開始接觸紅黑樹的時候，感覺很難。其實不然，紅黑樹只是情況分的多了一點而已，相較于線段樹，主席樹等等，簡單多了。對于紅黑樹3種插入維護(hù)4種刪除維護(hù)沒必要去記憶，稍作了解，對于紅黑樹的性質(zhì)和特點，需要特別記憶。

??本專欄知識點是通過零聲教育的線上課學(xué)習(xí)，進(jìn)行梳理總結(jié)寫下文章，對c/c++linux課程感興趣的讀者，可以點擊鏈接：C/C++Linux服務(wù)器開發(fā)/后臺架構(gòu)師【零聲教育】-學(xué)習(xí)視頻教程-騰訊課堂課程介紹詳細(xì)查看課程的服務(wù)。

注意，本文圖中紅黑樹的葉子結(jié)點默認(rèn)不畫出來~

為什么要有紅黑樹

二叉搜索樹

??二叉搜索樹（又叫二叉排序樹，BST）：對于任意一個結(jié)點，其左子樹的值必定小于該結(jié)點，其右子樹的值必定大于該結(jié)點。那么中序遍歷的時候，就是有序的了。理論上來說，增加，刪除，修改的時間復(fù)雜度都是O(log(N))。但是它存在一個致命的問題。

??退化：向樹中插入[1，2，3，4，5，6]，此時樹退化成了一個鏈表，增加，刪除，修改的時間復(fù)雜度退化為O(N)

添加圖片注釋，不超過 140 字（可選）

平衡二叉搜索樹

??平衡二叉搜索樹（AVL Tree）：它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉搜索樹。如果向樹中插入[1，2，3，4，5，6]

添加圖片注釋，不超過 140 字（可選）

可以看到AVLTree在最壞的情況下，依然保持了“絕對的平衡”：左右兩個子樹的高度差的絕對值不超過1。那么AVL Tree是如何保證平衡的呢，是通過旋轉(zhuǎn)，可以看到，無論是插入還是刪除元素，都要去通過旋轉(zhuǎn)維護(hù)整個樹的平衡。

• AVL查詢元素：O(log(N))
• AVL插入元素：最多一次旋轉(zhuǎn)O(1)，加上查詢的時間O(log(N))，插入的復(fù)雜度O(log(N))
• AVL刪除元素：必須檢查從刪除結(jié)點開始到根結(jié)點路徑上的所有結(jié)點的平衡因子。因此刪除的代價比較大，刪除最多需要log(N)次旋轉(zhuǎn)，加上查詢的時間，刪除的復(fù)雜度O(2log(N))

紅黑樹

??我們發(fā)現(xiàn)，AVL樹未免太嚴(yán)格了一些，有沒有一種數(shù)據(jù)結(jié)構(gòu)，能讓AVL樹不那么嚴(yán)格平衡，降低維護(hù)平衡的開銷，同時又不能像BST一樣退化呢？

當(dāng)然有，就是本文所寫的紅黑樹（rbTree）：

• rbTree查詢元素：O(log(N))
• rbTree插入元素：插入最多2次旋轉(zhuǎn)，加上查詢的時間O(log(N))，插入的復(fù)雜度O(log(N))
• rbTree刪除元素：刪除最多需要3次旋轉(zhuǎn)，加上查詢的時間，刪除的復(fù)雜度O(log(N))

??雖然插入和刪除元素后，需要旋轉(zhuǎn)和變色（本文中統(tǒng)一為維護(hù)），但是這一時間復(fù)雜度可以估算為O(1)不計

??因為rbTree的第6條性質(zhì)（見下文）

• 所以紅黑樹的查詢效率略低與AVL的查詢
• 紅黑樹和AVL插入的速度差不多
• 紅黑樹刪除的速度比AVL快，因為AVL刪除最多需要og(N)次旋轉(zhuǎn)

紅黑樹的應(yīng)用場景

紅黑樹的性質(zhì)（重點）

紅黑樹的定義

#define RED 0#define BlACK 1typedef int KEY_TYPE;typedef struct _rbtree_node { unsigned char color;//顏色 struct _rbtree_node *left;//左子樹 struct _rbtree_node *right;//右子樹 struct _rbtree_node *parent;//父結(jié)點 KEY_TYPE key; void *value;} rbtree_node;//紅黑樹結(jié)點typedef struct _rbtree { rbtree_node *root;//根結(jié)點 rbtree_node *nil;//通用葉子結(jié)點} rbtree;//紅黑樹

紅黑樹的左旋與右旋

動三個方向，改6個指針。 通過旋轉(zhuǎn)，調(diào)整左右高度，使樹達(dá)到平衡。

添加圖片注釋，不超過 140 字（可選）

左旋leftRotate(T,x)—中右->左中

降低X結(jié)點的高度，提高X結(jié)點右結(jié)點（即Y）的高度。

添加圖片注釋，不超過 140 字（可選）

右旋rightRotate(T,y)—中左->中右

降低Y結(jié)點的高度，提高Y結(jié)點左結(jié)點（即X）的高度。

添加圖片注釋，不超過 140 字（可選）

//左旋leftRotate(T,x)—中右->左中//降低X結(jié)點的高度，提高X結(jié)點右結(jié)點（即Y）的高度。void _left_rotate(rbtree *T, rbtree_node *x) { rbtree_node *y = x->right; //1 x->right = y->left;//x的右子樹指向y的左子樹 if (y->left != T->nil) { y->left->parent = x;//y的左子樹的父節(jié)點指向x } //2 y->parent = x->parent;//y的父結(jié)點指向x的父結(jié)點 if (x->parent == T->nil) {//如果x是根結(jié)點 T->root = y; } else if (x == x->parent->left) { x->parent->left = y;//本來指向x結(jié)點的父指針，改成指向y } else { x->parent->right = y; } //3 y->left = x;//y的左子樹指向x結(jié)點 x->parent = y;//x的父節(jié)點指向y}//右旋//copy左旋的代碼//left改成right，right改成left//x改成y，y改成xvoid _right_rotate(rbtree *T, rbtree_node *y) { rbtree_node *x = y->left; //1 y->left = x->right; if (x->right != T->nil) { x->right->parent = y; } //2 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; } //3 x->right = y; y->parent = x;}

紅黑樹插入結(jié)點與插入維護(hù)紅黑樹的三種情況

插入結(jié)點

??在插入結(jié)點時，我們始終認(rèn)為“插入這個結(jié)點之前，原來的紅黑樹是滿足紅黑樹性質(zhì)的==”，那么插入的位置容易找，就是不斷的對比key，最終找到位置，那么新增的結(jié)點是什么顏色呢？我們通過性質(zhì)發(fā)現(xiàn)：

• 如果新結(jié)點是黑色，違背了第5條性質(zhì)
• 如果新結(jié)點是紅色，可能違背第4條性質(zhì)

而第四條性質(zhì)，我們可以通過旋轉(zhuǎn)與上色的方式修復(fù)，所以在我們插入結(jié)點的時候，我們始終認(rèn)為新結(jié)點是紅色

//因為傳入的key可能是字符，可能是整形，所以要提取出來//這里可以看出，其實可以封裝成一個模板int key_compare(KEY_TYPE a, KEY_TYPE b) { //這里假設(shè)是int if (a > b) { return 1; } else if (a root; rbtree_node *y = T->nil;//y是x的父節(jié)點 while (x != T->nil) {//二分找位置 y = x; if (key_compare(z->key, x->key) left; } else if (key_compare(z->key, x->key) > 0) { x = x->right; } else { //如果key相等，看自己的業(yè)務(wù)情景 //重復(fù)插入可以不修改直接退出，可以修改val return; } } //插入 z->parent = y; if (y == T->nil) { T->root = z; } else if (key_compare(z->key, y->key) left = z; } else { y->right = z; } z->left = T->nil; z->right = T->nil; z->color = RED; //維護(hù)紅黑樹 rbtree_insert_fixup(T, z);}

插入結(jié)點后維護(hù)紅黑樹

??我們知道新增結(jié)點是紅色，如果新結(jié)點是父節(jié)點也是紅色，那么就需要維護(hù)紅黑樹了。

??如果父結(jié)點是爺結(jié)點是左子樹，可以歸納出來三種情況。同理如果父結(jié)點是爺結(jié)點是右子樹，我們也可以歸納出來三種情況。但是這三種情況的差異就是旋轉(zhuǎn)方向的區(qū)別而已。一共是6種情況，但是歸納出來其實是3種，讀者不要搞錯了。

在下面的圖中：z表示新增結(jié)點，y表示叔結(jié)點

父結(jié)點是爺結(jié)點是左子樹

1. 叔結(jié)點是紅色的

• 將叔結(jié)點和父結(jié)點變黑，爺結(jié)點變紅
• 將當(dāng)前結(jié)點變成爺結(jié)點（因為爺結(jié)點是紅，爺結(jié)點的父節(jié)點也可能是紅，所以要遞歸維護(hù)）

添加圖片注釋，不超過 140 字（可選）

2. 叔結(jié)點是黑色的且新結(jié)點是左子樹

• 將父結(jié)點變成黑色，爺結(jié)點變成紅色
• 以爺結(jié)點為中心右旋

添加圖片注釋，不超過 140 字（可選）

3. 叔結(jié)點是黑色的且新結(jié)點是右子樹

• 以父結(jié)點為中心左旋
• 將父結(jié)點變黑色，爺結(jié)點變紅色
• 以爺結(jié)點為中心右旋

添加圖片注釋，不超過 140 字（可選）

父結(jié)點是爺結(jié)點是右子樹

1. 叔結(jié)點是紅色的

• 將叔結(jié)點和父結(jié)點變黑，爺結(jié)點變紅
• 將當(dāng)前結(jié)點變成爺結(jié)點（因為爺結(jié)點是紅，爺結(jié)點的父節(jié)點也可能是紅，所以要遞歸維護(hù)）

添加圖片注釋，不超過 140 字（可選）

2. 叔結(jié)點是黑色的且新結(jié)點是左子樹

• 以父結(jié)點為中心右旋
• 將父結(jié)點變黑色，爺結(jié)點變紅色
• 以爺結(jié)點為中心左旋

添加圖片注釋，不超過 140 字（可選）

3. 叔結(jié)點是黑色的且新結(jié)點是右子樹

• 將父結(jié)點變成黑色，爺結(jié)點變成紅色
• 以爺結(jié)點為中心左旋

添加圖片注釋，不超過 140 字（可選）

維護(hù)代碼

//修復(fù)第4條性質(zhì)void rbtree_insert_fixup(rbtree *T, rbtree_node *z) { while (z->parent->color == RED) {//父結(jié)點是紅色的，需要調(diào)整 if (z->parent == z->parent->parent->left) {//如果父結(jié)點是爺結(jié)點是左子樹 rbtree_node *y = z->parent->parent->right;//叔結(jié)點 if (y->color == RED) {//叔結(jié)點是紅色的 //先變色，叔,父變黑 z->parent->color = BLACK; y->color = BLACK; //爺結(jié)點變紅 z->parent->parent->color = RED; //下面的調(diào)整完了，調(diào)整上面 z = z->parent->parent; } else {//叔父結(jié)點是黑色 if (z == z->parent->right) {//新節(jié)點是在右邊 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 { // 如果父結(jié)點是爺結(jié)點是右子樹 rbtree_node *y = z->parent->parent->left;//叔父結(jié)點 if (y->color == RED) {//叔父結(jié)點是紅色的 //先變色，叔,父變黑 z->parent->color = BLACK; y->color = BLACK; //爺結(jié)點變紅 z->parent->parent->color = RED; //下面的調(diào)整完了，調(diào)整上面 z = z->parent->parent; } else {//叔父結(jié)點是黑色 if (z == z->parent->left) {//新節(jié)點是在左邊 z = z->parent; rbtree_right_rotate(T, z); } z->parent->color = BLACK; z->parent->parent->color = RED; rbtree_left_rotate(T, z->parent->parent); } } } //最后別忘了根節(jié)點始終是黑色 T->root->color = BLACK;}

紅黑樹刪除結(jié)點與刪除維護(hù)紅黑樹的四種情況

刪除結(jié)點

我們定義：

• 覆蓋結(jié)點：z（被指定刪除的結(jié)點，實際上被覆蓋）
• 刪除結(jié)點：y（實際上被刪除的結(jié)點，一般是后繼結(jié)點）
• 軸心結(jié)點：x（維護(hù)紅黑樹的結(jié)點）

紅黑樹刪除結(jié)點根據(jù)改結(jié)點的左右子樹分為三種情況：

對不同情況的處理：

• 情況1：直接刪除該結(jié)點
• 情況2：將該結(jié)點的唯一子樹掛到父結(jié)點上，然后刪除該結(jié)點
• 情況3：找一個刪除結(jié)點y（后繼結(jié)點）覆蓋 指定結(jié)點z，然后刪除 刪除結(jié)點y，對于這個刪除結(jié)點y來說，它的情況一定是情況1或情況2

刪除代碼

rbtree_node *rbtree_mini(rbtree *T, rbtree_node *x) { while (x->left != T->nil) { x = x->left; } return x;}//找后繼結(jié)點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); } //找到結(jié)點第一個父結(jié)點 while ((y != T->nil) && (x == y->right)) { x = y; y = y->parent; } return y;}//覆蓋結(jié)點z//刪除結(jié)點y//軸心結(jié)點xrbtree_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); } //一般x是y的右子樹，找到軸心結(jié)點 if (y->left != T->nil) { x = y->left; } else if (y->right != T->nil) { x = y->right; } //將該結(jié)點的唯一子樹掛到父結(jié)點上，然后刪除該結(jié)點 x->parent = y->parent; if (y->parent == T->nil) {//根結(jié)點 T->root = x; } else if (y == y->parent->left) { y->parent->left = x; } else { y->parent->right = x; } //進(jìn)行覆蓋操作 if (y != z) { z->key = y->key; z->value = y->value; } //黑色才需要調(diào)整 if (y->color == BLACK) { rbtree_delete_fixup(T, x); } return y;}

刪除結(jié)點后維護(hù)紅黑樹

??想一想，刪除一個結(jié)點，該結(jié)點是什么顏色的時候才需要維護(hù)紅黑樹呢？

• 如果是紅色，沒有違反任何性質(zhì)。所以如果是紅色直接刪除即可，無需維護(hù)
• 如果是黑色，黑色被刪除，那么必定違反第5條性質(zhì)，破壞了黑高，所以我們需要針對這一情況進(jìn)行維護(hù)

??如果當(dāng)前結(jié)點是父結(jié)點的左子樹的情況，可以歸納出來四種情況。同理如果當(dāng)前結(jié)點是父結(jié)點的右子樹，我們也可以歸納出來四種情況。但是這四種情況的差異就是旋轉(zhuǎn)方向的區(qū)別而已（鏡像的）。一共是8種情況，但是歸納出來其實是4種，讀者不要搞錯了。

當(dāng)前結(jié)點是父結(jié)點的左子樹的情況

1.當(dāng)前結(jié)點的兄弟結(jié)點是紅色的

• 兄弟節(jié)點變成黑色
• 父節(jié)點變成紅色
• 父節(jié)點做左旋
• 將兄弟結(jié)點調(diào)整為父節(jié)點的右子樹

添加圖片注釋，不超過 140 字（可選）

2. 當(dāng)前結(jié)點的兄弟結(jié)點是黑色的，而且兄弟結(jié)點的兩個孩子結(jié)點都是黑色的

• 兄弟節(jié)點變成紅色
• 軸心結(jié)點變?yōu)楦腹?jié)點

添加圖片注釋，不超過 140 字（可選）

3. 當(dāng)前結(jié)點的兄弟結(jié)點是黑色的，而且兄弟結(jié)點的左孩子是紅色的，右孩子是黑色的

• 將左孩子涂黑
• 將兄弟節(jié)點變紅
• 對兄弟節(jié)點右旋
• 將兄弟結(jié)點調(diào)整為父節(jié)點的右子樹
• 現(xiàn)在情況3就會變成情況4，接著做情況4的步驟

添加圖片注釋，不超過 140 字（可選）

4. 當(dāng)前結(jié)點的兄弟結(jié)點是黑色的，而且兄弟結(jié)點的左孩子是黑色的，右孩子是紅色的

• 將兄弟節(jié)點換成父節(jié)點的顏色
• 把父節(jié)點和兄弟節(jié)點的右孩子涂黑
• 對父節(jié)點做左旋
• 設(shè)置x指針，指向根節(jié)點

添加圖片注釋，不超過 140 字（可選）

當(dāng)前結(jié)點是父結(jié)點的右子樹的情況

1. 當(dāng)前結(jié)點的兄弟結(jié)點是紅色的

• 兄弟節(jié)點變成黑色
• 父節(jié)點變成紅色
• 父節(jié)點做右旋
• 將兄弟結(jié)點調(diào)整為父節(jié)點的左子樹

2. 當(dāng)前結(jié)點的兄弟結(jié)點是黑色的，而且兄弟結(jié)點的兩個孩子結(jié)點都是黑色的

• 兄弟節(jié)點變成紅色
• 軸心結(jié)點變?yōu)楦腹?jié)點

3. 當(dāng)前結(jié)點的兄弟結(jié)點是黑色的，而且兄弟結(jié)點的左孩子是黑色的，右孩子是紅色的

• 將右孩子變黑
• 將兄弟節(jié)點變紅
• 對兄弟結(jié)點左旋
• 將兄弟結(jié)點調(diào)整為父節(jié)點的左子樹
• 現(xiàn)在情況3就會變成情況4，接著做情況4的步驟

4. 當(dāng)前結(jié)點的兄弟結(jié)點是黑色的，而且兄弟結(jié)點的左孩子是紅色的，右孩子是黑色的

• 將兄弟節(jié)點換成父節(jié)點的顏色
• 把父節(jié)點和兄弟節(jié)點的左孩子變黑
• 對父節(jié)點做右旋
• 將軸心結(jié)點調(diào)整為根結(jié)點

維護(hù)代碼

void rbtree_delete_fixup(rbtree *T, rbtree_node *x) { //如果x是紅色，變成黑色，如果x是黑色，需要調(diào)整 while ((x != T->root) && (x->color == BLACK)) { //當(dāng)前結(jié)點是父結(jié)點的左子樹 if (x == x->parent->left) { //兄弟節(jié)點 rbtree_node *w = x->parent->right; // 情況1：兄弟節(jié)點為紅色 if (w->color == RED) { // 兄弟節(jié)點變成黑色 w->color = BLACK; // 父節(jié)點變成紅色 x->parent->color = RED; // 父節(jié)點做左旋 rbtree_left_rotate(T, x->parent); //將兄弟結(jié)點調(diào)整為父節(jié)點的右子樹 w = x->parent->right; } // 情況2：兄弟節(jié)點是黑色的，且兄弟的左孩子和右孩子都是黑色 if ((w->left->color == BLACK) && (w->right->color == BLACK)) { // 兄弟節(jié)點變成紅色 w->color = RED; // 軸心結(jié)點變?yōu)楦腹?jié)點 x = x->parent; } else { // 情況3：x的兄弟節(jié)點是黑色的，兄弟的左孩子是紅色，右孩子是黑色 if (w->right->color == BLACK) { // 將左孩子涂黑 w->left->color = BLACK; // 將兄弟節(jié)點變紅 w->color = RED; // 對兄弟節(jié)點右旋 rbtree_right_rotate(T, w); // 重新設(shè)置x的兄弟節(jié)點 w = x->parent->right; } // 情況4：x的兄弟節(jié)點是黑色；x的兄弟節(jié)點的右孩子是紅色的 // 將兄弟節(jié)點換成父節(jié)點的顏色 w->color = x->parent->color; // 把父節(jié)點和兄弟節(jié)點的右孩子涂黑 x->parent->color = BLACK; w->right->color = BLACK; // 對父節(jié)點做左旋 rbtree_left_rotate(T, x->parent); // 設(shè)置x指針，指向根節(jié)點 x = T->root; } } else {//當(dāng)前結(jié)點是父結(jié)點的右子樹 //兄弟節(jié)點 rbtree_node *w = x->parent->left; //情況1：兄弟結(jié)點為紅色 if (w->color == RED) { // 兄弟節(jié)點變成黑色 w->color = BLACK; // 父節(jié)點變成紅色 x->parent->color = RED; // 父節(jié)點做右旋 rbtree_right_rotate(T, x->parent); //將兄弟結(jié)點調(diào)整為父節(jié)點的左子樹 w = x->parent->left; } // 情況2：兄弟節(jié)點是黑色的，且兄弟的左孩子和右孩子都是黑色 if ((w->left->color == BLACK) && (w->right->color == BLACK)) { // 兄弟節(jié)點變成紅色 w->color = RED; // 軸心結(jié)點變?yōu)楦腹?jié)點 x = x->parent; } else { // 情況3：x的兄弟結(jié)點是黑色的，兄弟的左孩子是黑色，右孩子是紅色 if (w->left->color == BLACK) { //將右孩子變黑 w->right->color = BLACK; //將兄弟節(jié)點變紅 w->color = RED; //對兄弟結(jié)點左旋 rbtree_left_rotate(T, w); //將兄弟結(jié)點調(diào)整為父節(jié)點的左子樹 w = x->parent->left; } // 情況4：x的兄弟結(jié)點是黑色的，兄弟的左孩子是紅色，右孩子是黑色 // 將兄弟節(jié)點換成父節(jié)點的顏色 w->color = x->parent->color; // 把父節(jié)點和兄弟節(jié)點的左孩子變黑 x->parent->color = BLACK; w->left->color = BLACK; // 對父節(jié)點做右旋 rbtree_right_rotate(T, x->parent); //將軸心結(jié)點調(diào)整為根結(jié)點 x = T->root; } } } // 繼承節(jié)點變?yōu)楹谏?，為了彌補失去的黑高 x->color = BLACK;}

紅黑樹的遍歷、查詢、測試

rbtree_node *rbtree_search(rbtree *T, KEY_TYPE key) { rbtree_node *node = T->root; while (node != T->nil) { if (key 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”, 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”); 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 key = keyArray[i]; node->value = NULL; rbtree_insert(T, node); } rbtree_traversal(T, T->root); printf(“—————————————-“); for (i = 0; i root); printf(“—————————————-“); }}

原文鏈接：隨處可見的紅黑樹詳解_cheems~的博客-CSDN博客