|
|
2008-11-10補充---這份代碼仍然是有問題的, 再次的修正版本在這里:http://www.shnenglu.com/converse/archive/2008/11/10/66530.html在之前，我曾經(jīng)給出過一份紅黑樹的實現(xiàn)代碼，很多人提出異議，說是代碼有問題，我曾經(jīng)做過一些測試，貌似都沒有出錯，因為這份代碼是在我學(xué)習(xí)紅黑樹之后很久才貼出來的，所以后來沒有再仔細看這份代碼。 最近，因為工作上的原因，我需要使用紅黑樹結(jié)構(gòu)，本以為拿來那份代碼稍加改動就可以了，沒想到代碼調(diào)試了很久都還有問題，于是，我決定重新補習(xí)紅黑樹的知識，仔細查看了原有的代碼，才發(fā)現(xiàn)是有問題的，在這里，給出修正版本的代碼，希望這次是沒有錯誤:) 請大家原諒我的疏忽。 我就不在原來的頁面修改那份代碼了，只是在上面加上說明那份代碼是有錯誤的。
 /*-----------------------------------------------------------
RB-Tree的插入和刪除操作的實現(xiàn)算法
參考資料:
1) <<Introduction to algorithm>>
2) <<STL源碼剖析>>
3) sgi-stl中stl_tree.h中的實現(xiàn)算法
4) http://epaperpress.com/sortsearch/index.html
5) http://www.ececs.uc.edu/~franco/C321/html/RedBlack/redblack.html
作者：李創(chuàng) (http://www.shnenglu.com/converse/)
您可以自由的傳播，修改這份代碼，轉(zhuǎn)載處請注明原作者
紅黑樹的幾個性質(zhì):
1) 每個結(jié)點只有紅和黑兩種顏色
2) 根結(jié)點是黑色的
3)空節(jié)點是黑色的（紅黑樹中，根節(jié)點的parent以及所有葉節(jié)點lchild、rchild都不指向NULL，而是指向一個定義好的空節(jié)點）。
4) 如果一個結(jié)點是紅色的,那么它的左右兩個子結(jié)點的顏色是黑色的
5) 對于每個結(jié)點而言,從這個結(jié)點到葉子結(jié)點的任何路徑上的黑色結(jié)點
的數(shù)目相同
-------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef int KEY;
enum NODECOLOR
{
BLACK = 0,
RED = 1
};
typedef struct RBTree
{
struct RBTree *parent;
struct RBTree *left, *right;
KEY key;
NODECOLOR color;
}RBTree, *PRBTree;
PRBTree RB_InsertNode(PRBTree root, KEY key);
PRBTree RB_InsertNode_Fixup(PRBTree root, PRBTree z);
PRBTree RB_DeleteNode(PRBTree root, KEY key);
PRBTree RB_DeleteNode_Fixup(PRBTree root, PRBTree x , PRBTree x_parent);
PRBTree Find_Node(PRBTree root, KEY key);
void Left_Rotate(PRBTree A, PRBTree& root);
void Right_Rotate(PRBTree A, PRBTree& root);
void Mid_Visit(PRBTree T);
void Mid_DeleteTree(PRBTree T);
void Print_Node(PRBTree node);
/*-----------------------------------------------------------
| A B
| / \ ==> / \
| a B A y
| / \ / \
| b y a b
-----------------------------------------------------------*/
void Left_Rotate(PRBTree A, PRBTree& root)
{
PRBTree B;
B = A->right;
A->right = B->left;
if (NULL != B->left)
B->left->parent = A;
B->parent = A->parent;
// 這樣三個判斷連在一起避免了A->parent = NULL的情況
if (A == root)
{
root = B;
}
else if (A == A->parent->left)
{
A->parent->left = B;
}
else
{
A->parent->right = B;
}
B->left = A;
A->parent = B;
}
/*-----------------------------------------------------------
| A B
| / \ / \
| B y ==> a A
| / \ / \
|a b b y
-----------------------------------------------------------*/
void Right_Rotate(PRBTree A, PRBTree& root)
{
PRBTree B;
B = A->left;
A->left = B->right;
if (NULL != B->right)
B->right->parent = A;
B->parent = A->parent;
// 這樣三個判斷連在一起避免了A->parent = NULL的情況
if (A == root)
{
root = B;
}
else if (A == A->parent->left)
{
A->parent->left = B;
}
else
{
A->parent->right = B;
}
A->parent = B;
B->right = A;
}
/*-----------------------------------------------------------
| 函數(shù)作用:查找key值對應(yīng)的結(jié)點指針
| 輸入?yún)?shù):根節(jié)點root,待查找關(guān)鍵值key
| 返回參數(shù):如果找到返回結(jié)點指針,否則返回NULL
-------------------------------------------------------------*/
PRBTree Find_Node(PRBTree root, KEY key)
{
PRBTree x;
// 找到key所在的node
x = root;
do
{
if (key == x->key)
break;
if (key < x->key)
{
if (NULL != x->left)
x = x->left;
else
break;
}
else
{
if (NULL != x->right)
x = x->right;
else
break;
}
} while (NULL != x);
return x;
}
/*-----------------------------------------------------------
| 函數(shù)作用:在樹中插入key值
| 輸入?yún)?shù):根節(jié)點root,待插入結(jié)點的關(guān)鍵值key
| 返回參數(shù):根節(jié)點root
-------------------------------------------------------------*/
PRBTree RB_InsertNode(PRBTree root, KEY key)
{
PRBTree x, y;
PRBTree z;
if (NULL == (z = (PRBTree)malloc(sizeof(RBTree))))
{
printf("Memory alloc error\n");
return NULL;
}
z->key = key;
// 得到z的父節(jié)點, 如果KEY已經(jīng)存在就直接返回
x = root, y = NULL;
while (NULL != x)
{
y = x;
if (key < x->key)
{
if (NULL != x->left)
{
x = x->left;
}
else
{
break;
}
}
else if (key > x->key)
{
if (NULL != x->right)
{
x = x->right;
}
else
{
break;
}
}
else
{
return root;
}
}
if (NULL == y || y->key > key)
{
if (NULL == y)
root = z;
else
y->left = z;
}
else
{
y->right = z;
}
// 設(shè)置z的左右子樹為空并且顏色是red，注意新插入的節(jié)點顏色都是red
z->parent = y;
z->left = z->right = NULL;
z->color = RED;
// 對紅黑樹進行修正
return RB_InsertNode_Fixup(root, z);
}
/*-----------------------------------------------------------
| 函數(shù)作用:對插入key值之后的樹進行修正
| 輸入?yún)?shù):根節(jié)點root,插入的結(jié)點z
| 返回參數(shù):根節(jié)點root
-------------------------------------------------------------*/
PRBTree RB_InsertNode_Fixup(PRBTree root, PRBTree z)
{
PRBTree y;
while (root != z && RED == z->parent->color) // 當(dāng)z不是根同時父節(jié)點的顏色是red
{
if (z->parent == z->parent->parent->left) // 父節(jié)點是祖父節(jié)點的左子樹
{
y = z->parent->parent->right; // y為z的伯父節(jié)點
if (NULL != y && RED == y->color) // 伯父節(jié)點存在且顏色是red
{
z->parent->color = BLACK; // 更改z的父節(jié)點顏色是B
y->color = BLACK; // 更改z的伯父節(jié)點顏色是B
z->parent->parent->color = RED; // 更改z的祖父節(jié)點顏色是B
z = z->parent->parent; // 更新z為它的祖父節(jié)點
}
else // 無伯父節(jié)點或者伯父節(jié)點顏色是b
{
if (z == z->parent->right) // 如果新節(jié)點是父節(jié)點的右子樹
{
z = z->parent;
Left_Rotate(z, root);
}
z->parent->color = BLACK; // 改變父節(jié)點顏色是B
z->parent->parent->color = RED; // 改變祖父節(jié)點顏色是R
Right_Rotate(z->parent->parent, root);
}
}
else // 父節(jié)點為祖父節(jié)點的右子樹
{
y = z->parent->parent->left; // y為z的伯父節(jié)點
if (NULL != y && RED == y->color) // 如果y的顏色是red
{
z->parent->color = BLACK; // 更改父節(jié)點的顏色為B
y->color = BLACK; // 更改伯父節(jié)點的顏色是B
z->parent->parent->color = RED; // 更改祖父節(jié)點顏色是R
z = z->parent->parent; // 更改z指向祖父節(jié)點
}
else // y不存在或者顏色是B
{
if (z == z->parent->left) // 如果是父節(jié)點的左子樹
{
z = z->parent;
Right_Rotate(z, root);
}
z->parent->color = BLACK; // 改變父節(jié)點的顏色是B
z->parent->parent->color = RED; // 改變祖父節(jié)點的顏色是RED
Left_Rotate(z->parent->parent, root);
}
}
} // while(RED == z->parent->color)
// 根節(jié)點的顏色始終都是B
root->color = BLACK;
return root;
}
/*-----------------------------------------------------------
| 函數(shù)作用:在樹中刪除key值
| 輸入?yún)?shù):根節(jié)點root,待插入結(jié)點的關(guān)鍵值key
| 返回參數(shù):根節(jié)點root
-------------------------------------------------------------*/
PRBTree RB_DeleteNode(PRBTree root, KEY key)
{
PRBTree x, y, z, x_parent;
// 首先查找需要刪除的節(jié)點
z = Find_Node(root, key);
if (NULL == z)
return root;
y = z, x = NULL, x_parent = NULL;
// y是x按照中序遍歷樹的后繼
if (NULL == y->left)
{
x = y->right;
}
else
{
if (NULL == y->right)
{
x = y->left;
}
else
{
y = y->right;
while (NULL != y->left)
y = y->left;
x = y->right;
}
}
if (y != z)
{
z->left->parent = y;
y->left = z->left;
if (y != z->right)
{
x_parent = y->parent;
if (NULL != x)
x->parent = y->parent;
y->parent->left = x;
y->right = z->right;
z->right->parent = y;
}
else
{
x_parent = y;
}
if (root == z)
{
root = y;
}
else if (z == z->parent->left)
{
z->parent->left = y;
}
else
{
z->parent->right = y;
}
y->parent = z->parent;
NODECOLOR color = y->color;
y->color = z->color;
z->color = color;
y = z;
}
else
{
x_parent = y->parent;
if (NULL != x)
x->parent = y->parent;
if (root == z)
{
root = y;
}
else if (z == z->parent->left)
{
z->parent->left = x;
}
else
{
z->parent->right = x;
}
}
if (BLACK == y->color)
{
root = RB_DeleteNode_Fixup(root, x, x_parent);
}
free(y);
return root;
}
/*-----------------------------------------------------------
| 函數(shù)作用:對刪除key值之后的樹進行修正
| 輸入?yún)?shù):根節(jié)點root,刪除的結(jié)點的子結(jié)點x
| 返回參數(shù):根節(jié)點root
-------------------------------------------------------------*/
PRBTree RB_DeleteNode_Fixup(PRBTree root, PRBTree x, PRBTree x_parent)
{
PRBTree w;
while (x != root && (NULL == x || BLACK == x->color))
{
if (x == x_parent->left) // 如果x是左子樹
{
w = x_parent->right; // w是x的兄弟結(jié)點
if (RED == w->color) // 如果w的顏色是紅色
{
w->color = BLACK;
x_parent->color = RED;
Left_Rotate(x_parent, root);
w = x_parent->right;
}
if ((NULL == w->left || BLACK == w->left->color) &&
(NULL == w->right || BLACK == w->right->color))
{
w->color = RED;
x = x_parent;
x_parent = x_parent->parent;
}
else
{
if (NULL == w->right || BLACK == w->right->color)
{
if (NULL != w->left)
w->left->color = BLACK;
w->color = RED;
Right_Rotate(w, root);
w = x_parent->right;
}
w->color = x_parent->color;
x_parent->color = BLACK;
if (NULL != w->right)
w->right->color = BLACK;
Left_Rotate(x->parent, root);
break;
}
}
else
{
w = x_parent->left; // w是x的兄弟結(jié)點
if (RED == w->color) // 如果w的顏色是紅色
{
w->color = BLACK;
x_parent->color = RED;
Right_Rotate(x_parent, root);
w = x_parent->left;
}
if ((NULL == w->left || BLACK == w->left->color) &&
(NULL == w->right || BLACK == w->right->color))
{
w->color = RED;
x = x_parent;
x_parent = x_parent->parent;
}
else
{
if (NULL == w->left || BLACK == w->left->color)
{
if (NULL != w->right)
w->right->color = BLACK;
w->color = RED;
Left_Rotate(w, root);
w = x_parent->left;
}
w->color = x_parent->color;
x_parent->color = BLACK;
if (NULL != w->left)
w->left->color = BLACK;
Right_Rotate(x->parent, root);
break;
}
}
}
x->color = BLACK;
return root;
}
void Print_Node(PRBTree node)
{
char* color[] = {"BLACK", "RED"};
printf("Key = %d,\tcolor = %s", node->key, color[node->color]);
if (NULL != node->parent)
printf(",\tparent = %d", node->parent->key);
if (NULL != node->left)
printf(",\tleft = %d", node->left->key);
if (NULL != node->right)
printf(",\tright = %d", node->right->key);
printf("\n");
}
// 中序遍歷樹, 加了一個判斷, 如果輸出的數(shù)據(jù)不滿足序列關(guān)系就報錯退出
void Mid_Visit(PRBTree T)
{
if (NULL != T)
{
if (NULL != T->left)
{
if (T->left->key > T->key)
{
printf("wrong!\n");
exit(-1);
}
Mid_Visit(T->left);
}
Print_Node(T);
if (NULL != T->right)
{
if (T->right->key < T->key)
{
printf("wrong\n");
exit(-1);
}
Mid_Visit(T->right);
}
}
}
// 中序刪除樹的各個節(jié)點
void Mid_DeleteTree(PRBTree T)
{
if (NULL != T)
{
if (NULL != T->left)
Mid_DeleteTree(T->left);
PRBTree temp = T->right;
free(T);
T = NULL;
if (NULL != temp)
Mid_DeleteTree(temp);
}
}
void Create_New_Array(int array[], int length)
{
for (int i = 0; i < length; i++)
{
array[i] = rand() % 256;
}
}
int main(int argc, char *argv[])
{
srand(time(NULL));
PRBTree root = NULL;
int i;
for (i = 0; i < 100000; i++)
{
root = RB_InsertNode(root, rand() % 10000);
}
Mid_Visit(root);
// 刪除整顆樹
Mid_DeleteTree(root);
return 0;
}
|