c - 红黑树程序陷入无限循环
问题描述
我有一个基于本书第 308 页的伪代码的 RB 树实现。我已将伪代码翻译成 C 以拥有一个工作程序，并让我更容易理解 RB 树是如何通过调试工作的但不幸的是，程序在这个函数中陷入（有时，取决于输入）无限循环：
void InsFixRBTREE(Tree*& tree, node*& newnode){
node* temp = newnode;
node* temp2 = tree->dummy;
if(tree->root == newnode){
newnode->color = 'B';
return;
}
while(temp->parent->color == 'R'){
if(temp->parent == temp->parent->parent->left){
temp2 = temp->parent->parent->right;
if(temp2->color == 'R'){
temp->parent->color = 'B';
temp2->color = 'B';
temp->parent->parent->color = 'R';
temp = temp->parent->parent;
}
else if ( temp == temp->parent->right){
temp = temp->parent;
RotateLeft(tree, temp);
}else{
temp->parent->color = 'B';
temp->parent->parent->color = 'R';
RotateRight(tree, temp->parent->parent);
}
}else {//if uncle is on the rightside
temp2 = temp->parent->parent->left;
if(temp2->color == 'R'){
temp->parent->color = 'B';
temp2->color = 'B';
temp->parent->parent->color = 'R';
temp = temp->parent->parent;
}
else if ( temp == temp->parent->left){
temp = temp->parent;
RotateRight(tree, temp);
}else{
temp->parent->color = 'B';
temp->parent->parent->color = 'R';
RotateLeft(tree, temp->parent->parent);
}
}
}
tree->root->color = 'B';
}
我对 RB 树的理解不够充分，解决这个问题将极大地帮助我了解它们是如何工作的。我的程序中完整的 RB 树实现代码：
struct node{
node* left;
node* right;
node* leftneighbour;
node* rightneighbour;
node* parent;
unsigned int value;
char color;
};
struct Tree{
node* root;
node* dummy;
};
node* ReturnSmallest(Tree* &tree){
node* temp = tree->root;
node* behind = tree->dummy;
while(temp != tree->dummy){
behind = temp;
temp = temp->left;
}
return behind;
}
node* ReturnBiggest(Tree* &tree){
node* temp = tree->root;
node* behind = tree->dummy;
while(temp != tree->dummy){
behind = temp;
temp = temp->right;
}
return behind;
}
void RotateRight(Tree*& tree, node* &newnode){
node* temp = newnode->left;
newnode->left = temp->right;
if(temp->right != tree->dummy){
temp->right->parent = newnode;
}
temp->parent = newnode->parent;
if(newnode->parent == tree->dummy){
tree->root = temp;
}else if (newnode == newnode->parent->right){
newnode->parent->right = temp;
}else{
newnode->parent->left = temp;
}
temp->right = newnode;
newnode->parent = temp;
}
void RotateLeft(Tree*& tree, node* &newnode){
node* temp = newnode->right;
newnode->right = temp->left;
if(temp->left != tree->dummy){
temp->left->parent = newnode;
}
temp->parent = newnode->parent;
if(newnode->parent == tree->dummy){
tree->root = temp;
}else if (newnode == newnode->parent->left){
newnode->parent->left = temp;
}else{
newnode->parent->right = temp;
}
temp->left = newnode;
newnode->parent = temp;
}
void DelFixRBTREE(Tree* &tree, node* &newnode){
node* temp = newnode;
node* uncletemp = tree->dummy;
while(temp->color == 'B' && temp != tree->root){
if(temp == temp->parent->left){
uncletemp = temp->parent->right;
if(uncletemp->color == 'R'){
uncletemp->color = 'B';
temp->parent->color = 'R';
RotateLeft(tree, temp->parent);
uncletemp = temp->parent->right;
}
if(uncletemp->left->color == 'B' && uncletemp->right->color == 'B'){
uncletemp->color = 'R';
temp = temp->parent;
}
else if (uncletemp->right->color == 'B'){
uncletemp->left->color = 'B';
uncletemp->color = 'R';
RotateRight(tree, uncletemp);
uncletemp = temp->parent->right;
}else{
uncletemp->color = temp->parent->color;
temp->parent->color = 'B';
uncletemp->right->color = 'B';
RotateLeft(tree, temp->parent);
temp = tree->root;
}
}else{
if(temp == temp->parent->right){
uncletemp = temp->parent->left;
if(uncletemp->color == 'R'){
uncletemp->color = 'B';
temp->parent->color = 'R';
RotateRight(tree, temp->parent);
uncletemp = temp->parent->left;
}
if(uncletemp->right->color == 'B' && uncletemp->left->color == 'B'){
uncletemp->color = 'R';
temp = temp->parent;
}
else if (uncletemp->left->color == 'B'){
uncletemp->right->color = 'B';
uncletemp->color = 'R';
RotateLeft(tree, uncletemp);
uncletemp = temp->parent->left;
}else{
uncletemp->color = temp->parent->color;
temp->parent->color = 'B';
uncletemp->left->color = 'B';
RotateRight(tree, temp->parent);
temp = tree->root;
}
}
}
}
}
void InsFixRBTREE(Tree*& tree, node*& newnode){
node* temp = newnode;
node* temp2 = tree->dummy;
if(tree->root == newnode){
newnode->color = 'B';
return;
}
while(temp->parent->color == 'R'){
if(temp->parent == temp->parent->parent->left){
temp2 = temp->parent->parent->right;
if(temp2->color == 'R'){
temp->parent->color = 'B';
temp2->color = 'B';
temp->parent->parent->color = 'R';
temp = temp->parent->parent;
}
else if ( temp == temp->parent->right){
temp = temp->parent;
RotateLeft(tree, temp);
}else{
temp->parent->color = 'B';
temp->parent->parent->color = 'R';
RotateRight(tree, temp->parent->parent);
}
}else {//if uncle is on the rightside
temp2 = temp->parent->parent->left;
if(temp2->color == 'R'){
temp->parent->color = 'B';
temp2->color = 'B';
temp->parent->parent->color = 'R';
temp = temp->parent->parent;
}
else if ( temp == temp->parent->left){
temp = temp->parent;
RotateRight(tree, temp);
}else{
temp->parent->color = 'B';
temp->parent->parent->color = 'R';
RotateLeft(tree, temp->parent->parent);
}
}
}
tree->root->color = 'B';
}
void RBAddToTree(Tree* &tree, node* newnode){
node* temp = tree->root;
node* behind = tree->dummy;
(newnode)->left = tree->dummy;
(newnode)->right = tree->dummy;
newnode->color = 'R';
(newnode)->leftneighbour = tree->dummy;
(newnode)->rightneighbour = tree->dummy;
(newnode)->parent = tree->dummy;
if((tree->root) == tree->dummy){
(tree->root) = newnode;
newnode->color = 'B';
return;
}
do{
if(temp == tree->dummy){
(newnode)->parent = behind;
if(behind->value < (newnode)->value){
behind->right = newnode;
}else{
behind->left = newnode;
}
break;
}else{
behind = temp;
if((newnode)->value > temp->value)
temp = temp->right;
else if ((newnode)->value < temp->value)
temp = temp->left;
else{
temp->rightneighbour = (newnode);
(newnode)->leftneighbour = temp;
return;
}
}
}while(1);
InsFixRBTREE(tree, newnode);
}
void DeleteSmallest(node*& smallest, Tree*& tree){
node* temp = smallest;
if(smallest == tree->root){
if(smallest->rightneighbour != tree->dummy){
tree->root = smallest->rightneighbour;
smallest->rightneighbour->leftneighbour = tree->dummy;
smallest->rightneighbour->color = smallest->color;
smallest->rightneighbour->right = smallest->right;
if(smallest->right != tree->dummy){
smallest->right->parent = smallest->rightneighbour;
}
smallest->right = tree->dummy;
smallest->rightneighbour = tree->dummy;
}else{//kiedy nie ma
tree->root = smallest->right;
if(smallest->right != tree->dummy){
smallest->right->parent = tree->dummy;
}
smallest->right = tree->dummy;
if(temp->color == 'B')
DelFixRBTREE(tree, tree->root);
}
}else if (smallest->rightneighbour != tree->dummy){
smallest->parent->left = smallest->rightneighbour;
smallest->rightneighbour->parent = smallest->parent;
if(smallest->right != tree->dummy){
smallest->right->parent = smallest->rightneighbour;
}
smallest->rightneighbour->right = smallest->right;
smallest->rightneighbour->leftneighbour = tree->dummy;
smallest->rightneighbour->color = smallest->color;
smallest->rightneighbour = tree->dummy;
smallest->parent = tree->dummy;
smallest->right = tree->dummy;
}else if(smallest->right != tree->dummy){
char color = temp->color;
temp = smallest->right;
smallest->right->parent = smallest->parent;
smallest->parent->left = smallest->right;
smallest->parent = tree->dummy;
smallest->right = tree->dummy;
if(color == 'B')
DelFixRBTREE(tree, temp);
}else{//kiedy jest leaf
smallest->parent->left = tree->dummy;
smallest->parent = tree->dummy;
if(temp->color == 'B')
DelFixRBTREE(tree, smallest->right);
}
}
void DeleteBiggest(node*& biggest, Tree*& tree){
node* temp = biggest;
if(biggest == tree->root){
if(biggest->rightneighbour != tree->dummy){
tree->root = biggest->rightneighbour;
biggest->rightneighbour->leftneighbour = tree->dummy;
biggest->rightneighbour->color = biggest->color;
biggest->rightneighbour->left = biggest->left;
if(biggest->left != tree->dummy){
biggest->left->parent = biggest->rightneighbour;
}
biggest->left = tree->dummy;
biggest->rightneighbour = tree->dummy;
}else{
tree->root = biggest->left;
if(biggest->left != tree->dummy){
biggest->left->parent = tree->dummy;
}
biggest->left = tree->dummy;
if(temp->color == 'B')
DelFixRBTREE(tree, tree->root);
}
}else if (biggest->rightneighbour != tree->dummy){
biggest->parent->right = biggest->rightneighbour;
biggest->rightneighbour->parent = biggest->parent;
if(biggest->left != tree->dummy){
biggest->left->parent = biggest->rightneighbour;
}
biggest->rightneighbour->left = biggest->left;
biggest->rightneighbour->leftneighbour = tree->dummy;
biggest->rightneighbour->color = biggest->color;
biggest->rightneighbour = tree->dummy;
biggest->parent = tree->dummy;
biggest->left = tree->dummy;
}else if(biggest->left != tree->dummy){
char color = temp->color;
temp = biggest->left;
biggest->left->parent = biggest->parent;
biggest->parent->right = biggest->left;
biggest->parent = tree->dummy;
biggest->left = tree->dummy;
if(color == 'B')
DelFixRBTREE(tree, temp);
}else{
biggest->parent->right = tree->dummy;
biggest->parent = tree->dummy;
if(temp->color == 'B')
DelFixRBTREE(tree, biggest->left);
}
}
正如我所说，实现是从书中 1:1 伪代码翻译成 C 语言。该程序的其余部分在不平衡的 BST 上运行良好，所以我认为这不是问题。程序的其余部分只需要更改此树中的最小/最大数字，这就是为什么没有删除具有两个孩子的节点等的实现。如果这个问题违反任何规则，我很抱歉，但我真的不明白为什么它不不行。提前致谢。
解决方案
推荐阅读
- npm - 创建数据库并加载文件（npm stardog）
- python - 使用 Python 在等效图上同时递归
- python - 调用时未使用函数
- lisp - Lisp (Allegro Common Lisp) 如何在 lambda 中使用带有 ' vs #' 的变量
- r - 自定义 R 帮助文件 - 字体着色
- asp.net-core - 如何在 asp.net 核心中创建一个单例服务，其中 Iconfiguration 被传递到其构造函数中
- css - 在 Bootstrap 4 中看不到文本的响应式表格压缩表单字段
- javascript - 单击时平滑滚动到特定部分
- javascript - 使用 Playwright 自动化工具获取当前页面 url？
- python - 4-5 个请求后的 403 状态代码，每个请求之间有超时