3

Viva, Estou a desenvolver código para uma àrvore AVL. Mas tenho problemas nas rotações.

Estrutura do node:

/*Node*/
struct Node{
    int             id;
    int             height;
    char            word[DIM];
    struct Node     *right;
    struct Node     *left;
} typedef node;

void insert(node **root, char *word){
    if(*root == NULL){
        *root = create_node(word);
    }else{
        if(strcmp((*root)->word, word)==0){
            (*root)->id += 1;
        }
        else if(strcmp((*root)->word, word)>0){
            insert(&((*root)->left),word);
            if(balance(&(*root)) == 2){
                printf("%s %s %d\n", (*root)->word, (*root)->left->word, strcmp((*root)->word, (*root)->left->word));
                if(balance(&((*root)->left)) > 0){
                    printf("Rotate Left\n");
                    rotateLeft(&(*root));
                }else{
                    printf("Rotate Left Right\n");
                    rotateLeft(&(*root));
                    rotateRight(&(*root));
                }
            }
        }else{
            insert(&((*root)->right),word);
            if(balance(&(*root)) == -2){
                printf("%s %s %d\n", (*root)->word, (*root)->right->word, strcmp((*root)->word, (*root)->right->word));
                if(balance(&((*root)->right)) > 0){
                    printf("Rotate Right\n");
                    rotateRight(&(*root));
                }else{
                    printf("Rotate Right Left\n");
                    rotateRight(&(*root));
                    rotateLeft(&(*root));
                }
            }
        }
    }
    int a = getHeight((*root)->left);
    int b = getHeight((*root)->right);
    (*root)->height = 1 + max(a, b);
    return;
}

Apresento a minha função recursiva Insert, que adiciona os node nas folhas da àrvore e quando retorna actualiza a sua altura. O problema é nas rotações,

void rotateLeft(node **root){
    node **leftChild = &((*root)->left);
    (*root)->left = (*leftChild)->right;
    (*leftChild)->right = (*root);
}

void rotateRight(node **root){
    node **rightChild = &((*root))->right;
    (*root)->right = (*rightChild)->left;
    (*rightChild)->left = (*root);
}

Obtenho sempre SEG FAULT quando a função tenta fazer uma rotação dupla. Ou seja rotação direita-esquerda e esquerda-direita.

1 Resposta 1

1

Uff, descobri a resposta if(balance(&((*root)->right)) > 0), essa linha estava mal. o correcto seria if(balance(&((*root)->right)) < 0)

Desenvolvi uma versão melhorada do Insert e das rotações, vou publicar.

node *rotate_LL(node *parent) 
{ 
    node *child = parent->left; 
    parent->left = child->right; 
    child->right = parent;
    return child; 
} 

node *rotate_RR(node *parent) 
{ 
    node *child = parent->right; 
    parent->right = child->left; 
    child->left = parent;
    return child; 
} 

node *rotate_RL(node *parent) 
{ 
    node *child = parent->right; 
    parent->right = rotate_LL(child); 
    return rotate_RR(parent); 
} 

node *rotate_LR(node *parent) 
{ 
    node *child = parent->left; 
    parent->left = rotate_RR(child);
    return rotate_LL(parent); 
} 


void insert(node **root, char *word){
    if(*root == NULL){
        *root = create_node(word);
    }else{
        if(strcmp((*root)->word, word)==0){
            (*root)->id += 1;
        }
        else if(strcmp((*root)->word, word)>0){
            insert(&((*root)->left),word);
            if(balance(&(*root)) > 1){
                if(balance(&((*root)->left)) > 0){
                    (*root) = rotate_LL(*root);
                }else{
                    (*root) = rotate_LR(*root);
                }
            }
        }else{
            insert(&((*root)->right),word);
            if(balance(&(*root)) < -1){
                if(balance(&((*root)->right)) < 0){
                     (*root) = rotate_RR(*root);
                }else{
                    (*root) = rotate_RL(*root);
                }
            }
        }
        int a = getHeight((*root)->left);
        int b = getHeight((*root)->right);
        (*root)->height = 1 + max(a, b);
    }
    return;
}

Nota: esta AVL está feita para o meu caso, se você precisar de reutilizar esse código tem que ter em conta certas condições. Se precisar de ajuda me envie email ou PM.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .