c – Problems with AVL Tree Rotations

Question:

Viva, I'm developing code for an AVL tree. But I have problems with rotations.

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

I present my recursive function Insert , which adds the node on the leaves from the tree and when he returns updated their 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:

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 rotações , I'll publish it.

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 you have to take into account certain conditions. If you need help send me email or PM.

Scroll to Top