?? 紅黑樹插入程序.cpp
字號:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream.h>
#define LENGTH 100
static int flag = 1; //是否出現紅--紅沖突的標志
static int flag2 = 0; //是計數虛擬節點的
static int height=0; // 記錄黑色高度
static flag3 = 1;
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 z);
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);
void Left_Rotate(PRBTree A, PRBTree& root)
{
PRBTree B;
B = A->right;
if (NULL == B)
return;
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;
}
void Right_Rotate(PRBTree A, PRBTree& root)
{
PRBTree B;
B = A->left;
if (NULL == B)
return;
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;
}
/**//*-----------------------------------------------------------
| 函數作用:查找key值對應的結點指針
| 輸入參數:根節點root,待查找關鍵值key
| 返回參數:如果找到返回結點指針,否則返回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;
}
/**//*-----------------------------------------------------------
| 函數作用:在樹中插入key值
| 輸入參數:根節點root,待插入結點的關鍵值key
| 返回參數:根節點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的父節點
x = root, y = NULL;
while (NULL != x)
{
y = x;
if (z->key < x->key)
{
if (NULL != x->left)
{
x = x->left;
}
else
{
break;
}
}
else
{
if (NULL != x->right)
{
x = x->right;
}
else
{
break;
}
}
}
// 把z放到合適的位置
z->parent = y;
if (NULL == y)
{
root = z;
}
else
{
if (z->key < y->key)
y->left = z;
else
y->right = z;
}
// 設置z的左右子樹為空并且顏色是red，注意新插入的節點顏色都是red
z->left = z->right = NULL;
z->color = RED;
// 對紅黑樹進行修正
return RB_InsertNode_Fixup(root, z);
}
/**//*-----------------------------------------------------------
| 函數作用:對插入key值之后的樹進行修正
| 輸入參數:根節點root,插入的結點z
| 返回參數:根節點root
-------------------------------------------------------------*/
PRBTree RB_InsertNode_Fixup(PRBTree root, PRBTree z)
{
PRBTree y;
while (root != z && RED == z->parent->color) // 當z不是根同時父節點的顏色是red
{
if (z->parent == z->parent->parent->left) // 父節點是祖父節點的左子樹
{
y = z->parent->parent->right; // y為z的伯父節點
if (NULL != y && RED == y->color) // 伯父節點存在且顏色是red
{
z->parent->color = BLACK; // 更改z的父節點顏色是B
y->color = BLACK; // 更改z的伯父節點顏色是B
z->parent->parent->color = RED; // 更改z的祖父節點顏色是B
z = z->parent->parent; // 更新z為它的祖父節點
}
else // 無伯父節點或者伯父節點顏色是b
{
if (z == z->parent->right) // 如果新節點是父節點的右子樹
{
z = z->parent;
Left_Rotate(z, root);
}
z->parent->color = BLACK; // 改變父節點顏色是B
z->parent->parent->color = RED; // 改變祖父節點顏色是R
Right_Rotate(z->parent->parent, root);
}
}
else // 父節點為祖父節點的右子樹
{
y = z->parent->parent->left; // y為z的伯父節點
if (NULL != y && RED == y->color) // 如果y的顏色是red
{
z->parent->color = BLACK; // 更改父節點的顏色為B
y->color = BLACK; // 更改伯父節點的顏色是B
z->parent->parent->color = RED; // 更改祖父節點顏色是R
z = z->parent->parent; // 更改z指向祖父節點
}
else // y不存在或者顏色是B
{
if (z == z->parent->left) // 如果是父節點的左子樹
{
z = z->parent;
Right_Rotate(z, root);
}
z->parent->color = BLACK; // 改變父節點的顏色是B
z->parent->parent->color = RED; // 改變祖父節點的顏色是RED
Left_Rotate(z->parent->parent, root);
}
}
} // while(RED == z->parent->color)
// 根節點的顏色始終都是B
root->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");
}
void BlackHeight(PRBTree T)
{ PRBTree p =T;
int temp;
flag2++;
while(p->parent!=NULL)
{ p=p->parent;
if(p->color==BLACK)
temp++;
}
if(flag==1)height= temp;
if(temp!=height) flag3=0;
}
void Mid_Visit(PRBTree T)
{ if(T->right==NULL&&T->left==NULL)
BlackHeight(T);
if (NULL != T)
{
if (NULL != T->left)
{ if(T->color==RED&&T->left->color==RED)
flag = 0;
Mid_Visit(T->left);}
Print_Node(T);
if (NULL != T->right)
{if(T->color==RED&&T->right->color==RED)
flag = 0;
Mid_Visit(T->right);}
}
}
void Create_New_Array(int array[], int length)
{
for (int i = 0; i < length; i++)
{
array[i] = rand() % 1000;
}
}
int main(int argc, char *argv[])
{
int array[LENGTH];
srand(time(NULL));
Create_New_Array(array, LENGTH);
PRBTree root = NULL;
int i;
for (i = 0; i <LENGTH; i++)
{
root = RB_InsertNode(root, array[i]);
}
Mid_Visit(root);
if(flag==0)
cout<<"出現了紅--紅沖突"<<endl; //檢驗的三條1:是否有紅-紅沖突2:是否中序遍歷是由小到大3:所有虛擬節點的黑色高度是；一樣的
else {cout<<"沒有出現紅-紅沖突"<<endl;
if(flag3==0)
cout<<"黑色高度不一樣,不是紅黑樹"<<endl;
else cout<<"是紅黑樹"<<endl;
}
return 0;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -