Вставка дерева AVL в C - PullRequest
Новая
       33

Вставка дерева AVL в C

0 голосов
/ 05 апреля 2019

Я реализовывал дерево AVL и его операции, такие как вращение.И в конце концов, когда я попытался вставить массив, результат казалсяразные.И кто-нибудь скажи мне, что пошло не так!Спасибо! 

#include <stdio.h>
#include <stdlib.h>
#define LH +1   
#define RH -1   
#define EQ 0
typedef int BOOL;
typedef struct node
{
    int bf;   
    struct node *left;
    struct node *right;
    int val;
}treeNode;  
void L_Rotate(treeNode **T)
{
    treeNode *p = (*T)->right;  
    (*T)->right = p->left;  
    p->left=*T;
    *T=p;
}
void R_Rotate(treeNode **T) 
{
    treeNode *p=(*T)->left;  
    (*T)->left=p->right;   
    p->right=*T;  
    *T=p; 
}
void Left_Balance(treeNode **T)
{
    treeNode *p=(*T)->left;
    treeNode *q;
    switch(p->bf)
    {
        case LH:  
            p->bf=(*T)->bf=EQ;
            R_Rotate(T); 
            break;
        case RH:  
            q = p->right; 
            switch(q->bf)
           {
               case LH: 
                   (*T)->bf=RH;
                   p->bf=EQ;
                   break;
               case EQ: 
                   (*T)->bf=q->bf=EQ;
                   break;
               case RH: 
                   p->bf=LH;
                   (*T)=EQ;
                   break;
           }
            q->bf=EQ;
            L_Rotate(&p);
            R_Rotate(T);
    }
}
void Right_Balance(treeNode **T)
{
    treeNode *p=(*T)->right;
    treeNode *q;
    switch(p->bf)
    {
        case RH:
            (*T)->bf=p->bf=EQ;
            L_Rotate(T);
            break;
        case LH:
            q=p->left;
            switch(q->bf)
           {
               case LH:
                   (*T)->bf=EQ;
                   p->bf=RH;
                   break;
               case RH:
                   (*T)->bf=LH;
                   p->bf=EQ;
                   break;
           }
            q->bf=EQ;
            R_Rotate(&p);
            L_Rotate(T);
    }
}
int insertAVL (treeNode **T,int key, BOOL *taller)
{
    if(!*T)
    {
        *T=malloc(sizeof(treeNode));
        if(!*T) return 0;
        (*T)->left=(*T)->right=NULL;
        (*T)->bf=EQ;
        *taller = 1;
        (*T)->val=key;
    }
    else
    {
        if(key==(*T)->val)
        {
            *taller= 0;
            return 0;
        }
        else if(key<(*T)->val)
        {
            if(!insertAVL(&(*T)->left,key,taller))  return 0;
            if(*taller)
            {
                switch((*T)->bf)
                {
                    case LH:
                        Left_Balance(T);
                        *taller=0;
                        break;
                    case RH:
                        (*T)->bf=EQ;
                        *taller =0;
                        break;
                    case EQ:
                        (*T)->bf=LH;
                        *taller =1;
                        break;
                }
            }
        }
        else
        {
            if(!insertAVL(&(*T)->right,key,taller))  return 0;
            if(*taller)
            {
                switch((*T)->bf)
                {
                    case LH:
                        (*T)->bf=EQ;
                        *taller=0;
                        break;
                    case EQ:
                        (*T)->bf=RH;
                        *taller=1;
                        break;
                    case RH:
                        Right_Balance(T);
                        *taller =0;
                        break;
                }
            }
        }
    }
    return 1;
}
void preOrder(treeNode *T)
{
    if(!T)
    {
        return;
    }
    printf("%d\n",T->val);
    preOrder(T->left);
    preOrder(T->right);
}
int main() {
    int i;
    int a[10]={3,2,1,4,5,6,7,10,9,8};
    treeNode *T=NULL;

    BOOL taller;
    for(i=0;i<10;i++)
    {
        insertAVL(&T,a[i],&taller);
        preOrder(T);
        printf("-------\n");
    }

    return 0;
}

Я прошел дерево после каждой вставки в дерево, результатыпрямо, пока я не вставил 9 в дерево.

Ответы [ 2 ]

1 голос
/ 05 апреля 2019

Когда вы изменяете дерево (или поддерево), вы передаете указатель на указатель заголовка, чтобы изменения отражались в исходной ссылке, либо глобальной заголовке, либо одной из левой / правой ссылок узла.На мой взгляд, это хорошая практика.

Когда вы балансируете дерево, вы делаете то же самое, но есть подводный камень: 

treeNode *p = (*T)->left;

// ... some stuff ...

L_Rotate(&p);
R_Rotate(T);

Здесь, p является локальной копией(*T)->left.В итоге вы модифицируете локальную переменную (которая сразу выйдет из области видимости), но не фактическую ссылку в родительском узле;узел "съеден".

Вы можете либо сделать p a treeNode **, либо, если вы не измените сам указатель, изменить код вращения на: 

L_Rotate(&(*T)->left);
R_Rotate(T);

Аналогично для другого вращения.

0 голосов
/ 05 апреля 2019

Я также заметил, что ваши функции баланса слева / справа не симметричны, а код выравнивания справа пропускает регистр эквалайзера. Я сделал несколько попыток добавить его и переписать Right_Balance, чтобы он был симметричен Left_Balance, но это ничего не решает. Проблема не только в этом.

Если я не ошибаюсь в управлении AVL, вы должны принять во внимание высоту каждой ячейки, чтобы решить, как балансировать после ввода нового значения.

В вашем случае нет высоты , но bf , способной получить 3 значения LH / RH / EQ, таким образом, bf эквивалентно высота в диапазоне от 1 до 3. Но после вставки 10 ячейка, имеющая значение 4, фактически имеет высоту 4, и вы не можете с этим справиться, и для меня вот почему вы не можете после вставки 9 правильно после 10.

...