目錄

• 1、紅黑樹原理
• • 1、紅黑樹性質(zhì)
  • 2、變換規(guī)則（從插入結(jié)點的角度來講）
  • • 1.變色
    • 2.左旋
    • 3.右旋
  • 3、刪除結(jié)點需要注意的地方
• 2、代碼
• • 1、定義結(jié)點以及構(gòu)造函數(shù)
  • 2、定義紅黑樹類以及聲明它的方法
  • 3、左旋
  • 4、右旋
  • 5、插入操作
  • 6、修正操作
  • 7、刪除操作
• 3、參考鏈接

1、紅黑樹原理

為了避免二叉搜索樹出現(xiàn)退化為鏈表的情況，出現(xiàn)了自平衡的二叉搜索樹。
AVL樹：平衡二叉樹，它的左右子樹高度之差不超過1，不過它太過于理想化。
通過性能綜合考慮選用紅黑樹。

1、紅黑樹性質(zhì)

1、每個結(jié)點不是紅色就是黑色
2、不可能有連在一起的紅色結(jié)點
3、根結(jié)點都是黑色
4、每個紅色結(jié)點的兩個子結(jié)點都是黑色。
5、葉子結(jié)點都是黑色(葉子結(jié)點指的是NULL結(jié)點)
6、 從一個節(jié)點到該節(jié)點的子孫節(jié)點的所有路徑上包含相同數(shù)目的黑節(jié)點。

2、變換規(guī)則（從插入結(jié)點的角度來講）

變換規(guī)則分為三種：

變色、左旋、右旋

1.變色

變色的前提：當(dāng)前結(jié)點的父結(jié)點是紅色，且它的祖父結(jié)點的另一個結(jié)點==(叔結(jié)點)也是紅色==。
變色的過程：

1、將父結(jié)點設(shè)為黑色
2、叔結(jié)點設(shè)為黑色
3、祖父結(jié)點設(shè)為紅色
4、把指針定義到祖父結(jié)點設(shè)為當(dāng)前要操作的結(jié)點。
5、繼續(xù)分析判斷

示例如下：
按照二叉搜索樹的規(guī)則插入對應(yīng)的結(jié)點6；發(fā)現(xiàn)違反規(guī)則了，兩個紅色的連到一起了，并且符合變色的前提，所以進(jìn)行變色

圖1 插入結(jié)點6，將其作為當(dāng)前結(jié)點

圖2 做完變色變換后，將之前的祖父結(jié)點作為當(dāng)前結(jié)點

2.左旋

觀察變色之后的樹，發(fā)現(xiàn)仍然是違反規(guī)則的：5、12兩個紅色連在一起了。
然后再看是不是符合變色的前提：顯然不符合，因為12的叔結(jié)點30不是紅色。那么這時就應(yīng)該判斷是否符合左旋的前提了。
左旋的前提：
當(dāng)前父結(jié)點是紅色，叔叔是黑色的時候，且當(dāng)前的結(jié)點是右子樹。
左旋的過程：

以父結(jié)點作為中心旋轉(zhuǎn)，動態(tài)圖如下：
1、將當(dāng)前以當(dāng)前結(jié)點為根結(jié)點的子樹(between E and S)連接到祖父結(jié)點E
2、E和S中較大的結(jié)點作為移動到根結(jié)點

左旋前后對比：

圖1 左旋前

圖2 左旋后

3.右旋

觀察左旋之后的樹，發(fā)現(xiàn)仍然是違反規(guī)則的：5、12兩個紅色的結(jié)點連在一起。且不符合變色和左旋的條件。
那么接下來就要使用右旋
右旋條件：
當(dāng)前父結(jié)點是紅色，叔結(jié)點是黑色，且當(dāng)前的結(jié)點是左子樹。
右旋的操作：

1、把父結(jié)點變?yōu)楹谏?br /> 2、把祖父結(jié)點變?yōu)榧t色
3、以祖父結(jié)點旋轉(zhuǎn)

右旋前后對比;13重新連接。

圖1 右旋前

圖2 右旋后

3、刪除結(jié)點需要注意的地方

1、將紅黑樹當(dāng)做一棵二叉搜索樹，將該結(jié)點從二叉搜索樹中刪除
2、通過旋轉(zhuǎn)和變色操作來修正這棵樹，使之重新成為一棵紅黑樹
關(guān)于二叉搜索樹的刪除結(jié)點不是這篇筆記的重點，可以參考我之前的一個刷題筆記，還是比較有用處的：

