紅黑樹的簡單介紹
紅黑樹(Red-Black Tree，簡稱R-B Tree)蛉签，它一種特殊的二叉查找樹胡陪。這意味著它滿足二叉查找樹的特征，但是也有許多自己的特性碍舍。
紅黑樹的特性：
- 每個節(jié)點的顏色非黑及紅柠座。
- 根節(jié)點是黑色。
- 每個葉子節(jié)點是黑色片橡。 [注：此葉子節(jié)點妈经，是指為空的葉子節(jié)點！]
- 如果一個節(jié)點是紅色的，則它的子節(jié)點必須是黑色的吹泡。
- 從一個節(jié)點到該節(jié)點的子孫節(jié)點的所有路徑上包含相同數(shù)目的黑色節(jié)點骤星。
這里推薦一個數(shù)據(jù)結(jié)構(gòu)可視化的網(wǎng)站，可以查看多種數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)可視化
實現(xiàn)
結(jié)點和樹的定義
enum RBTColor{Red,Black};
template <typename keytype>
class RBTNode{
public:
RBTColor color;
keytype key;
RBTNode *left;
RBTNode *right;
RBTNode *parent;
RBTNode(keytype k,RBTColor c):key(k),color(c),left(nullptr),right(nullptr),parent(nullptr){}
};
template <typename keytype>
class RBTree{
typedef RBTNode<keytype> Node;
private:
Node *RBTRoot;
void __insert(Node *&root,const keytype key); //插入內(nèi)部接口
void in_correct(Node *&root,Node *node); //插入修正接口
void left_rotate(Node *&root,Node *x); //左旋
void right_rotate(Node *&root,Node *y); //右旋
void __traversal(Node *&root); //遍歷(中序)內(nèi)部接口
void __remove(Node *&root,Node *node); //刪除內(nèi)部接口
void out_correct(Node *&root,Node *node); //刪除修正接口
Node *__search(Node *&root,const keytype key); //查找內(nèi)部接口
Node *find_successor_node(Node *node); //尋找后繼結(jié)點
void deleteTree(Node *&root); //刪除樹
public:
RBTree():RBTRoot(nullptr){};
~RBTree();
bool search(const keytype key); //查找外部接口
void insert(const keytype key); //插入外部接口
void remove(const keytype key); //刪除外部接口
void traversal(); //遍歷(中序)外部接口
};
左旋和右旋
詳細的注釋和代碼：
/*
* 左旋示意圖(對節(jié)點x進行左旋)：
* px px
* / /
* x y
* / \ ---(左旋)---> / \
* lx y x ry
* / \ / \
* ly ry lx ly
*
*/
//左旋
template <typename keytype>
void RBTree<keytype>::left_rotate(Node *&root,Node *x){
Node *y = x->right; //設x的右孩子為y
x->right = y->left; //將y的左孩子設為x的右孩子
if(y->left != nullptr) y->left->parent = x; //將y左孩子的父親設為x
y->parent = x->parent; //將y的父親設為x的父親
//情況1：x的父親為空結(jié)點
if(x->parent == nullptr) root = y; //將y設為根結(jié)點
else{
//情況2：x是其父親的左孩子
if(x->parent->left == x) x->parent->left = y; //將y設為x父結(jié)點的左孩子
//情況3：x是其父親的右孩子
else x->parent->right = y; //將y設為x父結(jié)點的右孩子
}
y->left = x; //將x設為y的左孩子
x->parent = y; //將y設為x的父結(jié)點
}
//右旋與左旋對稱
//右旋
template <typename keytype>
void RBTree<keytype>::right_rotate(Node *&root,Node *y){
Node *x = y->left; //設y的左孩子為x
y->left = x->right; //將x的左孩子設為y的右孩子
if(x->right != nullptr) x->right->parent = y; //將x右孩子的父親設為y
x->parent = y->parent; //將x的父親設為y的父親
//情況1：y的父親為空結(jié)點
if(y->parent == nullptr) root = x; //將x設為根結(jié)點
else{
//情況2：y是其父親的右孩子
if(y->parent->right == y) y->parent->right = x; //將x設為y父結(jié)點的右孩子
//情況3：y是其父親的左孩子
else y->parent->left = x; //將x設為y父結(jié)點的作孩子
}
x->right = y; //將y設為x的右孩子
y->parent = x; //將x設為y的父結(jié)點
}
插入
- 將紅黑樹當作二叉查找樹爆哑，插入結(jié)點
- 將結(jié)點著色為紅色
- 通過著色和旋轉(zhuǎn)操作洞难，使其重新成為一個紅黑樹
//插入
template <typename keytype>
void RBTree<keytype>::__insert(Node *&root,const keytype key){
Node *node = new Node(key,Black); //新建結(jié)點
//利用指針，非遞歸插入
Node *p = nullptr;
Node *q = root;
while (q != nullptr){
p = q;
if(key < q->key) q = q->left;
else q = q->right;
}
node->parent = p;
if(p != nullptr){
if(key < p->key) p->left = node;
else p->right = node;
}else root = node;
node->color = Red;
in_correct(root,node); //修正紅黑樹
}
這里將第三步細化為修正操作揭朝，如下
插入修正
根據(jù)插入結(jié)點的情況队贱，分為三種情況處理
- 插入的結(jié)點是根結(jié)點：將此結(jié)點著色為黑色
- 插入結(jié)點的父結(jié)點是黑色的：不做操作
- 插入結(jié)點的父結(jié)點是紅色的：
針對情況3，進一步細分為三種情況
(1) 插入結(jié)點的父結(jié)點是紅色的潭袱，且叔叔結(jié)點(即當前結(jié)點的祖父結(jié)點的另一個子結(jié)點)也是紅色
=>將父結(jié)點著色為黑色
=>將叔叔結(jié)點著色為黑色
=>將祖父結(jié)點著色為紅色
=>將祖父結(jié)點設為"當前結(jié)點"柱嫌，對"當前結(jié)點"繼續(xù)進行以上的操作
(2) 當前節(jié)點的父結(jié)點是紅色，叔叔節(jié)點是黑色屯换，且當前節(jié)點是其父節(jié)點的右孩子
=>將父結(jié)點設為”當前節(jié)點“
=>將”當前節(jié)點“進行左旋
(3) 當前節(jié)點的父結(jié)點是紅色编丘，叔叔節(jié)點是黑色，且當前節(jié)點是其父節(jié)點的左孩子
=>將父結(jié)點著色為黑色
=>將祖父結(jié)點著色為紅色
=>將祖父結(jié)點進行右旋
注：以上的三種情況趟径，針對當前節(jié)點的父結(jié)點是其祖父結(jié)點的左孩子瘪吏，則叔叔結(jié)點就是當前結(jié)點祖父結(jié)點的右孩子。若當前節(jié)點的父結(jié)點是其祖父結(jié)點的右孩子蜗巧，則上面操作中的"right"和"left"對調(diào)，依次執(zhí)行蕾盯。
插入修正代碼：
//插入修正
template <typename keytype>
void RBTree<keytype>::in_correct(Node *&root,Node *node){
Node *gparent = nullptr;
while(node->parent != nullptr && node->parent->color == Red){
gparent = node->parent->parent;
if(node->parent == gparent->left){
Node *uncle = gparent->right;
if(uncle->color == Red){
node->parent->color = Black;
uncle->color = Black;
gparent->color = Red;
node = gparent;
}else{
if(node->parent->left == node){
node->parent->color = Black;
gparent->color = Red;
right_rotate(root,gparent);
}else{
node = node->parent;
left_rotate(root,node);
}
}
}else{
Node *uncle = gparent->left;
if(uncle->color == Red){
node->parent->color = Black;
uncle->color = Black;
gparent->color = Red;
node = gparent;
}else{
if(node->parent->right == node){
node->parent->color = Black;
gparent->color = Red;
right_rotate(root,gparent);
}else{
node = node->parent;
left_rotate(root,node);
}
}
}
}
root->color = Black;
}
遍歷(中序)
//遍歷(中序)內(nèi)部接口
template <typename keytype>
void RBTree<keytype>::__traversal(Node *&root){
if(root == nullptr) return;
__traversal(root->left);
cout << root->key << " ";
__traversal(root->right);
}
//遍歷(中序)外部接口
template <typename keytype>
void RBTree<keytype>::traversal(){
__traversal(RBTRoot);
}
測試
int main(){
RBTree<int> tree;
tree.insert(20);
tree.insert(10);
tree.insert(50);
tree.insert(15);
tree.insert(40);
tree.traversal();
return 0;
}
測試結(jié)果
