Thread: AVL Tree Insert

  1. #1
    Registered User
    Join Date
    Aug 2012
    Posts
    24

    AVL Tree Insert

    okay. So I have this code for AVL tree 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 a structure pointer( since I'm planning to make it return error codes.

    so I did this

    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);
    }
     
    void insert(struct node** node, void *key)
    {
        /* 1.  Perform the normal BST rotation */
        int balance;
    	if ((*node) == NULL)
            (*node)=newNode(key);
     
        if (CompareIntegerDefault(key , (*node)->key)<0)
            insert(&((*node)->left), key);
        else
            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)
            (*node)= rightRotate((*node));
     
        // Right Right Case
        if (balance < -1 && CompareIntegerDefault(key , (*node)->right->key)>0)
            (*node)= leftRotate((*node));
     
        // Left Right Case
        if (balance > 1 && CompareIntegerDefault(key , (*node)->left->key)>0)
        {
            (*node)->left =  leftRotate((*node)->left);
            (*node)= rightRotate((*node));
        }
     
        // Right Left Case
        if (balance < -1 && CompareIntegerDefault(key , (*node)->right->key)<0)
        {
            (*node)->right = rightRotate((*node)->right);
            (*node)= leftRotate((*node));
        }
     
        /* return the (unchanged) (*node) pointer */
       
    }
    
    
    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;
    	 insert(&(hdl->root), &a);
    	b=5;
         insert(&(hdl->root), &b);
        c=10;
    	 insert(&(hdl->root), &c);
        d=0;
    	 insert(&(hdl->root), &d);
        e=6;
    	 insert(&(hdl->root), &e);
        f=11;
    	 insert(&(hdl->root), &f);
        g=-1;
    	 insert(&(hdl->root), &g);
        i=1;
    	 insert(&(hdl->root), &i);
        j=2;
    	 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;
    }
    I get a warning:-

    warning C4717: 'insert' : recursive on all control paths, function will cause runtime stack overflow.
    I can't figure out why this doesn't work!!
    Can someone please help me understand!
    Thanks in advance!
    Last edited by sakura; 12-07-2012 at 12:49 AM.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > if (balance > 1 && max1(*key , *((*node)->left->key))<0)
    max1 doesn't return <0 or >0 or anything like that.
    It's just the larger of the two numbers, not the comparison of the two numbers.

    You also make use of max() as well.
    Perhaps you need to clean up the code by giving one of them a much better name.

    > struct node* insert(struct node** node, int *key)
    Make this
    void insert(struct node** node, int *key)
    since you never actually return a node, nor do you ever assign the result (even if it did).
    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.

  3. #3
    Registered User
    Join Date
    Aug 2012
    Posts
    24
    Okay the code was messed up, but has been editted now. Problem persists. Please help me out!!!

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > warning C4717: 'insert' : recursive on all control paths, function will cause runtime stack overflow.
    > I can't figure out why this doesn't work!!
    Do you know what the word "all" means?

    Can you see that calling insert() ALWAYS calls insert(), so you have recursion without end?

    Perhaps something like this
    Code:
        if ((*node) == NULL) {
            (*node)=newNode(key);
        } else if (CompareIntegerDefault(key , (*node)->key)<0) {
            insert(&((*node)->left), key);
        } else {
            insert(&((*node)->right), key);
        }
    where the simple case does NOT call insert recursively.
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Tree Insert
    By Fatima Rizwan in forum C++ Programming
    Replies: 6
    Last Post: 05-27-2010, 01:33 AM
  2. Binary Search Tree Insert
    By bleuz in forum C++ Programming
    Replies: 5
    Last Post: 04-30-2010, 09:53 AM
  3. insert into binary tree question..
    By transgalactic2 in forum C Programming
    Replies: 32
    Last Post: 11-18-2008, 03:21 PM
  4. Insert elements in binary tree
    By lastrial in forum C Programming
    Replies: 3
    Last Post: 05-23-2007, 10:22 AM
  5. Binary Tree Insert & Find
    By Micko in forum C++ Programming
    Replies: 4
    Last Post: 04-11-2004, 01:18 PM