二叉搜索樹的插入、刪除、修剪、構(gòu)造操作（leetcode701、450、669、108）

怕麻煩的話也可以直接看下面的截圖：

2、代碼

1、定義結(jié)點以及構(gòu)造函數(shù)

每個結(jié)點有顏色和值，左右孩子以及父結(jié)點指針。
定義帶參構(gòu)造函數(shù)

template <class T> class RBTNode{public:RBTColor color; // 顏色T key; // 關(guān)鍵字(鍵值)RBTNode *left; // 左孩子RBTNode *right; // 右孩子RBTNode *parent; // 父結(jié)點RBTNode(T value, RBTColor c, RBTNode *p, RBTNode *l, RBTNode *r):key(value),color(c),parent(),left(l),right(r) {} };

2、定義紅黑樹類以及聲明它的方法

每棵樹有一個根結(jié)點還有空結(jié)點

template <class T> class RBTree {private:RBTNode<T> *mRoot; // 根結(jié)點public:RBTree();~RBTree();// 前序遍歷"紅黑樹"void preOrder();// 中序遍歷"紅黑樹"void inOrder();// 后序遍歷"紅黑樹"void postOrder();// (遞歸實現(xiàn))查找"紅黑樹"中鍵值為key的節(jié)點RBTNode<T>* search(T key);// (非遞歸實現(xiàn))查找"紅黑樹"中鍵值為key的節(jié)點RBTNode<T>* iterativeSearch(T key);// 查找最小結(jié)點：返回最小結(jié)點的鍵值。T minimum();// 查找最大結(jié)點：返回最大結(jié)點的鍵值。T maximum();// 找結(jié)點(x)的后繼結(jié)點。即，查找"紅黑樹中數(shù)據(jù)值大于該結(jié)點"的"最小結(jié)點"。RBTNode<T>* successor(RBTNode<T> *x);// 找結(jié)點(x)的前驅(qū)結(jié)點。即，查找"紅黑樹中數(shù)據(jù)值小于該結(jié)點"的"最大結(jié)點"。RBTNode<T>* predecessor(RBTNode<T> *x);// 將結(jié)點(key為節(jié)點鍵值)插入到紅黑樹中void insert(T key);// 刪除結(jié)點(key為節(jié)點鍵值)void remove(T key);// 銷毀紅黑樹void destroy();// 打印紅黑樹void print();private:// 前序遍歷"紅黑樹"void preOrder(RBTNode<T>* tree) const;// 中序遍歷"紅黑樹"void inOrder(RBTNode<T>* tree) const;// 后序遍歷"紅黑樹"void postOrder(RBTNode<T>* tree) const;// (遞歸實現(xiàn))查找"紅黑樹x"中鍵值為key的節(jié)點RBTNode<T>* search(RBTNode<T>* x, T key) const;// (非遞歸實現(xiàn))查找"紅黑樹x"中鍵值為key的節(jié)點RBTNode<T>* iterativeSearch(RBTNode<T>* x, T key) const;// 查找最小結(jié)點：返回tree為根結(jié)點的紅黑樹的最小結(jié)點。RBTNode<T>* minimum(RBTNode<T>* tree);// 查找最大結(jié)點：返回tree為根結(jié)點的紅黑樹的最大結(jié)點。RBTNode<T>* maximum(RBTNode<T>* tree);// 左旋void leftRotate(RBTNode<T>* &root, RBTNode<T>* x);// 右旋void rightRotate(RBTNode<T>* &root, RBTNode<T>* y);// 插入函數(shù)void insert(RBTNode<T>* &root, RBTNode<T>* node);// 插入修正函數(shù)void insertFixUp(RBTNode<T>* &root, RBTNode<T>* node);// 刪除函數(shù)void remove(RBTNode<T>* &root, RBTNode<T> *node);// 刪除修正函數(shù)void removeFixUp(RBTNode<T>* &root, RBTNode<T> *node, RBTNode<T> *parent);// 銷毀紅黑樹void destroy(RBTNode<T>* &tree);// 打印紅黑樹void print(RBTNode<T>* tree, T key, int direction);#define rb_parent(r) ((r)->parent) #define rb_color(r) ((r)->color) #define rb_is_red(r) ((r)->color==RED) #define rb_is_black(r) ((r)->color==BLACK) #define rb_set_black(r) do { (r)->color = BLACK; } while (0) #define rb_set_red(r) do { (r)->color = RED; } while (0) #define rb_set_parent(r,p) do { (r)->parent = (p); } while (0) #define rb_set_color(r,c) do { (r)->color = (c); } while (0) };

3、左旋

/* * 對紅黑樹的節(jié)點(x)進(jìn)行左旋轉(zhuǎn)** 左旋示意圖(對節(jié)點x進(jìn)行左旋)：* px px* / /* x y * / \ --(左旋)--> / \ #* lx y x ry * / \ / \* ly ry lx ly ***/ template <class T> void RBTree<T>::leftRotate(RBTNode<T>* &root, RBTNode<T>* x) {// 設(shè)置x的右孩子為yRBTNode<T> *y = x->right;// 將 “y的左孩子” 設(shè)為 “x的右孩子”；// 如果y的左孩子非空，將 “x” 設(shè)為 “y的左孩子的父親”x->right = y->left;if (y->left != NULL)y->left->parent = x;// 將 “x的父親” 設(shè)為 “y的父親”y->parent = x->parent;if (x->parent == NULL){root = y; // 如果 “x的父親” 是空節(jié)點，則將y設(shè)為根節(jié)點}else{if (x->parent->left == x)x->parent->left = y; // 如果 x是它父節(jié)點的左孩子，則將y設(shè)為“x的父節(jié)點的左孩子”elsex->parent->right = y; // 如果 x是它父節(jié)點的左孩子，則將y設(shè)為“x的父節(jié)點的左孩子”}// 將 “x” 設(shè)為 “y的左孩子”y->left = x;// 將 “x的父節(jié)點” 設(shè)為 “y”x->parent = y; }

4、右旋

/* * 對紅黑樹的節(jié)點(y)進(jìn)行右旋轉(zhuǎn)** 右旋示意圖(對節(jié)點y進(jìn)行左旋)：* py py* / /* y x * / \ --(右旋)--> / \ #* x ry lx y * / \ / \ #* lx rx rx ry* */ template <class T> void RBTree<T>::rightRotate(RBTNode<T>* &root, RBTNode<T>* y) {// 設(shè)置x是當(dāng)前節(jié)點的左孩子。RBTNode<T> *x = y->left;// 將 “x的右孩子” 設(shè)為 “y的左孩子”；// 如果"x的右孩子"不為空的話，將 “y” 設(shè)為 “x的右孩子的父親”y->left = x->right;if (x->right != NULL)x->right->parent = y;// 將 “y的父親” 設(shè)為 “x的父親”x->parent = y->parent;if (y->parent == NULL) {root = x; // 如果 “y的父親” 是空節(jié)點，則將x設(shè)為根節(jié)點}else{if (y == y->parent->right)y->parent->right = x; // 如果 y是它父節(jié)點的右孩子，則將x設(shè)為“y的父節(jié)點的右孩子”elsey->parent->left = x; // (y是它父節(jié)點的左孩子) 將x設(shè)為“x的父節(jié)點的左孩子”}// 將 “y” 設(shè)為 “x的右孩子”x->right = y;// 將 “y的父節(jié)點” 設(shè)為 “x”y->parent = x; }

5、插入操作

內(nèi)部接口 – insert(root, node)的作用是將"node"節(jié)點插入到紅黑樹中。其中，root是根，node是被插入節(jié)點。
外部接口 – insert(key)的作用是將"key"添加到紅黑樹中。

/* * 將結(jié)點插入到紅黑樹中** 參數(shù)說明：* root 紅黑樹的根結(jié)點* node 插入的結(jié)點 // 對應(yīng)《算法導(dǎo)論》中的node*/ template <class T> void RBTree<T>::insert(RBTNode<T>* &root, RBTNode<T>* node) {RBTNode<T> *y = NULL;RBTNode<T> *x = root;// 1. 將紅黑樹當(dāng)作一顆二叉查找樹，將節(jié)點添加到二叉查找樹中。while (x != NULL){y = x;if (node->key < x->key)x = x->left;elsex = x->right;}node->parent = y;if (y!=NULL){if (node->key < y->key)y->left = node;elsey->right = node;}elseroot = node;// 2. 設(shè)置節(jié)點的顏色為紅色node->color = RED;// 3. 將它重新修正為一顆二叉查找樹insertFixUp(root, node); }/* * 將結(jié)點(key為節(jié)點鍵值)插入到紅黑樹中** 參數(shù)說明：* tree 紅黑樹的根結(jié)點* key 插入結(jié)點的鍵值*/ template <class T> void RBTree<T>::insert(T key) {RBTNode<T> *z=NULL;// 如果新建結(jié)點失敗，則返回。if ((z=new RBTNode<T>(key,BLACK,NULL,NULL,NULL)) == NULL)return ;insert(mRoot, z); }

6、修正操作

根據(jù)條件，分別進(jìn)行變色、左旋、右旋操作，最后再將根結(jié)點置為黑色。
對于叔叔結(jié)點是組父結(jié)點的左孩子還是右孩子需要分類討論。
操作的具體步驟，可以返回上文對比看。
insertFixUp(root, node)的作用是對應(yīng)"上面所講的第三步"。它是一個內(nèi)部接口。

/** 紅黑樹插入修正函數(shù)** 在向紅黑樹中插入節(jié)點之后(失去平衡)，再調(diào)用該函數(shù)；* 目的是將它重新塑造成一顆紅黑樹。** 參數(shù)說明：* root 紅黑樹的根* node 插入的結(jié)點 // 對應(yīng)《算法導(dǎo)論》中的z*/ template <class T> void RBTree<T>::insertFixUp(RBTNode<T>* &root, RBTNode<T>* node) {RBTNode<T> *parent, *gparent;// 若“父節(jié)點存在，并且父節(jié)點的顏色是紅色”while ((parent = rb_parent(node)) && rb_is_red(parent)){gparent = rb_parent(parent);//若“父節(jié)點”是“祖父節(jié)點的左孩子”if (parent == gparent->left){RBTNode<T> *uncle = gparent->right;// Case 1條件：叔叔節(jié)點是紅色,此時采用變色if (uncle && rb_is_red(uncle)){rb_set_black(uncle);rb_set_black(parent);rb_set_red(gparent);node = gparent;continue;}// Case 2條件：叔叔是黑色，且當(dāng)前節(jié)點是右孩子,此時采用左旋if (parent->right == node){RBTNode<T> *tmp;leftRotate(root, parent);tmp = parent;parent = node;node = tmp;}// Case 3條件：叔叔是黑色，且當(dāng)前節(jié)點是左孩子,此時采用右旋rb_set_black(parent);rb_set_red(gparent);rightRotate(root, gparent);} else//若“z的父節(jié)點”是“z的祖父節(jié)點的右孩子”{RBTNode<T> *uncle = gparent->left;// Case 1條件：叔叔節(jié)點是紅色if (uncle && rb_is_red(uncle)){rb_set_black(uncle);rb_set_black(parent);rb_set_red(gparent);node = gparent;continue;}// Case 2條件：叔叔是黑色，且當(dāng)前節(jié)點是左孩子if (parent->left == node){RBTNode<T> *tmp;rightRotate(root, parent);tmp = parent;parent = node;node = tmp;}// Case 3條件：叔叔是黑色，且當(dāng)前節(jié)點是右孩子。rb_set_black(parent);rb_set_red(gparent);leftRotate(root, gparent);}}// 將根節(jié)點設(shè)為黑色rb_set_black(root); }

7、刪除操作

將紅黑樹內(nèi)的某一個節(jié)點刪除。需要執(zhí)行的操作依次是：首先，將紅黑樹當(dāng)作一顆二叉查找樹，將該節(jié)點從二叉查找樹中刪除；然后，通過"旋轉(zhuǎn)和重新著色"等一系列來修正該樹，使之重新成為一棵紅黑樹。

3、參考鏈接

1、紅黑樹 - C++代碼實現(xiàn)
2、leetcode刷題(十）：樹（紅黑樹，B樹）
3、B站視頻,關(guān)于紅黑樹的推導(dǎo)
4、慕課視頻，關(guān)于模板類的寫法指導(dǎo)
5、二叉搜索樹的插入、刪除、修剪、構(gòu)造操作（leetcode701、450、669、108）
6、紅黑樹的刪除調(diào)整過程(轉(zhuǎn)載)

總結(jié)

以上是生活随笔為你收集整理的红黑树的实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。