PDA

View Full Version : Code red black tree trong c++ chạy không đúng?



squall_ttthp
21-02-2012, 03:08 PM
Mình có viết 1 bài cài đặt cây đỏ đen như thế này.

#include <cstdio>
#include <algorithm>
#include <string>
enum rbt_color { RED, BLACK };
struct rbt_node
{
int key;//khoa
//int sub_tree;
rbt_node *left;
rbt_node *right;
rbt_node *parent;
rbt_color color;
};
//ktra do
int is_RED(rbt_node *root)
{
return root != NULL && root->color == RED;
}
//ktra den
int is_BLACK(rbt_node *root)
{
return root != NULL && root->color == BLACK;
}
//tao 1 node voi cac gia tri ban dau
rbt_node *make_node(int key)
{
rbt_node *new_node = new rbt_node;
new_node->key = key;
new_node->color = RED;
new_node->left = NULL;
new_node->right = NULL;
//new_node->sub_tree = 1;
return new_node;
}
// them 1 node moi nhung chua ktra mau
//tree-luu cay, node-luu node can them, parent-node cha
void add_node(rbt_node *&root, rbt_node *node, rbt_node *parent)
{
if(root == NULL)
{
node->parent = parent;
root = node;
}
else if(node->key < root->key)
{
//root->sub_tree += 1;
add_node(root->left, node, root);
}
else if(node->key > root->key)
{
//root->sub_tree += 1;
add_node(root->right, node, root);
}
}
//quay trai
void left_rotate(rbt_node *&root, rbt_node *&node)
{
rbt_node *new_node = node->right;
if(new_node != NULL)
{
node->right = new_node->left;
if(new_node->left != NULL)
new_node->left->parent = node;
if(node->parent == NULL)
root = new_node;
else if(node == node->parent->left)
node->parent->left = new_node;
else
node->parent->right = new_node;

new_node->left = node;
new_node->parent = node->parent;
new_node->left->parent = new_node;
}
}
//quay phai
void right_rotate(rbt_node *&root, rbt_node *&node)
{

rbt_node *new_node = node->left;
if(new_node != NULL)
{
node->left = new_node->right;
if(new_node->right != NULL)
new_node->right->parent = node;
if(node->parent == NULL)
root = new_node;
else if(node == node->parent->right)
node->parent->right = new_node;
else
node->parent->left = new_node;

new_node->right = node;
new_node->parent = node->parent;
new_node->right->parent = new_node;
}
}
//them node va chinh mau
void add_rbt_node(rbt_node *&root, int key, rbt_node *parent)
{
rbt_node *n = make_node(key);
add_node(root, n, parent);
while(n != root && n->parent->color == RED)//ko phai goc va cha la RED
{
if(n->parent == n->parent->parent->left)
{
rbt_node *uncle = n->parent->parent->right;//node chu
if(uncle != NULL && uncle->color == RED)//ktra chu, neu la RED -> TH3
{
n->parent->color == BLACK;
uncle->color = BLACK;
n->parent->parent->color = RED;
n = n->parent->parent;
}
else//TH4
{
if(n == n->parent->right)
{
n = n->parent;
left_rotate(root, n);
}
n->parent->color = BLACK;
n->parent->parent->color = RED;
right_rotate(root, n->parent->parent);
}
}
else
{
rbt_node *uncle = n->parent->parent->left;
if(uncle != NULL && uncle->color == RED)//ktra chu, neu la RED -> TH3
{
n->parent->color = BLACK;
uncle->color = BLACK;
n->parent->parent->color = RED;
n = n->parent->parent;
}
else//TH4
{
if(n == n->parent->left)
{
n = n->parent;
right_rotate(root, n);
}
n->parent->color = BLACK;
n->parent->parent->color = RED;
left_rotate(root, n->parent->parent);
}
}
}
root->color = BLACK;//cho node goc BLACK tranh bi thay doi thanh RED trong qua trinh Fix
}
//tim kiem
rbt_node *search_key(rbt_node *root, int key)
{
if(root == NULL)//cho con trong
return NULL;//ko tim thay
else if(root->key == key)//da co key do
return root;//tim thay
else if(root->key < key)
search_key(root->right, key);
else if(root->key > key)
search_key(root->left, key);
}
// node anh em
rbt_node *sibling(rbt_node *n)
{
if (n == n->parent->left)
return n->parent->right;
else
return n->parent->left;
}
// kiem tra node co phai node la ko
bool is_leaf(rbt_node *n)
{
if(n->left == NULL && n->right == NULL)
return true;
return false;
}
//du node con vao node can xoa
void replace_node(rbt_node *&n, rbt_node *&child)
{
child->parent = n->parent;
}
// duyet cay
void print_out(rbt_node *root)
{
if(root != NULL)
{
print_out(root->left);

printf("key:%d\t", root->key);
if(root->color == BLACK)
printf("color:black\t");
else
printf("color:red\t");
if(root->parent != NULL)
printf("parent:%d\t",root->parent->key);
else
printf("parent:-\t");
if(root->left != NULL)
printf("left:%d\t",root->left->key);
else
printf("left:-\t");
if(root->right != NULL)
printf("right:%d\t",root->right->key);
else
printf("right:-\t");
printf("\n");

print_out(root->right);
}
}

int main()
{
int key;
rbt_node *root = NULL;
int option=0;
while(option!=5)
{
printf("=====Lua chon=====\n-Them node(1)\n-Xoa node(2)\n-Tim node(3)\n-Hien thi (4)\n-Thoat(5)\n");
do option=fgetc(stdin); while(-1 != option && isspace(option));
option-='0';
switch(option)
{
case 1:
printf("Nhap node can chen: ");
scanf("%d",&key);
if(search_key(root,key) != NULL)
{
printf("Node mang gia tri %d da co!\n", key);
}
else
{
add_rbt_node(root,key,NULL);
}
break;
case 2:
printf("Nhap node can xoa: ");
scanf("%d",&key);
if(search_key(root,key) == NULL)
{
printf("Node mang gia tri %d khong co!\n", key);
}
else
{
//delete_rbt_node(root,key);
}
break;
case 3:
printf("Nhap key can tim: ");
scanf("%d",&key);
if(search_key(root,key) != NULL)
printf("Cay co chua khoa: %d\n", key);
else
printf("Cay khong chua khoa: %d\n", key);
break;
case 4:
printf("*****HIEN THI*****\n");
print_out(root);
break;
case 5: break;
default:
printf("Loi nhap. Thu lai.\n");
}
}
system("PAUSE");
return 0;
}


khi chạy nó như thế này:
http://i1052.photobucket.com/albums/s445/squall_ttthp/1.jpg

thế là mình sai ở hàm search_key mà chưa hiểu sao, mong mọi người giúp đỡ.

heocoi_minmin
04-01-2013, 09:17 AM
hàm sercg_key thiếu return:D:D:D

heocoi_minmin
04-01-2013, 09:19 AM
hàm searrch_key thiếu return :D:D:D

daict
03-05-2013, 04:33 PM
//du node con vao node can xoa
void replace_node(rbt_node *&n, rbt_node *&child)
{
child->parent = n->parent;
}
hàm nay có đúng ko vậy bạn???