溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
1、紅黑樹
(1)、概念
i>每個結點不是紅的就是黑的；
ii>根結點為黑的；
iii>紅結點的孩子必為黑結點；
iv>(除了根結點)任一結點不管通過什么路徑，到達葉子節點的黑結點數目一定相同；
總結概括：一頭一腳黑，黑同紅不連：根為黑，到腳(葉子節點)的黑結點相同，紅結點不相連；
2、遞歸--->一般先寫if結束語句
化非遞歸------>用while()循環和棧;
enum{RED, BLACK}; 這個枚舉是有值得，分別為0、1；
3、紅黑樹與AVL樹
AVL樹-------->由高度限定平衡，是嚴格意義上的平衡，絕對平衡；
RBTree------->由紅黑顏色限定平衡，不是太嚴格；
4、紅黑樹的插入
全部代碼用C實現：
(1)、紅黑樹是二叉搜索樹，按二叉搜索樹的大小比較進行插入；
(2)、只能插入紅色結點(黑色的話不滿足黑同)，紅色若相連，通過旋轉解決！！！
結構體控制頭：
typedef struct Node{ //紅黑樹結點類型
Color color; //紅或黑色
Type data; //存儲的數據
struct Node *leftChild, *rightChild, *parent; //為了方便操作，左右孩子和父結點指針
}Node;
typedef struct RBTree{ //紅黑樹類型
Node *root; //根結點
Node *NIL; //指向一個空結點，構造了root有父結點;
}RBTree;我的想法是：用一個指向樹類型的指針，申請一個樹類型空間，在利用樹類型空間里面的root構造一棵樹；
模型示意圖如下：
在產生的結點中，每個結點的左右開始都賦值為NIL；指向空結點，使root的父為空，便于操作；
只能開始插入時為紅結點，最終插入完成，經過旋轉可為黑色;
對于要旋轉的話，有如下2大種情形：
(1)、錯誤的方式
直接將根結點與左右孩子交換顏色，但是就不滿足根是黑色了;
(2)、正確旋轉的兩種方式
i>: 先做一次右單旋轉，在交換1結點和2結點顏色，如下圖：
ii>:先做一次先左后右的雙旋轉，在交換1結點和4結點的顏色，如下圖：
先左后右的旋轉在這里可以通過：先左旋在右旋實現；實際上只寫左和右旋函數就夠了;
以上的2個圖在左邊的，實際上在右邊是為鏡像，一個道理；
左旋代碼實現：
void leftRotate(RBTree *t, Node *p){
Node *s = p->rightChild;
p->rightChild = s->leftChild;
if(s->leftChild != t->NIL){
s->leftChild->parent = p;
}
s->parent = p->parent;
if(p->parent == t->NIL){
t->root = s;
}else if(p == p->parent->leftChild){
p->parent->leftChild = s;
}else{
p->parent->rightChild = s;
}
s->leftChild = p;
p->parent = s;
}右旋代碼實現：
void rightRotate(RBTree *t, Node *p){
Node *s = p->leftChild;
p->leftChild = s->rightChild;
if(s->rightChild != t->NIL){
s->rightChild->parent = p;
}
s->parent = p->parent;
if(p->parent == t->NIL){
t->root = s;
}else if(p == p->parent->leftChild){
p->parent->leftChild = s;
}else{
p->parent->rightChild = s;
}
s->rightChild = p;
p->parent = s;
}5、插入完整代碼、測試代碼、測試結果
(1)、插入代碼：
#ifndef _RBTREE_H_
#define _RBTREE_H_
#include<malloc.h>
typedef enum{RED, BLACK} Color;
typedef struct Node{
Color color;
Type data;
struct Node *leftChild, *rightChild, *parent;
}Node;
typedef struct RBTree{
Node *root;
Node *NIL;
}RBTree;
Node *createNode(); //創建一個結點空間
void initRBTree(RBTree **t); //初始化紅黑樹
void leftRotate(RBTree *t, Node *p); //坐旋轉函數
void rightRotate(RBTree *t, Node *p); //右旋轉函數
void insertFixup(RBTree *t, Node *x); //插入的調整函數
bool insert(RBTree *t, Type x); //插入函數
void showRBTree(RBTree rb); //顯示函數
void show(RBTree rb, Node *t); //真正的顯示函數
void show(RBTree rb, Node *t){
if(t != rb.NIL){
show(rb, t->leftChild);
printf("%d : %d\n", t->data, t->color);
show(rb, t->rightChild);
}
}
void showRBTree(RBTree rb){
show(rb, rb.root);
}
bool insert(RBTree *t, Type x){
Node *s = t->root;
Node *p = t->NIL;
while(s != t->NIL){ //找插入位置
p = s;
if(p->data == x){
return false;
}else if(x < p->data){
s = s->leftChild;
}else{
s = s->rightChild;
}
}
Node *q = createNode();
q->data = x;
q->parent = p;
if(p == t->NIL){
t->root = q;
}else if(x < p->data){
p->leftChild = q;
}else{
p->rightChild = q;
}
q->leftChild = t->NIL; //都指向空結點
q->rightChild = t->NIL;
q->color = RED; //插入結點顏色為紅
insertFixup(t, q); //調用一個調整函數
return true;
}
void insertFixup(RBTree *t, Node *x){
Node *s;
while(x->parent->color == RED){
if(x->parent == x->parent->parent->leftChild){ //leftChild
s = x->parent->parent->rightChild;
if(s->color == RED){
x->parent->color = BLACK;
s->color = BLACK;
x->parent->parent->color = RED;
x = x->parent->parent;
continue;
}else if(x == x->parent->rightChild){
x = x->parent;
leftRotate(t, x);
}
x->parent->color = BLACK; //交換顏色
x->parent->parent->color = RED;
rightRotate(t, x->parent->parent);
}else{ //rightChild
s = x->parent->parent->leftChild;
if(s->color == RED){
x->parent->color = BLACK;
s->color = BLACK;
x->parent->parent->color = RED;
x = x->parent->parent;
continue;
}else if(x == x->parent->leftChild){
x = x->parent;
rightRotate(t, x);
}
x->parent->color = BLACK; //交換顏色
x->parent->parent->color = RED;
leftRotate(t, x->parent->parent);
}
}
t->root->color = BLACK;
}
void rightRotate(RBTree *t, Node *p){
Node *s = p->leftChild;
p->leftChild = s->rightChild;
if(s->rightChild != t->NIL){
s->rightChild->parent = p;
}
s->parent = p->parent;
if(p->parent == t->NIL){
t->root = s;
}else if(p == p->parent->leftChild){
p->parent->leftChild = s;
}else{
p->parent->rightChild = s;
}
s->rightChild = p;
p->parent = s;
}
void leftRotate(RBTree *t, Node *p){
Node *s = p->rightChild;
p->rightChild = s->leftChild;
if(s->leftChild != t->NIL){
s->leftChild->parent = p;
}
s->parent = p->parent;
if(p->parent == t->NIL){
t->root = s;
}else if(p == p->parent->leftChild){
p->parent->leftChild = s;
}else{
p->parent->rightChild = s;
}
s->leftChild = p;
p->parent = s;
}
void initRBTree(RBTree **t){
(*t) = (RBTree *)malloc(sizeof(RBTree));
(*t)->NIL = createNode();
(*t)->root = (*t)->NIL;
(*t)->NIL->color = BLACK;
(*t)->NIL->data = -1;
}
Node *createNode(){
Node *p = (Node *)malloc(sizeof(Node));
p->color = BLACK;
p->data = 0;
p->leftChild = p->rightChild = p->parent = NULL;
return p;
}
#endif(2)、測試代碼：
#include<stdio.h>
typedef int Type;
#include"RBTree.h"
int main(void){
RBTree *rb;
int ar[] = {10, 7, 4, 8, 15, 5, 6, 11, 13, 12,};
//int ar[] = {10, 7, 5};
int n = sizeof(ar)/sizeof(int);
int i;
initRBTree(&rb);
for(i = 0; i < n; i++){
insert(rb, ar[i]);
}
printf("0代表紅，1代表黑\n");
showRBTree(*rb);
return 0;
} (3)、測試結果：
6、刪除算法
紅黑樹的刪除思路：
在搜索二叉樹中，永遠記住刪除結點，先化為只有左樹或右樹一個分支在解決；
所以，先找到結點，在轉換為只有一個分支的，在刪除(只能刪除紅色的結點)，可能通過旋轉調整函數進行平衡！！！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
