AVL left & right rotation

This is a discussion on AVL left & right rotation within the C Programming forums, part of the General Programming Boards category; Hey fellow programmers. I am creating and implementing a left and a right rotation to balance a bst into an ...

  1. #1
    Registered User
    Join Date
    Feb 2013
    Posts
    9

    AVL left & right rotation

    Hey fellow programmers. I am creating and implementing a left and a right rotation to balance a bst into an avl tree. I have made and tried 5 different codes that are commented in the functions left_rotate() and right_rotate() but none have run correctly. Sometimes the program works, sometimes there is a segmentation fault and sometimes not all inserted numbers are shown. Can you guys help me with this?
    avl.c
    Code:
    #include<stdio.h>#include<stdlib.h>
    #include<time.h>
    #include "avl.h"
    
    
    #define N 10
    
    
    void swap(int *a, int *b){
        int temp;
        temp = *a;
        *a = *b;
        *b = temp;
    }
    
    
    main(){
        avl_node *root = NULL;
        int i, a[N];
        
        for(i = 0; i < N; i++){
            a[i] = i+1;
        }
        
        //randomize
        srand(time(NULL));
        for(i = 0; i < N; i++){
            swap(&a[i], &a[rand()%N]);
        }
        
        for(i = 0; i < N; i++){
            insert_value(&root, a[i]);
            view(root, 0);
            printf("--------------Inserted %i--------------\n", a[i]);
            getc(stdin);
        }
    }
    avl.h
    Code:
    #include<string.h>
    #include<stdio.h>
    #include<stdlib.h>
    #include<time.h>
    
    
    #define N 10
    #define BALANCED 0
    #define LEFT_LEANING 1
    #define RIGHT_LEANING 2
    
    
    typedef struct node_tag{
        int x, height;
        struct node_tag *parent;
        struct node_tag *left;
        struct node_tag *right;
    }avl_node;
    
    
    int max(int a, int b){ return(a>b?a:b);}
    
    
    void updateheight(avl_node *temp){
        if(temp!=NULL)
            temp->height = max(temp->left==NULL?-1:temp->left->height,
                       temp->right==NULL?-1:temp->right->height)+1;
    }
    
    
    //implement left rotate right rotate functions
    
    
    void left_rotate(avl_node **temp){
    /*
    avl_node *temp2;
    (*temp)->right=(*temp)->parent;
    (*temp)->parent=temp2->parent;
    temp2->parent=(*temp)->left;
    */
    /*
        avl_node *temp2=malloc(sizeof(avl_node *));
    
    
         temp2 = (*temp)->left;
         (*temp)->left = temp2->right;
         temp2->right = (*temp);
         (*temp) = temp2;
    */ 
    /*     
        avl_node *t = (*temp)->right;
        (*temp)->right = t->left;
        t->left = (*temp);
        (*temp) = t;
    */
    /*
        avl_node *k1;
    k1=(*temp)->left;
    (*temp)->left=k1->right;
    k1->right=(*temp);
    (*temp)=k1;
    */
    /*
    avl_node *t = (*temp);
    (*temp)=t->right;
    t->right = (*temp)->left;
    (*temp)->left = t;
    
    
    updateheight(t);
    updateheight(*temp);
    */
    }
    
    
    void *right_rotate(avl_node **temp){
    /*
    avl_node *temp2;
    (*temp)->left=(*temp)->parent;
    (*temp)->parent=temp2->parent;
    temp2->parent=(*temp)->right;
    */
    /*
        avl_node *temp2=malloc(sizeof(avl_node *));
    
    
         temp2 = (*temp)->right;
         (*temp)->right = temp2->left;
         temp2->left = (*temp);
         (*temp) = temp2;
    */
    /*
     avl_node *t = (*temp)->left;
        (*temp)->left = t->right;
        t->right = (*temp);
        (*temp) = t;
    */
    /* 
        avl_node *k1;
    k1=(*temp)->right;
    (*temp)->right=k1->left;
    k1->left=(*temp);
    (*temp)=k1;
    */
    /*
    avl_node *t = (*temp);
    (*temp)=t->left;
    t->left = (*temp)->right;
    (*temp)->right = t;
    
    
    updateheight(t);
    updateheight(*temp);
    */
    }
    
    
    void insert_fixup(avl_node **rootptr, avl_node *temp){
        int current=BALANCED, previous, lh, rh;
        //call left rotate right rotate functions
        do{
            lh = (temp->left == NULL?-1:temp->left->height);
            rh = (temp->right == NULL?-1:temp->right->height);
            
            previous = current;
            current = (lh==rh?BALANCED:(lh>rh?LEFT_LEANING:RIGHT_LEANING));
            
            if(abs(lh-rh)>1){ //anomaly or violation found!
                if(current==LEFT_LEANING){
                    if(previous==LEFT_LEANING)
                        right_rotate(&temp);
                    else{
                        left_rotate(&(temp->left));
                        right_rotate(&temp);
                    }
                }
                else{
                    if(previous==RIGHT_LEANING)
                        left_rotate(&temp);
                    else{
                        right_rotate(&(temp->right));
                        left_rotate(&temp);
                    }
                }
            }//endif anomaly found
            
            updateheight(temp);
            
            if(temp->parent == NULL) //if root is reached
                *rootptr=temp;     //update root in main
                
            temp=temp->parent; //move up
        }while(temp!=NULL);
    }
    
    
    void insert_node(avl_node **rootptr, avl_node *temp){
    
    
        avl_node *temp2 = (*rootptr);
            avl_node *y = NULL;
            temp->left = NULL;
            temp->right = NULL;
            //temp->x = x;
    
    
            // Add your code here
            while (temp2!=NULL){
                  y=temp2;
                  if (temp->x < temp2->x)
                     temp2= temp2->left;
                  else temp2 = temp2->right;
            }
            temp->parent=y;
            if (y==NULL)
                 (*rootptr)=temp;
            else if (temp->x < y->x)
                 y->left =temp;
            else y->right =temp;
    
    
    }
    
    
    void insert_value(avl_node **rootptr, int x){
        avl_node *temp;
        temp = (avl_node *) malloc(sizeof(avl_node));
        temp->x = x;
        temp->parent = temp->left = temp->right = NULL;
        insert_node(rootptr, temp);
        insert_fixup(rootptr, temp);
    }
    
    
    void view(avl_node *root, int tabs){
        int i;
        if(root != NULL){
            view(root->right, tabs+1);
            for(i = 0; i < tabs; i++) printf("\t");
            
            printf("%2i\n", root->x);
            view(root->left, tabs+1);
        }
    }
    Attached Files Attached Files
    • File Type: h avl.h (3.7 KB, 40 views)
    • File Type: c avl.c (534 Bytes, 26 views)

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Do you have to use parent pointers? It's much easier if you perform insertion recursively and perform rebalancing upon return of recursive calls.

    Obviously using malloc in there is wrong, so you can rule that out.

    Lines 45-48 look right according to my own code, but then you have the hassle of updating parent pointers as well to worry about.

    Why not simplify 130-135 etc to like this:
    Code:
                    if (previous != LEFT_LEANING)
                        left_rotate(&(temp->left));
                    right_rotate(&temp);
    I.e. take advantage of the fact that the last thing in the if and the else branches are the same.

    Where does your debugger say it is crashing?
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C compiler reads from right to left or left to right?
    By ajishgopalr in forum C Programming
    Replies: 12
    Last Post: 07-16-2011, 09:12 PM
  2. Bit rotation...
    By Junior89 in forum C++ Programming
    Replies: 4
    Last Post: 06-10-2007, 04:47 PM
  3. Rotation in 3D?
    By Queatrix in forum C++ Programming
    Replies: 4
    Last Post: 12-24-2006, 05:46 AM
  4. rotation
    By muttski in forum A Brief History of Cprogramming.com
    Replies: 3
    Last Post: 10-10-2002, 04:34 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21