-1

AVL バランス バイナリ ツリーを作成するコードを作成しようとしています。目的は、新しいノードが挿入されるたびに (AVL) バランスを維持するためにサブツリーを回転させることです。

(ノードの左側のサブツリーのすべての値は、このノードの値より小さくなければなりません。ノードの右側のサブツリーのすべての値は、このノードの値より大きくなければなりません)

私が書いたばかりのコードは、特定の順序で挿入された番号では機能しますが、他の順序では機能しません。たとえば、次の入力は正常に機能します。

10 7 14 12 15 3 0 

16 8 20 14 23 0

これはしません:

10 7 3 15 12 14 0 

10 7 5 14 13 0

なんで？

#include <stdio.h>
#include <stdlib.h>

typedef enum {false, true} Boolean;
typedef enum {minus = -1, zero, plus} balance;

typedef struct nohh {
    int info;
    balance bal;
    struct nohh *left;
    struct nohh *right;
} nohh, *noh;

void PrintTree(noh p);
Boolean Insert(noh *p, int x, Boolean *alt);
void RotateLL(noh p, noh p1);
void RotateLR(noh p, noh p1);
void RotateRR(noh p, noh p1);
void RotateRL(noh p, noh p1);

int main(){
    noh p = NULL;
    int x;
    Boolean check = false, *bol = &check;

    printf("int number ('0' to exit): ");
    scanf("%d", &x);

    do{
        check = Insert(&p, x, bol);
        printf("check = %d\n", check);

        printf("int number: ");
        scanf("%d", &x);
    }while(x != 0);

    PrintTree(p);

    return 0;
}

void PrintTree(noh p){
    printf("%d >> bal = %d\n", p->info, p->bal);
    if(p->left != NULL)
        PrintTree(p->left);
    if(p->right != NULL)
        PrintTree(p->right);
}

Boolean Insert(noh *p, int x, Boolean *alt){
    int info;

    if((*p)==NULL){
        *p = malloc(sizeof(nohh));
        (*p)->left = (*p)->right = NULL;
        (*p)->info = x;
        (*p)->bal = zero;
        *alt = true;
        return true;
    } else { /* if p isnt pointing to NULL */
        info = (*p)->info;
        if(x == info)
            return false;
        else if(x < info){ /* follow left */
            Boolean res = Insert(&(*p)->left, x, alt);
            if(!res)
                return false;
            if(*alt){ /* height increase */
                noh p1;
                switch((*p)->bal){
                case plus:
                    (*p)->bal = zero; *alt = false;
                    break;
                case zero:
                    (*p)->bal = minus; 
                    break;
                case minus: /* -1 -1 = -2 => not balanced!! */
                    p1 = (*p)->left;
                    if(p1->bal == minus){
                        /* Rotation LL */
                        RotateLL(*p, p1);
                        *alt = true;
                    } else if(p1->bal == plus){
                        /* Rotation LR */
                        RotateLR(*p, p1);
                        *alt = true;
                    } else {
                        /* Rotation LL */
                        RotateLL(*p, p1);
                        *alt = false;
                    }
                    p1->bal = zero; *alt = false;
                    break;
                }
            }
            return true;
        } else { /* follow right */
            Boolean res = Insert(&(*p)->right, x, alt);
            if(!res)
                return false;
            if(*alt){ /* height increase */
                noh p1;
                switch((*p)->bal){
                case minus:
                    (*p)->bal = zero; *alt = false;
                    break;
                case zero:
                    (*p)->bal = plus; 
                    break;
                case plus: /* 1 +1 = 2 => Not balanced! */
                    p1 = (*p)->right;
                    if(p1->bal == plus){
                        /* Rotation RR */
                        RotateRR(*p, p1);
                        *alt = true;
                    } else if(p1->bal == minus){
                        /* Rotation RL */
                        RotateRL(*p, p1);
                        *alt = true;
                    } else {
                        /* Rotation RR */
                        RotateRR(*p, p1);
                        *alt = false;
                    }
                    p1->bal = zero; *alt = false;
                    break;
                }
            }
            return true;
        }
    }
}

void RotateLL(noh p, noh p1){
    noh p2, aux;

    p2 = p1->left;

    aux = p;
    p = p1;
    p->right = aux;

    aux->left = aux->right = NULL;
    aux->bal = p2->bal = p->bal = zero;
}

void RotateLR(noh p, noh p1){
    noh p2, aux;
    aux = p;
    p2 = p1->right;

    p = p2;
    p2->left = p1;
    p2->right = aux;

    aux->left = aux->right = NULL;
    p1->left = p1->right = NULL;
    aux->bal = p1->bal = p->bal = zero;
}

void RotateRR(noh p, noh p1){
    noh p2, aux;

    p2 = p1->right;

    aux = p;
    p = p1;
    p->left = aux;

    aux->left = aux->right = NULL;
    aux->bal = p2->bal = p->bal = zero;
}

void RotateRL(noh p, noh p1){
    noh p2, aux;
    aux = p;
    p2 = p1->left;

    p = p2;
    p2->right = p1;
    p2->left = aux;

    aux->left = aux->right = NULL;
    p1->left = p1->right = NULL;

    aux->bal = p1->bal = p->bal = zero;
}
4

1 に答える 1

1

RotateLL/LR/RL/RR の実装には欠陥があります — ローテーションに関係するノード間でポインターを正しく調整しますが、ポインターを古いルート ノードに変更しません。これにより、ローテーションが発生したときにノードが失われます。

PrintTree()のループ内にへの呼び出しを挿入すると、何が起こっているかがわかりますmain()。例えば：

int number ('0' to exit): 1
check = 1
1 >> bal = 0
int number: 2
check = 1
1 >> bal = 1
2 >> bal = 0
int number: 3
check = 1
1 >> bal = 0

各 Rotate 関数が新しいルート ノードへのポインタを返すようにし、 でポインタを適切に更新するのがおそらく最も簡単でしょうInsert()。ルート ノードが移動したという事実を反映Insert()するために更新が必要になる状況がいくつかあることに注意してください。*p

于 2014-10-23T01:49:31.903 に答える