Problems with AVL Tree Rotations

Question

Hurrah, I’m developing code for an AVL tree. But I have rotational problems.

Node structure:

/*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;
}

Introducing my recursive function Insert, who adds the node on the leaves of the tree and when it returns update its height. The problem is in the rotations,

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);
}

I always get SEG FAULT when the function tries to do a double rotation. That is right-left and left-right rotation.

Answer 1

Uff, I found the answer if(balance(&((*root)->right)) > 0), that line was wrong. the correct one would be if(balance(&((*root)->right)) < 0)

I developed an improved version of Insert and of rotações, I’m going to publish.

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;
}

Note: this AVL is made for my case, if you need to reuse this code have to take into account certain conditions. If you need help send me email or PM.