Spin Problems AVL Trees

Question

Spin Problems AVL Trees

Navigation

#1 by (1 votes)

3

Live, I am developing code for an AVL tree. But I have problems with the 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 to the leaves of the tree, and when it returns it updates 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.

c

asked by anonymous 16.03.2014 / 21:29

1 answer

Call another page with the action of a form Doubt - SQL Server Query Condition

score 1 · Accepted Answer

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

I've developed an improved version of Insert and rotações , I'll 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 you have to take into account certain conditions. If you need help send me an email or PM.