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それぞれ) は基本的にミラーなので、右の回転関数が機能しないというバグがあります。さまざまな呼び出しを試しましたが、現在はforテスト用にループを使用しているだけです。入力を減らすと、すべて正常に動作しますが、関数を呼び出す必要があるとすぐにrotaciona_dir、プログラムがクラッシュします。
IDE/コンパイラについては、Ubuntu 16.04 LTS システムで Code-Blocks IDE 13.12 を使用しています。
また、コードの改善や一般的なプログラミングのヒントも歓迎します。私自身は C プログラマーではありません (Python が私のメイン言語です) ので、これに対する答えは非常に単純かもしれません。