AVLツリー回転の問題

Question

私はAVLツリーの実装で非常に奇妙な問題に直面してきました。以下のコードを与えられれば、正しいローテーションなしで実行することができます。なぜなら、私の場合、私はクラッシュしているからです。私はすでにデバッグを試み、ファイルを削除してプロジェクトを作り直して再構築しましたが、これはうまくいきませんでした。

私はブラジル人で、変数名は主にポルトガル語ですが、問題を解決する上で問題があると判明した場合は、変数を変更します名前を英語にする。

avl.hファイル：

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

typedef struct avl{ 
    int elemento; 
    struct avl *esq; 
    struct avl *dir; 
    int altura; 
}avl; 

avl *novo_no(int); 
avl *rotacao_dir(avl *); 
avl *rotacao_esq(avl *); 
avl *insercao_avl(avl *, int); 
int calcula_fb(avl *); 
int max(int, int); 
int get_altura(avl *); 
void in_order(avl *); 

avl.cファイル：

#include "avl_tree.h" 

//creates a new node with the given integer 
avl *novo_no(int elemento){ 
    avl *novo = (avl *)malloc(sizeof(avl)); 
    if(novo){ 
     novo->elemento = elemento; 
     novo->dir = NULL; 
     novo->esq = NULL; 
     novo->altura = 1; 
     return novo; 
    }else 
     exit(1); 
} 

//right rotation 
avl *rotacao_dir(avl *arv){ 

    avl *filho_esq = arv->esq; 
    avl *subarvore_dir = filho_esq->dir; 

    filho_esq->dir = arv; 
    arv->esq = subarvore_dir; 

    //updates the height 

    arv->altura = max(get_altura(arv->esq), get_altura(arv->dir)) + 1; 
    filho_esq->altura = max(get_altura(filho_esq->esq), get_altura(filho_esq->dir)) + 1; 
    //printf("Altura de [%d]: %d\n\n", filho_esq->elemento, filho_esq->altura); //debug print of the node and it's height 

    return filho_esq; 
} 

//left rotation 
avl *rotacao_esq(avl *arv){ 
    avl *filho_dir = arv->dir; 
    avl *subarvore_esq = filho_dir->esq; 

    filho_dir->esq = arv; 
    arv->dir = subarvore_esq; 

    //updates the height 

    arv->altura = max(get_altura(arv->esq), get_altura(arv->dir)) + 1; 
    filho_dir->altura = max(get_altura(filho_dir->esq), get_altura(filho_dir->dir)) + 1; 
    printf("Altura de [%d]: %d", filho_dir->elemento, filho_dir->altura); 

    return filho_dir; 
} 

//insertion 
avl *insercao_avl(avl *arv, int elemento){ 

    /*1. BST normal insertion*/ 

    if(arv == NULL) return novo_no(elemento); 

    avl *aux = arv; 
    if(elemento <= aux->elemento) 
     aux->esq = insercao_avl(aux->esq, elemento); 
    else 
     aux->dir = insercao_avl(aux->dir, elemento); 

    //Inicia os testes para as rotacoes 

    /*2. updates height */ 
    arv->altura = max(get_altura(arv->esq), get_altura(arv->dir)) + 1; 

    /*3. get the balance*/ 
    int fb = calcula_fb(arv); 
    printf("FB do no[%d] = %d\n",arv->elemento, fb); 

    //If unbalanced node, 1 of the 4 following cases will apply: 

    //3.1 esq->esq 
    if (fb > 1 && elemento < arv->esq->elemento) 
     return rotacao_dir(arv); 

    //3.2 dir->dir 
    else if (fb < -1 && elemento > arv->dir->elemento) 
     return rotacao_dir(arv); 

    //3.3 esq->dir 
    else if (fb > 1 && elemento > arv->esq->elemento){ 
     arv->esq = rotacao_dir(arv->esq); 
     return rotacao_dir(arv); 
    } 

    //3.4 dir->esq 
    else if (fb < -1 && elemento < arv->dir->elemento){ 
     arv->dir = rotacao_dir(arv->dir); 
     return rotacao_dir(arv); 
    } 

    /*4. Returns node */ 
    return arv; 
} 

//gets the balancing factor of a node 
int calcula_fb(avl *arv){ 
    if(arv == NULL) return 0; 
    else return(get_altura(arv->esq) - get_altura(arv->dir)); 
} 


//get max between 2 values 
int max(int a, int b){ 
    return((a > b) ? a : b); 
} 

//get a node's height 
int get_altura(avl *arv){ 
    if(arv == NULL) return 0; 
    else return arv->altura; 
} 

// in-order travel of the tree 
void in_order(avl *arv){ 
    if(arv == NULL) // se arvore vazia então finaliza 
     return; 

    in_order(arv->esq); // chamada recursiva para a subarvore esquerda 
    printf("[ %2d ] ", arv->elemento); // visita a raiz 
    in_order(arv->dir); // chamada recursiva para a subarvore direita 
} 

main.cファイル：

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

int main(){ 

    avl *raiz; 
    int i; 
    for(i = 0; i < 10; i++) 
     raiz = insercao_avl(raiz, i); 

    in_order(raiz); 


    return 0; 
} 

あなたが見ることができるように、私の左右の回転機能（それぞれrotaciona_dirとrotaciona_esq ）はbasicaちょっと鏡があったので、正しいものはうまくいかないとバグします。私は別の呼び出しをしようとしていますが、現在は私はちょうどforループを使ってテストしています。入力を減らすと、すべて正常に動作しますが、rotaciona_dir関数を呼び出すとすぐにプログラムがクラッシュします。

IDE /コンパイラに関するノートで

、私はUbuntuの16.04 LTSシステムでは、コードブロックIDE 13.12を使用しています。また

、任意のコードの改善や、一般的なプログラミングのヒントは歓迎されている。私はあまりありませんよCプログラマー自身（Pythonは私の主な言語です）ですので、これに対する答えはとても簡単かもしれません。

Answer 1

私はちょっとだけ自動補完を使ったようです。ケースが呼んでいたrotacao_esq、私の左回転機能、それはコードが誤動作していた。学んだ教訓。この問題を解決済みとしてマークする。 @IanAbbottに感謝してくれたすべての人に感謝します。