紅黑樹(shù)的特點(diǎn)及應(yīng)用
比起理解紅黑樹(shù)的原理，更重要的是理解紅黑樹(shù)的應(yīng)用場(chǎng)景，因?yàn)槟承?yīng)用場(chǎng)景的需要，紅黑樹(shù)才會(huì)應(yīng)運(yùn)而生。
紅黑樹(shù)的特點(diǎn)：
插入，刪除，查找都是O(logn)的復(fù)雜度。
紅黑樹(shù)的應(yīng)用：
- epoll的實(shí)現(xiàn)，內(nèi)核會(huì)在內(nèi)存開(kāi)辟一個(gè)空間存放epoll的紅黑樹(shù)，并將每個(gè)epollfd加入到紅黑樹(shù)中，一般epoll會(huì)設(shè)置LT水平觸發(fā)，當(dāng)網(wǎng)卡有數(shù)據(jù)到來(lái)，可讀緩沖區(qū)不為空，會(huì)觸發(fā)回調(diào)EPOLLIN事件，而之前注冊(cè)了對(duì)EPOLLIN事件感興趣的socketfd會(huì)有專門的隊(duì)列存儲(chǔ)，內(nèi)核會(huì)遍歷隊(duì)列搜尋對(duì)應(yīng)的socketfd，因?yàn)樵诩t黑樹(shù)里找有近似O(logn)的時(shí)間復(fù)雜度，所以10億個(gè)socket也只需要20次查找。
- 進(jìn)程調(diào)度，內(nèi)核CFS隊(duì)列，以紅黑樹(shù)的形式存儲(chǔ)進(jìn)程信息。
- 有的hashtable（記得是java），當(dāng)沖突時(shí)不以鏈表來(lái)組織重復(fù)元素，而是以紅黑樹(shù)的形式來(lái)組織。
- 內(nèi)存管理，比如空閑鏈表freelist可以通過(guò)紅黑樹(shù)來(lái)組織，這樣malloc的時(shí)候要找到符合大小的內(nèi)存塊，如果不是firstfit的原則，而是全局最優(yōu)大小原則，想找到適合的內(nèi)存塊就可以通過(guò)紅黑樹(shù)來(lái)找。
- Nginx的Timer事件管理。
紅黑樹(shù)定義
寫(xiě)代碼之前先寫(xiě)一下紅黑樹(shù)的規(guī)則吧
- 每個(gè)顏色不是紅就是黑。
- 根節(jié)點(diǎn)必黑
- 葉子節(jié)點(diǎn)必黑
- 紅色節(jié)點(diǎn)的左右孩子都為黑
- 每個(gè)節(jié)點(diǎn)到其葉子節(jié)點(diǎn)（nil）的所有路徑上的黑色節(jié)點(diǎn)數(shù)量都一樣
我的理解：從任一節(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑上，路徑的元素必然有黑色節(jié)點(diǎn)，而路徑的長(zhǎng)度則取決于路徑上紅色節(jié)點(diǎn)的數(shù)量，最短的路徑上，所有節(jié)點(diǎn)都是黑色，這種情況下，查找效率為真實(shí)的O(logn)，和嚴(yán)格平衡的AVL樹(shù)一致。而如果在剛剛的最短路徑上，也就是所有黑色節(jié)點(diǎn)的中間插入紅色節(jié)點(diǎn)，這樣是不會(huì)打破紅黑樹(shù)的平衡的(規(guī)則5)，此時(shí)便是最長(zhǎng)路徑，查找效率為2logn，但依然和logn在同一數(shù)量級(jí)，因此，紅黑樹(shù)的查找效率可以看做是(Ologn)，同時(shí)比AVL樹(shù)擁有更高的插入和刪除效率。
紅黑樹(shù)代碼框架
//-既然標(biāo)題是c++，那么就寫(xiě)成滿滿的c++風(fēng)格吧
using Color = bool;//-顏色因?yàn)橹挥屑t或者黑，選擇bool類型
using KEY_TYPE = int;//-為了更好理解紅黑樹(shù)，就不寫(xiě)成模板類了，所以首選萬(wàn)年int（笑~）
using VALUE_TYPE = int;//-同理
//-全局靜態(tài)紅黑變量
static const Color red = false;
static const Color black = true;
//-紅黑樹(shù)的節(jié)點(diǎn)特點(diǎn)，有color，有parent
class RBtree_node{
public:
Color color;
RBtree_node * parent;
RBtree_node * left;
RBtree_node * right;
KEY_TYPE key;//-后期如果想解耦合，可以將key和value抽離出去
VALUE_TYPE value;
RBtree_node(Color color_):color(color_),parent(nullptr),left(nullptr),right(nullptr),key(-99999){}
RBtree_node(Color color_, KEY_TYPE key_,RBtree_node * nil):
color(color_),parent(nil),left(nil),right(nil),key(key_){}
};
class RBtree{
private:
//-紅黑樹(shù)數(shù)據(jù)成員：其中nil的意義在于，因?yàn)榧t黑樹(shù)的所有葉子節(jié)點(diǎn)都是黑色的，所以可以將所有臨近末尾的節(jié)點(diǎn)，
//-都連接到這一個(gè)葉子結(jié)點(diǎn)nil上，同理，root的parent也可以連接到nil上，形成一個(gè)dummy空節(jié)點(diǎn)
RBtree_node * root;
RBtree_node * nil;
public :
//-以下實(shí)現(xiàn)了紅黑樹(shù)常用接口：
//-構(gòu)造函數(shù)
RBtree(){
nil = new RBtree_node(black);//-為所有葉子節(jié)點(diǎn)nil初始化，顏色為黑色
root = nil;//-紅黑樹(shù)為空的時(shí)候，讓nil作為root
}
//-左旋
void leftRotate(RBtree_node *left_node);
//- 右旋
void rightRotate(RBtree_node * right_node);
//-插入key
void insertNode(KEY_TYPE key);
//-修復(fù)插入
void fixInsert(RBtree_node * node);
//-查找某個(gè)key的節(jié)點(diǎn)
RBtree_node* searchNode(KEY_TYPE key);
//-查找某個(gè)節(jié)點(diǎn)的中序后繼
RBtree_node* successor(RBtree_node * node);
//-刪除key
void deleteNode(KEY_TYPE key);
//-修復(fù)刪除
void fixDelete(RBtree_node * node);
//-層序遍歷打印紅黑樹(shù)
void print();
//-打印中序遍歷
void printMiddle(RBtree_node * node);
};
using Color = bool;//-顏色因?yàn)橹挥屑t或者黑，選擇bool類型
using KEY_TYPE = int;//-為了更好理解紅黑樹(shù)，就不寫(xiě)成模板類了，所以首選萬(wàn)年int（笑~）
using VALUE_TYPE = int;//-同理
//-全局靜態(tài)紅黑變量
static const Color red = false;
static const Color black = true;
//-紅黑樹(shù)的節(jié)點(diǎn)特點(diǎn)，有color，有parent
class RBtree_node{
public:
Color color;
RBtree_node * parent;
RBtree_node * left;
RBtree_node * right;
KEY_TYPE key;//-后期如果想解耦合，可以將key和value抽離出去
VALUE_TYPE value;
RBtree_node(Color color_):color(color_),parent(nullptr),left(nullptr),right(nullptr),key(-99999){}
RBtree_node(Color color_, KEY_TYPE key_,RBtree_node * nil):
color(color_),parent(nil),left(nil),right(nil),key(key_){}
};
class RBtree{
private:
//-紅黑樹(shù)數(shù)據(jù)成員：其中nil的意義在于，因?yàn)榧t黑樹(shù)的所有葉子節(jié)點(diǎn)都是黑色的，所以可以將所有臨近末尾的節(jié)點(diǎn)，
//-都連接到這一個(gè)葉子結(jié)點(diǎn)nil上，同理，root的parent也可以連接到nil上，形成一個(gè)dummy空節(jié)點(diǎn)
RBtree_node * root;
RBtree_node * nil;
public :
//-以下實(shí)現(xiàn)了紅黑樹(shù)常用接口：
//-構(gòu)造函數(shù)
RBtree(){
nil = new RBtree_node(black);//-為所有葉子節(jié)點(diǎn)nil初始化，顏色為黑色
root = nil;//-紅黑樹(shù)為空的時(shí)候，讓nil作為root
}
//-左旋
void leftRotate(RBtree_node *left_node);
//- 右旋
void rightRotate(RBtree_node * right_node);
//-插入key
void insertNode(KEY_TYPE key);
//-修復(fù)插入
void fixInsert(RBtree_node * node);
//-查找某個(gè)key的節(jié)點(diǎn)
RBtree_node* searchNode(KEY_TYPE key);
//-查找某個(gè)節(jié)點(diǎn)的中序后繼
RBtree_node* successor(RBtree_node * node);
//-刪除key
void deleteNode(KEY_TYPE key);
//-修復(fù)刪除
void fixDelete(RBtree_node * node);
//-層序遍歷打印紅黑樹(shù)
void print();
//-打印中序遍歷
void printMiddle(RBtree_node * node);
};
接下來(lái)將接口一一實(shí)現(xiàn)：
紅黑樹(shù)節(jié)點(diǎn)左旋右旋：
實(shí)現(xiàn)參照該圖，至于學(xué)習(xí)方法也沒(méi)啥捷徑，只能把這個(gè)結(jié)構(gòu)圖和變換方式深深印刻在腦海里。
手撕代碼的時(shí)候想象一下還是容易寫(xiě)的，如果覺(jué)得這樣很累就紙上畫(huà)個(gè)草圖。
由于左旋和右旋是對(duì)稱的，所以規(guī)則只需要記一半。
圖1 左旋右旋
//-左旋
void RBtree::leftRotate(RBtree_node *left_node){
RBtree_node * right_node = left_node->right;//-右節(jié)點(diǎn)的左枝條接在左節(jié)點(diǎn)的右枝條上
left_node->right = right_node->left;
if(right_node->left!=nil){
left_node->right->parent = left_node;
}
//-右節(jié)點(diǎn)接在左節(jié)點(diǎn)的父親上
right_node->parent = left_node->parent;
if(left_node == root){
//-nil不會(huì)指向任何節(jié)點(diǎn)，但是root->parent是nil
root = right_node;
}
else if(left_node == left_node->parent->left){
left_node->parent->left = right_node;
}else{
left_node->parent->right = right_node;
}
//-左節(jié)點(diǎn)接在右節(jié)點(diǎn)的左枝上
left_node->parent = right_node;
right_node->left = left_node;
}
//- 右旋：寫(xiě)完左旋后，把所有l(wèi)eft和right對(duì)調(diào)即可
void RBtree::rightRotate(RBtree_node * right_node){
RBtree_node * left_node = right_node->left;
right_node->left = left_node->right;
if(left_node->right!=nil){
right_node->left->parent = right_node;
}
left_node->parent = right_node->parent;
if(right_node == root){
root = left_node;
}
else if(right_node == right_node->parent->right){
right_node->parent->right = left_node;
}else{
right_node->parent->left = left_node;
}
right_node->parent = left_node;
left_node->right = right_node;
}
紅黑樹(shù)的插入，插入修復(fù)
插入的步驟原理：
- 找到插入位置，注意紅黑樹(shù)新節(jié)點(diǎn)的插入位置都是葉子結(jié)點(diǎn)。
- 如果紅黑樹(shù)中沒(méi)有節(jié)點(diǎn)，插入節(jié)點(diǎn)需要改變r(jià)oot指向，同時(shí)將root的parent指向nil。
- 改變插入節(jié)點(diǎn)父親的左右指針，同時(shí)插入節(jié)點(diǎn)本身的左右指針指向nil。
- 如果插入節(jié)點(diǎn)的父親是紅色，說(shuō)明平衡被打破了，需要執(zhí)行修復(fù)插入，讓紅黑樹(shù)恢復(fù)平衡
要點(diǎn):
- 如果在查找的時(shí)候發(fā)現(xiàn)元素已經(jīng)存在，我這里就直接拋棄了新元素的插入，如果要實(shí)現(xiàn)紅黑樹(shù)multimap的insert_equal功能可以自己實(shí)現(xiàn)一下。
- 為什么要插入修復(fù)？
首先我們會(huì)強(qiáng)制默認(rèn)所有的新節(jié)點(diǎn)都是紅色節(jié)點(diǎn)。
因?yàn)榧t色節(jié)點(diǎn)不論插在哪個(gè)位置，都不會(huì)破壞規(guī)則5（路徑上黑色節(jié)點(diǎn)數(shù)量相同），唯一可能破壞的是規(guī)則4（紅色節(jié)點(diǎn)的孩子必黑），由于破壞規(guī)則5比破壞規(guī)則4要容易得多，所以將新節(jié)點(diǎn)設(shè)置為紅色可以盡量地避免破壞規(guī)則。
當(dāng)新的紅色節(jié)點(diǎn)插入到一個(gè)紅色節(jié)點(diǎn)之后，破壞了規(guī)則4，才需要修復(fù)，如圖2，插入元素16
修復(fù)的意義和規(guī)則在于，如何將新紅節(jié)點(diǎn)的父親（34）變成黑色后，依然能保持紅黑樹(shù)的左右平衡，這個(gè)時(shí)候才涉及到對(duì)伯父節(jié)點(diǎn)（184）的討論
插入修復(fù)的步驟原理：
- 我們的目的是為了讓左邊cur為紅的情況下，使父親變黑且不會(huì)破壞平衡。
- 所以只要cur的parent是紅色，就一直循環(huán)。
- 判斷伯父節(jié)點(diǎn)（184），如果伯父節(jié)點(diǎn)是紅色，如圖2，那么同時(shí)將父親和伯父改成黑色就不會(huì)改變平衡，將祖父（101）變紅，讓cur變成祖父（101）進(jìn)入下一輪迭代。
圖2 伯父（184）為紅
如果伯父節(jié)點(diǎn)是黑色，如圖3，插入節(jié)點(diǎn)16
圖3 伯父（184）為黑
那么將父親（34）變黑就會(huì)讓左邊多一個(gè)黑色，不過(guò)可以通過(guò)讓祖父（101）變紅，旋轉(zhuǎn)祖父，讓祖父下沉，父親上浮，這樣相當(dāng)于讓老爹變黑同時(shí)左右都加了一個(gè)黑色，不會(huì)破壞平衡。
- 但是旋轉(zhuǎn)祖父需要有個(gè)前提條件，插入節(jié)點(diǎn)不能是父親的靠?jī)?nèi)節(jié)點(diǎn)，如圖4，插入節(jié)點(diǎn)（36）為右孩子，父親（34）是祖父（101）左枝。
圖4，插入節(jié)點(diǎn)（36）是靠?jī)?nèi)節(jié)點(diǎn)
一旦右旋祖父（101），就會(huì)破壞cur（36）和父親（34）的連接關(guān)系，所以必須要把cur從靠?jī)?nèi)節(jié)點(diǎn)變成靠外節(jié)，一個(gè)方便的方式是讓父親成為新cur（34），并右旋cur（34），如圖5，之后再進(jìn)行上個(gè)步驟，將新父親（36）變黑，祖父（101）變紅，右旋祖父。
圖5 原cur（36）經(jīng)過(guò)旋轉(zhuǎn)變?yōu)楦赣H，將34作為新cur
要點(diǎn)：
- 終止條件，當(dāng)當(dāng)前節(jié)點(diǎn)（紅）的父親為黑的時(shí)候打破循環(huán)（注意回溯到nil的時(shí)候的，nil也是黑色）
- 終止循環(huán)后，注意如果回溯到root，會(huì)改變r(jià)oot的顏色為紅，需要在循環(huán)結(jié)束后fix成黑色。
- 因?yàn)楦赣H是祖父左枝也好右枝也好，變換總是左右對(duì)稱的，所以規(guī)則只需要記一半。
//-插入key
void RBtree::insertNode(KEY_TYPE key){
RBtree_node * prev = nil;
RBtree_node * cur = root;
while(cur!=nil){
prev = cur;
if(key>cur->key){
cur = cur->right;
}else if(keykey){
cur = cur->left;
}else{//-該key已經(jīng)存在
return;
}
}
//-創(chuàng)建新節(jié)點(diǎn)
RBtree_node * new_node = new RBtree_node(red,key,nil);
//-如果節(jié)點(diǎn)沒(méi)有元素
new_node->parent = prev;
if(prev == nil){
root = new_node;
}
else if(key key){
prev ->left = new_node;
}else{
prev ->right = new_node;
}
fixInsert(new_node);
print();
}
//-修復(fù)插入
void RBtree::fixInsert(RBtree_node * new_node){
while(new_node -> parent->color == red){//-終止條件要注意
//-如果父親是左枝
if(new_node->parent == new_node -> parent->parent->left){
//-獲得其伯父節(jié)點(diǎn)
RBtree_node * uncle = new_node->parent->parent->right;
if(uncle->color == red){//-如果伯父是紅色，那么將父親和伯父同時(shí)變黑，不會(huì)破壞左右平衡
uncle->color = black;
new_node->parent->color = black;
new_node->parent ->parent->color = red;//-將祖父變紅，才能實(shí)現(xiàn)下一輪回溯修復(fù)
new_node = new_node->parent->parent;
}else{//-如果伯父是黑色
//-判斷new_node是不是右孩子，如果是右孩子轉(zhuǎn)換成左孩子
if(new_node == new_node -> parent->right){
new_node = new_node->parent;
leftRotate(new_node);
}
//-此時(shí)紅色節(jié)點(diǎn)是左孩子
//-如果結(jié)構(gòu)本是平衡狀態(tài)，右邊本該比左邊多一個(gè)黑，但是我們將父親（左)變黑會(huì)破壞平衡，
//-所以需要右旋祖父，把父親上浮，相當(dāng)于在左枝多一個(gè)黑的時(shí)候給右枝也多了黑，這樣左右就能平衡
new_node->parent->color = black;
new_node->parent ->parent->color = red;
rightRotate(new_node->parent->parent);
}
}
//-如果父親是右枝（將上邊代碼的left和right全部對(duì)調(diào)即可，不用記規(guī)則）
else {
RBtree_node * uncle = new_node->parent->parent->left;
if(uncle->color == red){//-如果伯父是紅色
uncle->color = black;
new_node->parent->color = black;
new_node->parent ->parent->color = red;
new_node = new_node->parent->parent;
}else{//-如果伯父是黑色
if(new_node == new_node -> parent->left){
new_node = new_node->parent;
rightRotate(new_node);
}
new_node->parent->color = black;
new_node->parent ->parent->color = red;
leftRotate(new_node->parent->parent);
}
}
}
//-如果new_node回溯到root，此時(shí)root->parent==nil（black）打破了循環(huán)，而此時(shí)root被改變成了黑色，違反了規(guī)則1，
//-所以最后需要強(qiáng)行把root fix成黑色
root->color = black;
}
void RBtree::insertNode(KEY_TYPE key){
RBtree_node * prev = nil;
RBtree_node * cur = root;
while(cur!=nil){
prev = cur;
if(key>cur->key){
cur = cur->right;
}else if(keykey){
cur = cur->left;
}else{//-該key已經(jīng)存在
return;
}
}
//-創(chuàng)建新節(jié)點(diǎn)
RBtree_node * new_node = new RBtree_node(red,key,nil);
//-如果節(jié)點(diǎn)沒(méi)有元素
new_node->parent = prev;
if(prev == nil){
root = new_node;
}
else if(key key){
prev ->left = new_node;
}else{
prev ->right = new_node;
}
fixInsert(new_node);
print();
}
//-修復(fù)插入
void RBtree::fixInsert(RBtree_node * new_node){
while(new_node -> parent->color == red){//-終止條件要注意
//-如果父親是左枝
if(new_node->parent == new_node -> parent->parent->left){
//-獲得其伯父節(jié)點(diǎn)
RBtree_node * uncle = new_node->parent->parent->right;
if(uncle->color == red){//-如果伯父是紅色，那么將父親和伯父同時(shí)變黑，不會(huì)破壞左右平衡
uncle->color = black;
new_node->parent->color = black;
new_node->parent ->parent->color = red;//-將祖父變紅，才能實(shí)現(xiàn)下一輪回溯修復(fù)
new_node = new_node->parent->parent;
}else{//-如果伯父是黑色
//-判斷new_node是不是右孩子，如果是右孩子轉(zhuǎn)換成左孩子
if(new_node == new_node -> parent->right){
new_node = new_node->parent;
leftRotate(new_node);
}
//-此時(shí)紅色節(jié)點(diǎn)是左孩子
//-如果結(jié)構(gòu)本是平衡狀態(tài)，右邊本該比左邊多一個(gè)黑，但是我們將父親（左)變黑會(huì)破壞平衡，
//-所以需要右旋祖父，把父親上浮，相當(dāng)于在左枝多一個(gè)黑的時(shí)候給右枝也多了黑，這樣左右就能平衡
new_node->parent->color = black;
new_node->parent ->parent->color = red;
rightRotate(new_node->parent->parent);
}
}
//-如果父親是右枝（將上邊代碼的left和right全部對(duì)調(diào)即可，不用記規(guī)則）
else {
RBtree_node * uncle = new_node->parent->parent->left;
if(uncle->color == red){//-如果伯父是紅色
uncle->color = black;
new_node->parent->color = black;
new_node->parent ->parent->color = red;
new_node = new_node->parent->parent;
}else{//-如果伯父是黑色
if(new_node == new_node -> parent->left){
new_node = new_node->parent;
rightRotate(new_node);
}
new_node->parent->color = black;
new_node->parent ->parent->color = red;
leftRotate(new_node->parent->parent);
}
}
}
//-如果new_node回溯到root，此時(shí)root->parent==nil（black）打破了循環(huán)，而此時(shí)root被改變成了黑色，違反了規(guī)則1，
//-所以最后需要強(qiáng)行把root fix成黑色
root->color = black;
}
紅黑樹(shù)查找某個(gè)key，以及找到某個(gè)節(jié)點(diǎn)的中序后繼
主要講下怎么根據(jù)當(dāng)前節(jié)點(diǎn)找中序后繼，根據(jù)BST的特性
- 如果當(dāng)前節(jié)點(diǎn)有右孩子：其后繼肯定在右枝條上，且是右枝條最左邊的元素。
- 如果當(dāng)前節(jié)點(diǎn)沒(méi)有右孩子：根據(jù)中序遍歷的遞歸順序，假設(shè)cur是其父親的左孩子，cur遍歷完后，下一個(gè)節(jié)點(diǎn)（后繼）就是父親，反之，如果cur是右孩子，說(shuō)明其父親也遞歸完了，需要回溯父親的父親，所以只需要一直往上找直到cur為其parent的左孩子為止，然后返回parent，而回溯到root的時(shí)候，root的父親雖然是nil，但是nil是沒(méi)有左右孩子的，所以退出循環(huán)。
//-查找某個(gè)key的節(jié)點(diǎn)
RBtree_node* RBtree::searchNode(KEY_TYPE key){
RBtree_node * cur = root;
while(cur!=nil){
if(key>cur -> key){
cur = cur->right;
}else if(key < cur -> key){
cur = cur->left;
}else{
return cur;
}
}
return cur;
}
//-查找某個(gè)節(jié)點(diǎn)的中序后繼
RBtree_node* RBtree::successor(RBtree_node * node){
//-如果節(jié)點(diǎn)有右孩子
if(node->right!=nil){
RBtree_node * res = node -> right;
while(res->left!=nil){
res = res->left;
}
return res;
}else{
while(node!=root&&node!=node->parent->left){
node = node->parent;
}
return node->parent;
}
}
RBtree_node* RBtree::searchNode(KEY_TYPE key){
RBtree_node * cur = root;
while(cur!=nil){
if(key>cur -> key){
cur = cur->right;
}else if(key < cur -> key){
cur = cur->left;
}else{
return cur;
}
}
return cur;
}
//-查找某個(gè)節(jié)點(diǎn)的中序后繼
RBtree_node* RBtree::successor(RBtree_node * node){
//-如果節(jié)點(diǎn)有右孩子
if(node->right!=nil){
RBtree_node * res = node -> right;
while(res->left!=nil){
res = res->left;
}
return res;
}else{
while(node!=root&&node!=node->parent->left){
node = node->parent;
}
return node->parent;
}
}
紅黑樹(shù)刪除，修復(fù)刪除
刪除的步驟原理：
- 類似二叉堆，當(dāng)我們從棧頂pop元素后，需要用二叉樹(shù)末尾節(jié)點(diǎn)代替原來(lái)的root，而后從二叉堆頂部開(kāi)始向下修復(fù)，同理，我們要?jiǎng)h除樹(shù)上的一個(gè)節(jié)點(diǎn)，自然需要一個(gè)節(jié)點(diǎn)來(lái)頂替刪除節(jié)點(diǎn)(key_node)的位置，因次，我們并不一定要在數(shù)據(jù)結(jié)構(gòu)上真正刪除key_node，可以找到那個(gè)頂替節(jié)點(diǎn)(delete_node)，將頂替節(jié)點(diǎn)的數(shù)據(jù)覆蓋key_node，而在數(shù)據(jù)結(jié)構(gòu)上真正刪除的是那個(gè)頂替節(jié)點(diǎn)（delete_node）。
- 在數(shù)據(jù)結(jié)構(gòu)上真正刪除哪個(gè)節(jié)點(diǎn)（delete_node怎么?。Q于(key_node)是否有左右枝條，
- 如果key_node左右孩子都沒(méi)有，說(shuō)明是葉子節(jié)點(diǎn)，直接刪除key_node即可，delete_node就是key_node本身。
- 如果key_node左右孩子只有其一，那么刪除key_node只需要將孩子接在祖父上，刪除自己即可，所以delete_node依舊是key_node本身。
- 如果key_node左右孩子都有，那么可以根據(jù)上面的successor函數(shù)，找到key_node的直接后繼，也就是刪除節(jié)點(diǎn)右邊最小的元素，將其本身數(shù)據(jù)用來(lái)頂替key_node，不會(huì)破壞BST的性質(zhì)。之后將其作為delete_node在數(shù)據(jù)結(jié)構(gòu)上刪除即可，如圖6。
圖6
找到delete_node后，還要找到delete_node的孩子（delete_son），將delete_son接在delete_node的父親上。
- 判斷delete_node是否是黑色，如果是黑色，則刪除了該元素必會(huì)破壞紅黑樹(shù)的平衡（規(guī)則5），需要修復(fù)fix_delete，而修復(fù)從delete_son開(kāi)始。
要點(diǎn)：
- 記得額外判斷如果delete_node是root的情況，需要更新其孩子delete_son為新的root。
修復(fù)刪除的步驟原理：
- 刪除節(jié)點(diǎn)delete_node如果是黑色的，說(shuō)明樹(shù)中有一個(gè)枝條（假設(shè)是左枝）的黑色節(jié)點(diǎn)必會(huì)比兄弟枝條（右枝）少一個(gè)。我們?cè)趺床拍苁棺笥抑匦缕胶?，要么讓左枝條黑色節(jié)點(diǎn)+1，要么讓右枝條黑色節(jié)點(diǎn)-1。后續(xù)步驟全都以delete_son為其父左枝條為例，因?yàn)閷?duì)稱，依舊只需要記一半的規(guī)則。
- 讓delete_son的兄弟bro變成黑色，如果bro是紅色，則bro->黑色，parent->紅色，左旋parent，此時(shí)bro的左枝會(huì)變成新的bro，因?yàn)閎ro是紅色，所以根據(jù)規(guī)則4，左枝必為黑，即新bro變?yōu)楹谏?/li>
- 判斷bro的孩子，
- 如果左黑右黑，將bro->紅色，不會(huì)改變bro后續(xù)孩子的平衡，同時(shí)，bro所在的右枝條的黑色節(jié)點(diǎn)-1，紅黑樹(shù)重新平衡，將父親作為新的delete_son繼續(xù)循環(huán)，直到delete_son為紅色。
- 如果左紅右黑，通過(guò)右旋bro，變成左黑右紅。
- 如果左黑右紅。bro繼承父親的顏色，將bro的父親變黑，右孩子變黑（右枝黑+1），左旋父親（左枝黑+1，右枝黑-1），總的來(lái)說(shuō)delete_son所在的左枝條的黑色節(jié)點(diǎn)+1，紅黑樹(shù)重新平衡，并且直接讓delete_son=root退出循環(huán)。
要點(diǎn)：
- 終止條件：當(dāng)delete_son==root或者delete_son為紅的時(shí)候終止循環(huán)。
//-刪除key
void RBtree::deleteNode(KEY_TYPE key){
//-查找key所在節(jié)點(diǎn)
RBtree_node * key_node = searchNode(key);
//-實(shí)際刪除的節(jié)點(diǎn)
RBtree_node* delete_node;
//-delete_node的孩子
RBtree_node* delete_son;
//-如果同時(shí)有左枝或者右枝條
if(key_node->left != nil&&key_node->right != nil){
delete_node = successor(key_node);
delete_son = delete_node->right;
}//-如果僅有左枝或者右枝條或者左右都沒(méi)有
else{
delete_node = key_node;
if(key_node->left != nil){
delete_son = key_node->left;
}else{
delete_son = key_node->right;
}
}
//-刪除deletenode
delete_son->parent = delete_node->parent;
//-先判斷deletenode是不是根節(jié)點(diǎn)
if(delete_node == root){
root = delete_son;
}
else if(delete_node == delete_node->parent->left){
delete_node->parent->left = delete_son;
}else{
delete_node -> parent -> right = delete_son;
}
//-覆蓋key_node原有數(shù)據(jù)
key_node->key = delete_node -> key;
key_node ->value = delete_node -> value;
//-如果刪除節(jié)點(diǎn)是黑色的，需要修復(fù)delete_son,注意是孩子
if(delete_node->color == black){
fixDelete(delete_son);
}
//-釋放空間
delete delete_node;
//-打印
print();
}
//-修復(fù)刪除
void RBtree::fixDelete(RBtree_node * delete_son){
//-修復(fù)的原因是因?yàn)閐elete_son所在的枝條的黑節(jié)點(diǎn)比另一個(gè)枝條少一個(gè)，所以不平衡，所以需要填上左邊缺失的黑，或者減掉右邊多余的黑
//-當(dāng)delete_son是黑色的一直循環(huán)
while(delete_son!=root&&delete_son->color == black){
//-判斷delete_son所在枝條,如果是左枝
if(delete_son == delete_son->parent->left){
//-如果兄弟是紅色的
RBtree_node * bro = delete_son->parent->right;
if(bro->color == red){
bro->color = black;//-兄弟變黑
delete_son->parent->color = red;//-父親變紅
leftRotate(delete_son->parent);//-左旋父親，兄弟上浮，相當(dāng)于左右都加了一個(gè)黑，不改變平衡狀態(tài)
bro = delete_son->parent->right;//-新的bro是原來(lái)bro的左枝，因?yàn)樵璪ro是紅的，其左右枝都是黑色的，這樣保證新的兄弟是黑色的
}
//-此時(shí)兄弟是黑色的,判斷兄弟的孩子
//-左黑右黑（兄弟的孩子平衡了）
if(bro->left->color == black&&bro->right -> color == black){
bro->color = red;//-相當(dāng)于右邊減去多的一個(gè)黑，達(dá)到平衡
delete_son = delete_son->parent;
}else{
//-如果是左紅右黑,變成左黑右紅
if (bro->right->color == black){
bro -> color = red;
bro->left->color = black;
rightRotate(bro);//-左節(jié)點(diǎn)上浮，相當(dāng)于左右都加了一個(gè)黑，不改變平衡
}
bro->color = bro->parent -> color;
bro->parent -> color = black;
bro->right->color = black;//-給右邊加了一個(gè)黑
leftRotate(delete_son->parent);//-父親下沉，兄弟上浮，左邊加一個(gè)黑，右邊減一個(gè)黑，總體上左邊填上了缺少的黑也達(dá)到了平衡
delete_son = root;
}
}
//-如果是右枝（不用記規(guī)則，把上面的代碼left和right對(duì)調(diào)即可）
else {
RBtree_node * bro = delete_son->parent->left;
if(bro->color == red){
bro->color = black;
delete_son->parent->color = red;
rightRotate(delete_son->parent);
bro = delete_son->parent->left;
}
if(bro->right->color == black&&bro->left -> color == black){
bro->color = red;
delete_son = delete_son->parent;
}else{
if (bro->left->color == black){
bro -> color = red;
bro->right->color = black;
leftRotate(bro);
}
bro->color = bro->parent -> color;
bro->parent -> color = black;
bro->left->color = black;
rightRotate(delete_son->parent);
delete_son = root;
}
}
}
delete_son->color = black;
}
void RBtree::deleteNode(KEY_TYPE key){
//-查找key所在節(jié)點(diǎn)
RBtree_node * key_node = searchNode(key);
//-實(shí)際刪除的節(jié)點(diǎn)
RBtree_node* delete_node;
//-delete_node的孩子
RBtree_node* delete_son;
//-如果同時(shí)有左枝或者右枝條
if(key_node->left != nil&&key_node->right != nil){
delete_node = successor(key_node);
delete_son = delete_node->right;
}//-如果僅有左枝或者右枝條或者左右都沒(méi)有
else{
delete_node = key_node;
if(key_node->left != nil){
delete_son = key_node->left;
}else{
delete_son = key_node->right;
}
}
//-刪除deletenode
delete_son->parent = delete_node->parent;
//-先判斷deletenode是不是根節(jié)點(diǎn)
if(delete_node == root){
root = delete_son;
}
else if(delete_node == delete_node->parent->left){
delete_node->parent->left = delete_son;
}else{
delete_node -> parent -> right = delete_son;
}
//-覆蓋key_node原有數(shù)據(jù)
key_node->key = delete_node -> key;
key_node ->value = delete_node -> value;
//-如果刪除節(jié)點(diǎn)是黑色的，需要修復(fù)delete_son,注意是孩子
if(delete_node->color == black){
fixDelete(delete_son);
}
//-釋放空間
delete delete_node;
//-打印
print();
}
//-修復(fù)刪除
void RBtree::fixDelete(RBtree_node * delete_son){
//-修復(fù)的原因是因?yàn)閐elete_son所在的枝條的黑節(jié)點(diǎn)比另一個(gè)枝條少一個(gè)，所以不平衡，所以需要填上左邊缺失的黑，或者減掉右邊多余的黑
//-當(dāng)delete_son是黑色的一直循環(huán)
while(delete_son!=root&&delete_son->color == black){
//-判斷delete_son所在枝條,如果是左枝
if(delete_son == delete_son->parent->left){
//-如果兄弟是紅色的
RBtree_node * bro = delete_son->parent->right;
if(bro->color == red){
bro->color = black;//-兄弟變黑
delete_son->parent->color = red;//-父親變紅
leftRotate(delete_son->parent);//-左旋父親，兄弟上浮，相當(dāng)于左右都加了一個(gè)黑，不改變平衡狀態(tài)
bro = delete_son->parent->right;//-新的bro是原來(lái)bro的左枝，因?yàn)樵璪ro是紅的，其左右枝都是黑色的，這樣保證新的兄弟是黑色的
}
//-此時(shí)兄弟是黑色的,判斷兄弟的孩子
//-左黑右黑（兄弟的孩子平衡了）
if(bro->left->color == black&&bro->right -> color == black){
bro->color = red;//-相當(dāng)于右邊減去多的一個(gè)黑，達(dá)到平衡
delete_son = delete_son->parent;
}else{
//-如果是左紅右黑,變成左黑右紅
if (bro->right->color == black){
bro -> color = red;
bro->left->color = black;
rightRotate(bro);//-左節(jié)點(diǎn)上浮，相當(dāng)于左右都加了一個(gè)黑，不改變平衡
}
bro->color = bro->parent -> color;
bro->parent -> color = black;
bro->right->color = black;//-給右邊加了一個(gè)黑
leftRotate(delete_son->parent);//-父親下沉，兄弟上浮，左邊加一個(gè)黑，右邊減一個(gè)黑，總體上左邊填上了缺少的黑也達(dá)到了平衡
delete_son = root;
}
}
//-如果是右枝（不用記規(guī)則，把上面的代碼left和right對(duì)調(diào)即可）
else {
RBtree_node * bro = delete_son->parent->left;
if(bro->color == red){
bro->color = black;
delete_son->parent->color = red;
rightRotate(delete_son->parent);
bro = delete_son->parent->left;
}
if(bro->right->color == black&&bro->left -> color == black){
bro->color = red;
delete_son = delete_son->parent;
}else{
if (bro->left->color == black){
bro -> color = red;
bro->right->color = black;
leftRotate(bro);
}
bro->color = bro->parent -> color;
bro->parent -> color = black;
bro->left->color = black;
rightRotate(delete_son->parent);
delete_son = root;
}
}
}
delete_son->color = black;
}
二叉樹(shù)層序遍歷和中序遍歷
每次插入刪除的時(shí)候，使用層序遍歷打印一遍二叉樹(shù)，可以驗(yàn)證一下是否正確。
每個(gè)節(jié)點(diǎn)都有前綴，b代表黑節(jié)點(diǎn)，r代表紅節(jié)點(diǎn)。
//-層序遍歷打印紅黑樹(shù)
void RBtree::print(){
std::deque dqueue;//-使用deque實(shí)現(xiàn)隊(duì)列
dqueue.push_back(root);
while(!dqueue.empty()){
int size = (int)dqueue.size();
for (int i = 0; i < size; ++i) {
RBtree_node* temp = dqueue.front();
dqueue.pop_front();
if(temp->left!=nullptr){
dqueue.push_back(temp -> left);
}
if(temp -> right != nullptr){
dqueue.push_back(temp -> right);
}
std::string color = temp->color?"b: ":"r: ";
std::string keystr = temp==nil?"nil":std::to_string(temp->key);
std::cout< }
std::cout< }
}
//-打印中序遍歷
void RBtree::printMiddle(RBtree_node * node){
if(node == nil){
return;
}
printMiddle(node->left);
std::string color = node->color?"b:":"r:";
std::cout
}<;
<*>
void RBtree::print(){
std::deque dqueue;//-使用deque實(shí)現(xiàn)隊(duì)列
dqueue.push_back(root);
while(!dqueue.empty()){
int size = (int)dqueue.size();
for (int i = 0; i < size; ++i) {
RBtree_node* temp = dqueue.front();
dqueue.pop_front();
if(temp->left!=nullptr){
dqueue.push_back(temp -> left);
}
if(temp -> right != nullptr){
dqueue.push_back(temp -> right);
}
std::string color = temp->color?"b: ":"r: ";
std::string keystr = temp==nil?"nil":std::to_string(temp->key);
std::cout< }
std::cout< }
}
//-打印中序遍歷
void RBtree::printMiddle(RBtree_node * node){
if(node == nil){
return;
}
printMiddle(node->left);
std::string color = node->color?"b:":"r:";
std::cout
}<;
<*>
紅黑樹(shù)測(cè)試代碼
寫(xiě)個(gè)循環(huán)來(lái)插入元素，輸入i插入元素，輸入d刪除元素，輸入q退出程序。
附上一個(gè)在線生成紅黑樹(shù)的連接，可以配合測(cè)試自己寫(xiě)的紅黑樹(shù)的正確性
紅黑樹(shù)動(dòng)畫(huà)在線演示
int main(){
RBtree rb;
std::string select;
KEY_TYPE key;
while(true){
std::cout<<"n輸入操作：i：插入key，d：刪除key q：退出"< std::cin>>select;
if(select == "i"){
std::cout<<"輸入key"< std::cin>>key;
rb.insertNode(key);
}else if(select == "d"){
std::cout<<"輸入key"< std::cin>>key;
rb.deleteNode(key);
}else if(select == "q"){
break;
}else{
std::cout<<"輸入不合法，重新輸入"< }
}
return 0;
};
;
;
;
RBtree rb;
std::string select;
KEY_TYPE key;
while(true){
std::cout<<"n輸入操作：i：插入key，d：刪除key q：退出"< std::cin>>select;
if(select == "i"){
std::cout<<"輸入key"< std::cin>>key;
rb.insertNode(key);
}else if(select == "d"){
std::cout<<"輸入key"< std::cin>>key;
rb.deleteNode(key);
}else if(select == "q"){
break;
}else{
std::cout<<"輸入不合法，重新輸入"< }
}
return 0;
};
;
;
;
完整代碼
#include
#include
#include
#include
//-既然標(biāo)題是c++，那么就寫(xiě)成滿滿的c++風(fēng)格吧
using Color = bool;//-顏色因?yàn)橹挥屑t或者黑，選擇bool類型
using KEY_TYPE = int;//-為了更好理解紅黑樹(shù)，就不寫(xiě)成模板類了，所以首選萬(wàn)年int（笑~）
using VALUE_TYPE = int;//-同理
//-全局靜態(tài)紅黑變量
static const Color red = false;
static const Color black = true;
//-紅黑樹(shù)的節(jié)點(diǎn)特點(diǎn)，有color，有parent
class RBtree_node{
public:
Color color;
RBtree_node * parent;
RBtree_node * left;
RBtree_node * right;
KEY_TYPE key;//-后期如果想解耦合，可以將key和value抽離出去
VALUE_TYPE value;
RBtree_node(Color color_):color(color_),parent(nullptr),left(nullptr),right(nullptr),key(-99999){}
RBtree_node(Color color_, KEY_TYPE key_,RBtree_node * nil):
color(color_),parent(nil),left(nil),right(nil),key(key_){}
};
class RBtree{
private:
//-紅黑樹(shù)數(shù)據(jù)成員：其中nil的意義在于，因?yàn)榧t黑樹(shù)的所有葉子節(jié)點(diǎn)都是黑色的，所以可以將所有臨近末尾的節(jié)點(diǎn)，
//-都連接到這一個(gè)葉子結(jié)點(diǎn)nil上，同理，root的parent也可以連接到nil上，形成一個(gè)dummy空節(jié)點(diǎn)
RBtree_node * root;
RBtree_node * nil;
public :
//-以下實(shí)現(xiàn)了紅黑樹(shù)常用接口：
//-構(gòu)造函數(shù)
RBtree(){
nil = new RBtree_node(black);//-為所有葉子節(jié)點(diǎn)nil初始化，顏色為黑色
root = nil;//-紅黑樹(shù)為空的時(shí)候，讓nil作為root
}
//-左旋
void leftRotate(RBtree_node *left_node);
//- 右旋
void rightRotate(RBtree_node * right_node);
//-插入key
void insertNode(KEY_TYPE key);
//-修復(fù)插入
void fixInsert(RBtree_node * node);
//-查找某個(gè)key的節(jié)點(diǎn)
RBtree_node* searchNode(KEY_TYPE key);
//-查找某個(gè)節(jié)點(diǎn)的中序后繼
RBtree_node* successor(RBtree_node * node);
//-刪除key
void deleteNode(KEY_TYPE key);
//-修復(fù)刪除
void fixDelete(RBtree_node * node);
//-層序遍歷打印紅黑樹(shù)
void print();
//-打印中序遍歷
void printMiddle(RBtree_node * node);
};
//-左旋
void RBtree::leftRotate(RBtree_node *left_node){
RBtree_node * right_node = left_node->right;
//-右節(jié)點(diǎn)的左枝條接在左節(jié)點(diǎn)的右枝條上
left_node->right = right_node->left;
if(right_node->left!=nil){
left_node->right->parent = left_node;
}
//-右節(jié)點(diǎn)接在左節(jié)點(diǎn)的父親上
right_node->parent = left_node->parent;
if(left_node == root){
//-nil不會(huì)指向任何節(jié)點(diǎn)，但是root->parent是nil
root = right_node;
}
else if(left_node == left_node->parent->left){
left_node->parent->left = right_node;
}else{
left_node->parent->right = right_node;
}
//-左節(jié)點(diǎn)接在右節(jié)點(diǎn)的左枝上
left_node->parent = right_node;
right_node->left = left_node;
}
//- 右旋：寫(xiě)完左旋后，把所有l(wèi)eft和right對(duì)調(diào)即可
void RBtree::rightRotate(RBtree_node * right_node){
RBtree_node * left_node = right_node->left;
right_node->left = left_node->right;
if(left_node->right!=nil){
right_node->left->parent = right_node;
}
left_node->parent = right_node->parent;
if(right_node == root){
root = left_node;
}
else if(right_node == right_node->parent->right){
right_node->parent->right = left_node;
}else{
right_node->parent->left = left_node;
}
right_node->parent = left_node;
left_node->right = right_node;
}
//-插入key
void RBtree::insertNode(KEY_TYPE key){
RBtree_node * prev = nil;
RBtree_node * cur = root;
while(cur!=nil){
prev = cur;
if(key>cur->key){
cur = cur->right;
}else if(keykey){
cur = cur->left;
}else{//-該key已經(jīng)存在
return;
}
}
//-創(chuàng)建新節(jié)點(diǎn)
RBtree_node * new_node = new RBtree_node(red,key,nil);
//-如果節(jié)點(diǎn)沒(méi)有元素
new_node->parent = prev;
if(prev == nil){
root = new_node;
}
else if(key key){
prev ->left = new_node;
}else{
prev ->right = new_node;
}
fixInsert(new_node);
print();
}
//-修復(fù)插入
void RBtree::fixInsert(RBtree_node * new_node){
while(new_node -> parent->color == red){//-終止條件要注意
//-如果父親是左枝
if(new_node->parent == new_node -> parent->parent->left){
//-獲得其伯父節(jié)點(diǎn)
RBtree_node * uncle = new_node->parent->parent->right;
if(uncle->color == red){//-如果伯父是紅色，那么將父親和伯父同時(shí)變黑，不會(huì)破壞左右平衡
uncle->color = black;
new_node->parent->color = black;
new_node->parent ->parent->color = red;//-將祖父變紅，才能實(shí)現(xiàn)下一輪回溯修復(fù)
new_node = new_node->parent->parent;
}else{//-如果伯父是黑色
//-判斷new_node是不是右孩子，如果是右孩子轉(zhuǎn)換成左孩子
if(new_node == new_node -> parent->right){
new_node = new_node->parent;
leftRotate(new_node);
}
//-此時(shí)紅色節(jié)點(diǎn)是左孩子
//-如果結(jié)構(gòu)本是平衡狀態(tài)，右邊本該比左邊多一個(gè)黑，但是我們將父親（左)變黑會(huì)破壞平衡，
//-所以需要右旋祖父，把父親上浮，相當(dāng)于在左枝多一個(gè)黑的時(shí)候給右枝也多了黑，這樣左右就能平衡
new_node->parent->color = black;
new_node->parent ->parent->color = red;
rightRotate(new_node->parent->parent);
}
}
//-如果父親是右枝（將上邊代碼的left和right全部對(duì)調(diào)即可，不用記規(guī)則）
else {
RBtree_node * uncle = new_node->parent->parent->left;
if(uncle->color == red){//-如果伯父是紅色
uncle->color = black;
new_node->parent->color = black;
new_node->parent ->parent->color = red;
new_node = new_node->parent->parent;
}else{//-如果伯父是黑色
if(new_node == new_node -> parent->left){
new_node = new_node->parent;
rightRotate(new_node);
}
new_node->parent->color = black;
new_node->parent ->parent->color = red;
leftRotate(new_node->parent->parent);
}
}
}
//-如果new_node回溯到root，此時(shí)root->parent==nil（black）打破了循環(huán)，而此時(shí)root被改變成了黑色，違反了規(guī)則1，
//-所以最后需要強(qiáng)行把root fix成黑色
root->color = black;
}
//-查找某個(gè)key的節(jié)點(diǎn)
RBtree_node* RBtree::searchNode(KEY_TYPE key){
RBtree_node * cur = root;
while(cur!=nil){
if(key>cur -> key){
cur = cur->right;
}else if(key < cur -> key){
cur = cur->left;
}else{
return cur;
}
}
return cur;
}
//-查找某個(gè)節(jié)點(diǎn)的中序后繼
RBtree_node* RBtree::successor(RBtree_node * node){
//-如果節(jié)點(diǎn)有右孩子
if(node->right!=nil){
RBtree_node * res = node -> right;
while(res->left!=nil){
res = res->left;
}
return res;
}else{
while(node!=root&&node!=node->parent->left){
node = node->parent;
}
return node->parent;
}
}
//-刪除key
void RBtree::deleteNode(KEY_TYPE key){
//-查找key所在節(jié)點(diǎn)
RBtree_node * key_node = searchNode(key);
//-實(shí)際刪除的節(jié)點(diǎn)
RBtree_node* delete_node;
//-delete_node的孩子
RBtree_node* delete_son;
//-如果同時(shí)有左枝或者右枝條
if(key_node->left != nil&&key_node->right != nil){
delete_node = successor(key_node);
delete_son = delete_node->right;
}//-如果僅有左枝或者右枝條或者左右都沒(méi)有
else{
delete_node = key_node;
if(key_node->left != nil){
delete_son = key_node->left;
}else{
delete_son = key_node->right;
}
}
//-刪除deletenode
delete_son->parent = delete_node->parent;
//-先判斷deletenode是不是根節(jié)點(diǎn)
if(delete_node == root){
root = delete_son;
}
else if(delete_node == delete_node->parent->left){
delete_node->parent->left = delete_son;
}else{
delete_node -> parent -> right = delete_son;
}
//-覆蓋key_node原有數(shù)據(jù)
key_node->key = delete_node -> key;
key_node ->value = delete_node -> value;
//-如果刪除節(jié)點(diǎn)是黑色的，需要修復(fù)delete_son,注意是孩子
if(delete_node->color == black){
fixDelete(delete_son);
}
//-釋放空間
delete delete_node;
//-打印
print();
}
//-修復(fù)刪除
void RBtree::fixDelete(RBtree_node * delete_son){
//-修復(fù)的原因是因?yàn)閐elete_son所在的枝條的黑節(jié)點(diǎn)比另一個(gè)枝條少一個(gè)，所以不平衡，所以需要填上左邊缺失的黑，或者減掉右邊多余的黑
//-當(dāng)delete_son是黑色的一直循環(huán)
while(delete_son!=root&&delete_son->color == black){
//-判斷delete_son所在枝條,如果是左枝
if(delete_son == delete_son->parent->left){
//-如果兄弟是紅色的
RBtree_node * bro = delete_son->parent->right;
if(bro->color == red){
bro->color = black;//-兄弟變黑
delete_son->parent->color = red;//-父親變紅
leftRotate(delete_son->parent);//-左旋父親，兄弟上浮，相當(dāng)于左右都加了一個(gè)黑，不改變平衡狀態(tài)
bro = delete_son->parent->right;//-新的bro是原來(lái)bro的左枝，因?yàn)樵璪ro是紅的，其左右枝都是黑色的，這樣保證新的兄弟是黑色的
}
//-此時(shí)兄弟是黑色的,判斷兄弟的孩子
//-左黑右黑（兄弟的孩子平衡了）
if(bro->left->color == black&&bro->right -> color == black){
bro->color = red;//-相當(dāng)于右邊減去多的一個(gè)黑，達(dá)到平衡
delete_son = delete_son->parent;
}else{
//-如果是左紅右黑,變成左黑右紅
if (bro->right->color == black){
bro -> color = red;
bro->left->color = black;
rightRotate(bro);//-左節(jié)點(diǎn)上浮，相當(dāng)于左右都加了一個(gè)黑，不改變平衡
}
bro->color = bro->parent -> color;
bro->parent -> color = black;
bro->right->color = black;//-給右邊加了一個(gè)黑
leftRotate(delete_son->parent);//-父親下沉，兄弟上浮，左邊加一個(gè)黑，右邊減一個(gè)黑，總體上左邊填上了缺少的黑也達(dá)到了平衡
delete_son = root;
}
}
//-如果是右枝（不用記規(guī)則，把上面的代碼left和right對(duì)調(diào)即可）
else {
RBtree_node * bro = delete_son->parent->left;
if(bro->color == red){
bro->color = black;
delete_son->parent->color = red;
rightRotate(delete_son->parent);
bro = delete_son->parent->left;
}
if(bro->right->color == black&&bro->left -> color == black){
bro->color = red;
delete_son = delete_son->parent;
}else{
if (bro->left->color == black){
bro -> color = red;
bro->right->color = black;
leftRotate(bro);
}
bro->color = bro->parent -> color;
bro->parent -> color = black;
bro->left->color = black;
rightRotate(delete_son->parent);
delete_son = root;
}
}
}
delete_son->color = black;
}
//-層序遍歷打印紅黑樹(shù)
void RBtree::print(){
std::deque dqueue;//-使用deque實(shí)現(xiàn)隊(duì)列
dqueue.push_back(root);
while(!dqueue.empty()){
int size = (int)dqueue.size();
for (int i = 0; i < size; ++i) {
RBtree_node* temp = dqueue.front();
dqueue.pop_front();
if(temp->left!=nullptr){
dqueue.push_back(temp -> left);
}
if(temp -> right != nullptr){
dqueue.push_back(temp -> right);
}
std::string color = temp->color?"b: ":"r: ";
std::string keystr = temp==nil?"nil":std::to_string(temp->key);
std::cout< }
std::cout< }
}
//-打印中序遍歷
void RBtree::printMiddle(RBtree_node * node){
if(node == nil){
return;
}
printMiddle(node->left);
std::string color = node->color?"b:":"r:";
std::cout
}
int main(){
RBtree rb;
std::string select;
KEY_TYPE key;
while(true){
std::cout<<"n輸入操作：i：插入key，d：刪除key q：退出"< std::cin>>select;
if(select == "i"){
std::cout<<"輸入key"< std::cin>>key;
rb.insertNode(key);
}else if(select == "d"){
std::cout<<"輸入key"< std::cin>>key;
rb.deleteNode(key);
}else if(select == "q"){
break;
}else{
std::cout<<"輸入不合法，重新輸入"< }
}
return 0;
};
;
;
;
<;
<*>
#include
#include
#include
//-既然標(biāo)題是c++，那么就寫(xiě)成滿滿的c++風(fēng)格吧
using Color = bool;//-顏色因?yàn)橹挥屑t或者黑，選擇bool類型
using KEY_TYPE = int;//-為了更好理解紅黑樹(shù)，就不寫(xiě)成模板類了，所以首選萬(wàn)年int（笑~）
using VALUE_TYPE = int;//-同理
//-全局靜態(tài)紅黑變量
static const Color red = false;
static const Color black = true;
//-紅黑樹(shù)的節(jié)點(diǎn)特點(diǎn)，有color，有parent
class RBtree_node{
public:
Color color;
RBtree_node * parent;
RBtree_node * left;
RBtree_node * right;
KEY_TYPE key;//-后期如果想解耦合，可以將key和value抽離出去
VALUE_TYPE value;
RBtree_node(Color color_):color(color_),parent(nullptr),left(nullptr),right(nullptr),key(-99999){}
RBtree_node(Color color_, KEY_TYPE key_,RBtree_node * nil):
color(color_),parent(nil),left(nil),right(nil),key(key_){}
};
class RBtree{
private:
//-紅黑樹(shù)數(shù)據(jù)成員：其中nil的意義在于，因?yàn)榧t黑樹(shù)的所有葉子節(jié)點(diǎn)都是黑色的，所以可以將所有臨近末尾的節(jié)點(diǎn)，
//-都連接到這一個(gè)葉子結(jié)點(diǎn)nil上，同理，root的parent也可以連接到nil上，形成一個(gè)dummy空節(jié)點(diǎn)
RBtree_node * root;
RBtree_node * nil;
public :
//-以下實(shí)現(xiàn)了紅黑樹(shù)常用接口：
//-構(gòu)造函數(shù)
RBtree(){
nil = new RBtree_node(black);//-為所有葉子節(jié)點(diǎn)nil初始化，顏色為黑色
root = nil;//-紅黑樹(shù)為空的時(shí)候，讓nil作為root
}
//-左旋
void leftRotate(RBtree_node *left_node);
//- 右旋
void rightRotate(RBtree_node * right_node);
//-插入key
void insertNode(KEY_TYPE key);
//-修復(fù)插入
void fixInsert(RBtree_node * node);
//-查找某個(gè)key的節(jié)點(diǎn)
RBtree_node* searchNode(KEY_TYPE key);
//-查找某個(gè)節(jié)點(diǎn)的中序后繼
RBtree_node* successor(RBtree_node * node);
//-刪除key
void deleteNode(KEY_TYPE key);
//-修復(fù)刪除
void fixDelete(RBtree_node * node);
//-層序遍歷打印紅黑樹(shù)
void print();
//-打印中序遍歷
void printMiddle(RBtree_node * node);
};
//-左旋
void RBtree::leftRotate(RBtree_node *left_node){
RBtree_node * right_node = left_node->right;
//-右節(jié)點(diǎn)的左枝條接在左節(jié)點(diǎn)的右枝條上
left_node->right = right_node->left;
if(right_node->left!=nil){
left_node->right->parent = left_node;
}
//-右節(jié)點(diǎn)接在左節(jié)點(diǎn)的父親上
right_node->parent = left_node->parent;
if(left_node == root){
//-nil不會(huì)指向任何節(jié)點(diǎn)，但是root->parent是nil
root = right_node;
}
else if(left_node == left_node->parent->left){
left_node->parent->left = right_node;
}else{
left_node->parent->right = right_node;
}
//-左節(jié)點(diǎn)接在右節(jié)點(diǎn)的左枝上
left_node->parent = right_node;
right_node->left = left_node;
}
//- 右旋：寫(xiě)完左旋后，把所有l(wèi)eft和right對(duì)調(diào)即可
void RBtree::rightRotate(RBtree_node * right_node){
RBtree_node * left_node = right_node->left;
right_node->left = left_node->right;
if(left_node->right!=nil){
right_node->left->parent = right_node;
}
left_node->parent = right_node->parent;
if(right_node == root){
root = left_node;
}
else if(right_node == right_node->parent->right){
right_node->parent->right = left_node;
}else{
right_node->parent->left = left_node;
}
right_node->parent = left_node;
left_node->right = right_node;
}
//-插入key
void RBtree::insertNode(KEY_TYPE key){
RBtree_node * prev = nil;
RBtree_node * cur = root;
while(cur!=nil){
prev = cur;
if(key>cur->key){
cur = cur->right;
}else if(keykey){
cur = cur->left;
}else{//-該key已經(jīng)存在
return;
}
}
//-創(chuàng)建新節(jié)點(diǎn)
RBtree_node * new_node = new RBtree_node(red,key,nil);
//-如果節(jié)點(diǎn)沒(méi)有元素
new_node->parent = prev;
if(prev == nil){
root = new_node;
}
else if(key key){
prev ->left = new_node;
}else{
prev ->right = new_node;
}
fixInsert(new_node);
print();
}
//-修復(fù)插入
void RBtree::fixInsert(RBtree_node * new_node){
while(new_node -> parent->color == red){//-終止條件要注意
//-如果父親是左枝
if(new_node->parent == new_node -> parent->parent->left){
//-獲得其伯父節(jié)點(diǎn)
RBtree_node * uncle = new_node->parent->parent->right;
if(uncle->color == red){//-如果伯父是紅色，那么將父親和伯父同時(shí)變黑，不會(huì)破壞左右平衡
uncle->color = black;
new_node->parent->color = black;
new_node->parent ->parent->color = red;//-將祖父變紅，才能實(shí)現(xiàn)下一輪回溯修復(fù)
new_node = new_node->parent->parent;
}else{//-如果伯父是黑色
//-判斷new_node是不是右孩子，如果是右孩子轉(zhuǎn)換成左孩子
if(new_node == new_node -> parent->right){
new_node = new_node->parent;
leftRotate(new_node);
}
//-此時(shí)紅色節(jié)點(diǎn)是左孩子
//-如果結(jié)構(gòu)本是平衡狀態(tài)，右邊本該比左邊多一個(gè)黑，但是我們將父親（左)變黑會(huì)破壞平衡，
//-所以需要右旋祖父，把父親上浮，相當(dāng)于在左枝多一個(gè)黑的時(shí)候給右枝也多了黑，這樣左右就能平衡
new_node->parent->color = black;
new_node->parent ->parent->color = red;
rightRotate(new_node->parent->parent);
}
}
//-如果父親是右枝（將上邊代碼的left和right全部對(duì)調(diào)即可，不用記規(guī)則）
else {
RBtree_node * uncle = new_node->parent->parent->left;
if(uncle->color == red){//-如果伯父是紅色
uncle->color = black;
new_node->parent->color = black;
new_node->parent ->parent->color = red;
new_node = new_node->parent->parent;
}else{//-如果伯父是黑色
if(new_node == new_node -> parent->left){
new_node = new_node->parent;
rightRotate(new_node);
}
new_node->parent->color = black;
new_node->parent ->parent->color = red;
leftRotate(new_node->parent->parent);
}
}
}
//-如果new_node回溯到root，此時(shí)root->parent==nil（black）打破了循環(huán)，而此時(shí)root被改變成了黑色，違反了規(guī)則1，
//-所以最后需要強(qiáng)行把root fix成黑色
root->color = black;
}
//-查找某個(gè)key的節(jié)點(diǎn)
RBtree_node* RBtree::searchNode(KEY_TYPE key){
RBtree_node * cur = root;
while(cur!=nil){
if(key>cur -> key){
cur = cur->right;
}else if(key < cur -> key){
cur = cur->left;
}else{
return cur;
}
}
return cur;
}
//-查找某個(gè)節(jié)點(diǎn)的中序后繼
RBtree_node* RBtree::successor(RBtree_node * node){
//-如果節(jié)點(diǎn)有右孩子
if(node->right!=nil){
RBtree_node * res = node -> right;
while(res->left!=nil){
res = res->left;
}
return res;
}else{
while(node!=root&&node!=node->parent->left){
node = node->parent;
}
return node->parent;
}
}
//-刪除key
void RBtree::deleteNode(KEY_TYPE key){
//-查找key所在節(jié)點(diǎn)
RBtree_node * key_node = searchNode(key);
//-實(shí)際刪除的節(jié)點(diǎn)
RBtree_node* delete_node;
//-delete_node的孩子
RBtree_node* delete_son;
//-如果同時(shí)有左枝或者右枝條
if(key_node->left != nil&&key_node->right != nil){
delete_node = successor(key_node);
delete_son = delete_node->right;
}//-如果僅有左枝或者右枝條或者左右都沒(méi)有
else{
delete_node = key_node;
if(key_node->left != nil){
delete_son = key_node->left;
}else{
delete_son = key_node->right;
}
}
//-刪除deletenode
delete_son->parent = delete_node->parent;
//-先判斷deletenode是不是根節(jié)點(diǎn)
if(delete_node == root){
root = delete_son;
}
else if(delete_node == delete_node->parent->left){
delete_node->parent->left = delete_son;
}else{
delete_node -> parent -> right = delete_son;
}
//-覆蓋key_node原有數(shù)據(jù)
key_node->key = delete_node -> key;
key_node ->value = delete_node -> value;
//-如果刪除節(jié)點(diǎn)是黑色的，需要修復(fù)delete_son,注意是孩子
if(delete_node->color == black){
fixDelete(delete_son);
}
//-釋放空間
delete delete_node;
//-打印
print();
}
//-修復(fù)刪除
void RBtree::fixDelete(RBtree_node * delete_son){
//-修復(fù)的原因是因?yàn)閐elete_son所在的枝條的黑節(jié)點(diǎn)比另一個(gè)枝條少一個(gè)，所以不平衡，所以需要填上左邊缺失的黑，或者減掉右邊多余的黑
//-當(dāng)delete_son是黑色的一直循環(huán)
while(delete_son!=root&&delete_son->color == black){
//-判斷delete_son所在枝條,如果是左枝
if(delete_son == delete_son->parent->left){
//-如果兄弟是紅色的
RBtree_node * bro = delete_son->parent->right;
if(bro->color == red){
bro->color = black;//-兄弟變黑
delete_son->parent->color = red;//-父親變紅
leftRotate(delete_son->parent);//-左旋父親，兄弟上浮，相當(dāng)于左右都加了一個(gè)黑，不改變平衡狀態(tài)
bro = delete_son->parent->right;//-新的bro是原來(lái)bro的左枝，因?yàn)樵璪ro是紅的，其左右枝都是黑色的，這樣保證新的兄弟是黑色的
}
//-此時(shí)兄弟是黑色的,判斷兄弟的孩子
//-左黑右黑（兄弟的孩子平衡了）
if(bro->left->color == black&&bro->right -> color == black){
bro->color = red;//-相當(dāng)于右邊減去多的一個(gè)黑，達(dá)到平衡
delete_son = delete_son->parent;
}else{
//-如果是左紅右黑,變成左黑右紅
if (bro->right->color == black){
bro -> color = red;
bro->left->color = black;
rightRotate(bro);//-左節(jié)點(diǎn)上浮，相當(dāng)于左右都加了一個(gè)黑，不改變平衡
}
bro->color = bro->parent -> color;
bro->parent -> color = black;
bro->right->color = black;//-給右邊加了一個(gè)黑
leftRotate(delete_son->parent);//-父親下沉，兄弟上浮，左邊加一個(gè)黑，右邊減一個(gè)黑，總體上左邊填上了缺少的黑也達(dá)到了平衡
delete_son = root;
}
}
//-如果是右枝（不用記規(guī)則，把上面的代碼left和right對(duì)調(diào)即可）
else {
RBtree_node * bro = delete_son->parent->left;
if(bro->color == red){
bro->color = black;
delete_son->parent->color = red;
rightRotate(delete_son->parent);
bro = delete_son->parent->left;
}
if(bro->right->color == black&&bro->left -> color == black){
bro->color = red;
delete_son = delete_son->parent;
}else{
if (bro->left->color == black){
bro -> color = red;
bro->right->color = black;
leftRotate(bro);
}
bro->color = bro->parent -> color;
bro->parent -> color = black;
bro->left->color = black;
rightRotate(delete_son->parent);
delete_son = root;
}
}
}
delete_son->color = black;
}
//-層序遍歷打印紅黑樹(shù)
void RBtree::print(){
std::deque dqueue;//-使用deque實(shí)現(xiàn)隊(duì)列
dqueue.push_back(root);
while(!dqueue.empty()){
int size = (int)dqueue.size();
for (int i = 0; i < size; ++i) {
RBtree_node* temp = dqueue.front();
dqueue.pop_front();
if(temp->left!=nullptr){
dqueue.push_back(temp -> left);
}
if(temp -> right != nullptr){
dqueue.push_back(temp -> right);
}
std::string color = temp->color?"b: ":"r: ";
std::string keystr = temp==nil?"nil":std::to_string(temp->key);
std::cout< }
std::cout< }
}
//-打印中序遍歷
void RBtree::printMiddle(RBtree_node * node){
if(node == nil){
return;
}
printMiddle(node->left);
std::string color = node->color?"b:":"r:";
std::cout
}
int main(){
RBtree rb;
std::string select;
KEY_TYPE key;
while(true){
std::cout<<"n輸入操作：i：插入key，d：刪除key q：退出"< std::cin>>select;
if(select == "i"){
std::cout<<"輸入key"< std::cin>>key;
rb.insertNode(key);
}else if(select == "d"){
std::cout<<"輸入key"< std::cin>>key;
rb.deleteNode(key);
}else if(select == "q"){
break;
}else{
std::cout<<"輸入不合法，重新輸入"< }
}
return 0;
};
;
;
;
<;
<*>
聲明：本文內(nèi)容及配圖由入駐作者撰寫(xiě)或者入駐合作網(wǎng)站授權(quán)轉(zhuǎn)載。文章觀點(diǎn)僅代表作者本人，不代表電子發(fā)燒友網(wǎng)立場(chǎng)。文章及其配圖僅供工程師學(xué)習(xí)之用，如有內(nèi)容侵權(quán)或者其他違規(guī)問(wèn)題，請(qǐng)聯(lián)系本站處理。
舉報(bào)投訴
-
內(nèi)存
+關(guān)注
關(guān)注
8文章
3047瀏覽量
74207 -
nginx
+關(guān)注
關(guān)注
0文章
152瀏覽量
12202
發(fā)布評(píng)論請(qǐng)先 登錄
相關(guān)推薦
什么是“紅黑樹(shù)”看了就知道
今天我們要說(shuō)的紅黑樹(shù)就是就是一棵非嚴(yán)格均衡的二叉樹(shù)，均衡二叉樹(shù)又是在二叉搜索樹(shù)的基礎(chǔ)上增加了自動(dòng)
發(fā)表于 10-27 17:00
一文詳解紅黑樹(shù)
紅黑樹(shù)是一種自平衡的二叉查找樹(shù)，是一種高效的查找樹(shù)。它是由 Rudolf Bayer 于1972年發(fā)明，在當(dāng)時(shí)被稱為對(duì)稱二叉 B
Linux通用塊層之deadline簡(jiǎn)介及通用塊層調(diào)度器框架
接口很簡(jiǎn)單，首先判斷request的IO方向，根據(jù)IO方向通過(guò)deadline_add_rq_rb將request添加到讀/寫(xiě)紅黑樹(shù)中，request在紅
紅魔Mars和黑鯊Helo哪個(gè)好
11月28日，努比亞正式發(fā)布了新一代的游戲手機(jī)——紅魔Mars電競(jìng)手機(jī)，和紅魔游戲手機(jī)1代相比，紅魔Mars電競(jìng)手機(jī)在性能、散熱、設(shè)計(jì)上全面升級(jí)，這也讓它與黑鯊游戲手機(jī)Helo之間的競(jìng)
詳解電源二叉樹(shù)到底是什么
作為數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)，樹(shù)分很多種，像 AVL 樹(shù)、紅黑樹(shù)、二叉搜索樹(shù)....今天我想分享的是關(guān)于二
紅魔3和黑鯊2買哪個(gè)好
買黑鯊2還是紅魔3？作為兩款同樣采用高通驍龍855移動(dòng)平臺(tái)的游戲手機(jī)，黑鯊2和紅魔3不免會(huì)被消費(fèi)者放在一起進(jìn)行比較。那么，黑鯊2和
黑鯊2和紅魔3哪個(gè)好
紅魔3和黑鯊2哪個(gè)好？和黑鯊科技今年上半年力推的“黑鯊2”一樣，紅魔3也搭載了高通驍龍855移動(dòng)平臺(tái)。那么，
紅魔Mars和黑鯊Helo哪個(gè)最好
在18年的圈里，游戲手機(jī)燃起了很大的熱點(diǎn)，尤其是黑鯊和紅魔更是打動(dòng)很多手游愛(ài)好者，進(jìn)化后的紅魔Mars和黑鯊Helo更是棋逢對(duì)手，如今令人期待的紅
紅黑樹(shù)（Red Black Tree）是一種自平衡的二叉搜索樹(shù)
平衡（Balance）：就是當(dāng)結(jié)點(diǎn)數(shù)量固定時(shí)，左右子樹(shù)的高度越接近，這棵二叉樹(shù)越平衡（高度越低）。而最理想的平衡就是完全二叉樹(shù)/滿二叉樹(shù)，高度最小的二叉樹(shù)。
如何使用 go 實(shí)現(xiàn)紅黑樹(shù)
二叉查找樹(shù)也叫二叉搜索樹(shù)，也叫二叉排序樹(shù)，它具有以下特點(diǎn)：1. 如果左子樹(shù)不為空，則左子樹(shù)上的結(jié)點(diǎn)的值都小于根節(jié)點(diǎn)；2. 如果右子樹(shù)不為空，則右子樹(shù)上的結(jié)點(diǎn)的值都大于根節(jié)點(diǎn)；3. 子樹(shù)
HashMap奪命14問(wèn)，你能堅(jiān)持到第幾問(wèn)？
在JDK1.8中，有“數(shù)組+鏈表+紅黑樹(shù)”組成。當(dāng)鏈表過(guò)長(zhǎng)，則會(huì)嚴(yán)重影響HashMap的性能，紅黑樹(shù)
紅黑樹(shù)是如何模擬2-3 B樹(shù)的操作邏輯的
大家都聽(tīng)說(shuō)過(guò)紅黑樹(shù)，也都知道紅黑樹(shù)很厲害，是計(jì)算機(jī)里面評(píng)價(jià)非常高的數(shù)據(jù)結(jié)構(gòu)。但是每當(dāng)想學(xué)習(xí)
PRBTEK萬(wàn)用筆紅黑表筆線PK1505的使用方法
萬(wàn)用筆紅黑表筆線，是一種功能強(qiáng)大并常被使用的電子測(cè)試工具，通常由精細(xì)的尖頭、手柄和紅黑表筆各一組組成。紅
為什么MySQL索引要用B+tree？
紅黑樹(shù)是一種特化的 AVL樹(shù)（平衡二叉樹(shù)），都是在進(jìn)行插入和刪除操作時(shí)通過(guò)特定操作保持二叉查找樹(shù)
發(fā)表于 10-30 14:41
?264次閱讀
工商網(wǎng)監(jiān)
評(píng)論