Программа с красно-черным деревом попадает в бесконечный цикл

Question

У меня есть реализация дерева R-B на основе псевдокода в этой книге начиная со страницы 308. Я перевел псевдокод на 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, поэтому я не думаю, что это проблема. Остальной программе нужно только изменить наименьшее / наибольшее число из этого дерева, поэтому нет никакой реализации для удаления узлов с двумя дочерними элементами и т. Д. Извините, если этот вопрос нарушает какие-либо правила, но я действительно не могу понять, почему это не так. не работает Заранее спасибо.