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.