Thread: AVL Tree Insert

    #1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    2
    Rep Power
    0

    AVL Tree Insert


    Hey,
    I have this code for AVL tree insert that works fine!

    Code:
    #include<stdio.h>
    #include<stdlib.h>
    
    typedef struct node
    {
        int *key;
        struct node *left;
        struct node *right;
        int height;
    }node ,*nodeptr;
     int CompareIntegerDefault(int *data1,int * data2)
    {
    	
    	if(*data1>*data2)
    		return (1);
    	else if(*data1==*data2)
    		return (0);
    	else 
    		return (-1);
    }
    // A utility function to get maximum of two integers
    int max1(int a, int b);
     
    // A utility function to get height of the tree
    int height(struct node *N)
    {
        if (N == NULL)
            return 0;
        return N->height;
    }
     
    // A utility function to get maximum of two integers
    int max1(int a, int b)
    {
    	if(a>b)
    		return a;
    	else
    		return b;
       // return (a > b)? a : b;
    }
     
    /* Helper function that allocates a new node with the given key and
        NULL left and right pointers. */
    struct node* newNode(int *key)
    {
        struct node* node = (struct node*)
                            malloc(sizeof(struct node));
        node->key   = key;
        node->left   = NULL;
        node->right  = NULL;
        node->height = 1;  // new node is initially added at leaf
        return(node);
    }
    
    typedef struct ContainerHandle
    {
    	struct node * root;
    	
    }ContainerHandle;
     
    // A utility function to right rotate subtree rooted with y
    // See the diagram given above.
    struct node *rightRotate(struct node *y)
    {
        struct node *x = y->left;
        struct node *T2 = x->right;
     
        // Perform rotation
        x->right = y;
        y->left = T2;
     
        // Update heights
        y->height = max1(height(y->left), height(y->right))+1;
        x->height = max1(height(x->left), height(x->right))+1;
     
        // Return new root
        return x;
    }
     
    // A utility function to left rotate subtree rooted with x
    // See the diagram given above.
    struct node *leftRotate(struct node *x)
    {
        struct node *y = x->right;
        struct node *T2 = y->left;
     
        // Perform rotation
        y->left = x;
        x->right = T2;
     
        //  Update heights
        x->height = max1(height(x->left), height(x->right))+1;
        y->height = max1(height(y->left), height(y->right))+1;
     
        // Return new root
        return y;
    }
     
    // Get Balance factor of node N
    int getBalance(struct node *N)
    {
        if (N == NULL)
            return 0;
        return height(N->left) - height(N->right);
    }
     
    struct node* insert(struct node* node, void *key)
    {
        /* 1.  Perform the normal BST rotation */
        int balance;
    	if (node == NULL)
            return(newNode(key));
     
        if (CompareIntegerDefault(key , node->key)<0)
            node->left  = insert(node->left, key);
        else
            node->right = insert(node->right, key);
     
        /* 2. Update height of this ancestor node */
        node->height = max1(height(node->left), height(node->right)) + 1;
     
        /* 3. Get the balance factor of this ancestor node to check whether
           this node became unbalanced */
        balance = getBalance(node);
     
        // If this node becomes unbalanced, then there are 4 cases
     
        // Left Left Case
        if (balance > 1 && CompareIntegerDefault(key , node->left->key)<0)
            return rightRotate(node);
     
        // Right Right Case
        if (balance < -1 && CompareIntegerDefault(key , node->right->key)>0)
            return leftRotate(node);
     
        // Left Right Case
        if (balance > 1 && CompareIntegerDefault(key , node->left->key)>0)
        {
            node->left =  leftRotate(node->left);
            return rightRotate(node);
        }
     
        // Right Left Case
        if (balance < -1 && CompareIntegerDefault(key , node->right->key)<0)
        {
            node->right = rightRotate(node->right);
            return leftRotate(node);
        }
     
        /* return the (unchanged) node pointer */
        return node;
    }
    
    void preOrder(struct node *root)
    {
        if(root != NULL)
        {
            printf("%d ",*(int *)(root->key));
            preOrder(root->left);
            preOrder(root->right);
        }
    }
    
    int main()
    {
    	ContainerHandle *hdl;
        /* Constructing tree given in the above figure */
    	int a,b,c,d,e,f,g,i,j,k,l,m,n,o,p,q,r,s,t;
        hdl=(ContainerHandle *)malloc(sizeof(ContainerHandle));
      
    	hdl->root=NULL;
    	a=9;
    	hdl->root=insert(hdl->root, &a);
    	b=5;
        hdl->root=insert(hdl->root, &b);
        c=10;
    	hdl->root=insert(hdl->root, &c);
        d=0;
    	hdl->root=insert(hdl->root, &d);
        e=6;
    	hdl->root=insert(hdl->root, &e);
        f=11;
    	hdl->root=insert(hdl->root, &f);
        g=-1;
    	hdl->root=insert(hdl->root, &g);
        i=1;
    	hdl->root=insert(hdl->root, &i);
        j=2;
    	hdl->root=insert(hdl->root, &j);
     
        /* The constructed AVL Tree would be
                9
               /  \
              1    10
            /  \     \
           0    5     11
          /    /  \
         -1   2    6
        */
     
        printf("Pre order traversal of the constructed AVL tree is \n");
        preOrder(hdl->root);
    	
        return 0;
    }
    But, I dont want the insert function to return structure pointer as I'm planning to make it return error codes. So here's what I did.

    Code:
    #include<stdio.h>
    #include<stdlib.h>
    
    typedef struct node
    {
        int *key;
        struct node *left;
        struct node *right;
        int height;
    }node ,*nodeptr;
     int CompareIntegerDefault(int *data1,int * data2)
    {
    	
    	if(*data1>*data2)
    		return (1);
    	else if(*data1==*data2)
    		return (0);
    	else 
    		return (-1);
    }
    // A utility function to get maximum of two integers
    int max1(int a, int b);
     
    // A utility function to get height of the tree
    int height(struct node *N)
    {
        if (N == NULL)
            return 0;
        return N->height;
    }
     
    // A utility function to get maximum of two integers
    int max1(int a, int b)
    {
    	if(a>b)
    		return a;
    	else
    		return b;
       // return (a > b)? a : b;
    }
     
    /* Helper function that allocates a new node with the given key and
        NULL left and right pointers. */
    struct node* newNode(int *key)
    {
        struct node* node = (struct node*)
                            malloc(sizeof(struct node));
        node->key   = key;
        node->left   = NULL;
        node->right  = NULL;
        node->height = 1;  // new node is initially added at leaf
        return(node);
    }
    
    typedef struct ContainerHandle
    {
    	struct node * root;
    	
    }ContainerHandle;
     
    // A utility function to right rotate subtree rooted with y
    // See the diagram given above.
    struct node *rightRotate(struct node *y)
    {
        struct node *x = y->left;
        struct node *T2 = x->right;
     
        // Perform rotation
        x->right = y;
        y->left = T2;
     
        // Update heights
        y->height = max1(height(y->left), height(y->right))+1;
        x->height = max1(height(x->left), height(x->right))+1;
     
        // Return new root
        return x;
    }
     
    // A utility function to left rotate subtree rooted with x
    // See the diagram given above.
    struct node *leftRotate(struct node *x)
    {
        struct node *y = x->right;
        struct node *T2 = y->left;
     
        // Perform rotation
        y->left = x;
        x->right = T2;
     
        //  Update heights
        x->height = max1(height(x->left), height(x->right))+1;
        y->height = max1(height(y->left), height(y->right))+1;
     
        // Return new root
        return y;
    }
     
    // Get Balance factor of node N
    int getBalance(struct node *N)
    {
        if (N == NULL)
            return 0;
        return height(N->left) - height(N->right);
    }
     
    struct node* insert(struct node* node, void *key)
    {
        /* 1.  Perform the normal BST rotation */
        int balance;
    	if (node == NULL)
            return(newNode(key));
     
        if (CompareIntegerDefault(key , node->key)<0)
            node->left  = insert(node->left, key);
        else
            node->right = insert(node->right, key);
     
        /* 2. Update height of this ancestor node */
        node->height = max1(height(node->left), height(node->right)) + 1;
     
        /* 3. Get the balance factor of this ancestor node to check whether
           this node became unbalanced */
        balance = getBalance(node);
     
        // If this node becomes unbalanced, then there are 4 cases
     
        // Left Left Case
        if (balance > 1 && CompareIntegerDefault(key , node->left->key)<0)
            return rightRotate(node);
     
        // Right Right Case
        if (balance < -1 && CompareIntegerDefault(key , node->right->key)>0)
            return leftRotate(node);
     
        // Left Right Case
        if (balance > 1 && CompareIntegerDefault(key , node->left->key)>0)
        {
            node->left =  leftRotate(node->left);
            return rightRotate(node);
        }
     
        // Right Left Case
        if (balance < -1 && CompareIntegerDefault(key , node->right->key)<0)
        {
            node->right = rightRotate(node->right);
            return leftRotate(node);
        }
     
        /* return the (unchanged) node pointer */
        return node;
    }
    
    void preOrder(struct node *root)
    {
        if(root != NULL)
        {
            printf("%d ",*(int *)(root->key));
            preOrder(root->left);
            preOrder(root->right);
        }
    }
    
    int main()
    {
    	ContainerHandle *hdl;
        /* Constructing tree given in the above figure */
    	int a,b,c,d,e,f,g,i,j,k,l,m,n,o,p,q,r,s,t;
        hdl=(ContainerHandle *)malloc(sizeof(ContainerHandle));
      
    	hdl->root=NULL;
    	a=9;
    	hdl->root=insert(hdl->root, &a);
    	b=5;
        hdl->root=insert(hdl->root, &b);
        c=10;
    	hdl->root=insert(hdl->root, &c);
        d=0;
    	hdl->root=insert(hdl->root, &d);
        e=6;
    	hdl->root=insert(hdl->root, &e);
        f=11;
    	hdl->root=insert(hdl->root, &f);
        g=-1;
    	hdl->root=insert(hdl->root, &g);
        i=1;
    	hdl->root=insert(hdl->root, &i);
        j=2;
    	hdl->root=insert(hdl->root, &j);
     
        /* The constructed AVL Tree would be
                9
               /  \
              1    10
            /  \     \
           0    5     11
          /    /  \
         -1   2    6
        */
     
        printf("Pre order traversal of the constructed AVL tree is \n");
        preOrder(hdl->root);
    	
        return 0;
    }
    But it gives me a warning that
    warning C4717: 'insert' : recursive on all control paths, function will cause runtime stack overflow.

    and it doesnt give output also
    Can someone please help me?
    Thanks in advance!
  2. #2
  3. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,392
    Rep Power
    1871
    Yet another selfish cross-poster

    READ THIS
    Particularly sections on choosing forums, and claiming urgency.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper

IMN logo majestic logo threadwatch logo seochat tools logo