0

赤黒木がほぼ完成しましたが、削除が誤動作しています。削除されない可能性のあるノードを削除する可能性があります。ルートを削除して印刷オプションを押すと、ツリーにすでに存在するノードが画面にスパム送信されます。プログラムがクラッシュするまで、2,1,7,5,8,11,14,15,4削除root=7して順番に印刷するなどのテストツリーで取得します。2,4,5,8,1,2,4,5,8,1,.....2を削除すると、プログラムが即座にクラッシュします。ノード11は、1-4-15のようなすべての葉と同様に、正常に削除されます。デバッグの問題を見つけようとしましたが、すべて正常に機能しているようです。このコードは、コーメンのアルゴリズムの紹介に基づいています。ありがとう！ 

void RB_delete(struct node* z,struct node* y) //delete z y=z on call
{
    struct node *x;
    enum type originalcolor;         //x  moves into y's original position
    originalcolor=y->color;     // Keep track of original color

        if (z->LC==nill)        //case 1: (z has no LC)
        {
            x=z->RC;
            RB_transplant(z,z->RC); 
        else if (z->RC==nill)           //case 2: z has LC but no RC
        {
            x=z->LC;
            RB_transplant(z,z->LC);
        }
        else            // two cases: z has both Children
        {
            y=tree_minimum(z->RC);      //find  successor
            originalcolor=y->color;     //save color of successor
            x=y->RC;
                if (y->P==z)    //successor has no LC cause its nill
                    x->P=y;
                else
                {
                    RB_transplant(y,y->RC);
                    y->RC=z->RC;
                    y->RC->P=y;
                }
            RB_transplant(z,y);
            y->LC=z->LC;
            y->LC->P=y;
            y->color=z->color;
        }
        if (originalcolor == black)
            RB_delete_fix(x);
        free(z);
}

void io_print(struct node *aux,struct node *auxnill)
{
    HANDLE  hConsole;
    hConsole = GetStdHandle(STD_OUTPUT_HANDLE);
    if(aux != auxnill)
    {
        io_print(aux->LC,auxnill);
        if (aux->color==red)
        {
            SetConsoleTextAttribute(hConsole, 12);
            printf("%d,\n",aux->key);fflush(stdout);
            SetConsoleTextAttribute(hConsole, 15);
        }
        if (aux->color==black)
        {
            SetConsoleTextAttribute(hConsole, 9);
            printf("%d,\n",aux->key);fflush(stdout);
            SetConsoleTextAttribute(hConsole, 15);
        }
            io_print(aux->RC,auxnill);
    }
}
4

1 に答える 1

0

さて、移植でポインタの置き忘れが1つありました...そして、あまり注意を払っていなかったので、それを見つけることができませんでした。私が持っていた：

void RB_transplant(struct node *aux,struct node *auxchild)  //replace the subtree rooted at node aux with the subtree rooted at aux-LC or aux->RC
{
    if (aux->P==nill)                           //if aux=root child becomes root
        root=auxchild;
    else if (aux==aux->P->LC)               //if child is a LC
        aux->P->LC=auxchild;                
    else aux->P->RC=auxchild;                   //if child is RC //connect grandparent's->RC with child
        auxchild->P=aux->P;                         //connect child to point to parent
}

問題は aux =>auxhild の 5 行目にありました... 問題は解決しました :)

于 2012-01-09T09:12:29.410 に答える