Thread: memmory addresses not working out or me screwing somthing up

  1. #76
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    something is off here:
    suppose i have the following numbers

    Code:
    nums[] = {9, 5, 10, 1, 7, 6};
    both the example and avl say it should be a "double rotate right"
    however my code prints out its a double left rotate

  2. #77
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    ok i havent fully tested this yet as my head is beginning to thump and i need t get off the pc and sit quite for a while. But although i still need to make it update the balance factor (im not sure why it isn't) i think i have severely broken the back of the issues

    a new main
    Code:
    #include "bst.h"
    
    void slr(Bin_Node **root); //root is the troubled node
    void srr(Bin_Node **root);
    void dlr(Bin_Node **root);
    void drr(Bin_Node **root);
    
    int main()
    {                   //10,6, 3, 9, 2, 3, 13, 54, 20, 43
        int i, nums[] = {9, 5, 10, 1, 7, 8};
        Bin_Tree *tree;//, *tree_trunk;
    
        tree = create_tree();
        for (i = 0; i < 6; i++)
        {
            insert(tree, nums[i]);
        }
        print(tree);
        destroy(tree);
    
        return 0;
    }
    
    void slr(Bin_Node **root) //single left rotate
    {
        Bin_Node *A = *root;
        Bin_Node *B = A->right;
        Bin_Node *C = B->left;
    
        //perform the rotation
        B->left = A;
        *root = B;
    
        // assigns B's left child to A->right as it must be bigger than A else if C = NULL sets A->right = NULL
        A->right = C;
    
        //call this to update balance factors of the moved nodes.
        balance(&(*root));
    
    }
    
    void srr(Bin_Node **root)
    {
        Bin_Node *A = *root;
        Bin_Node *B = A->left;
        Bin_Node *C = B->right;
    
        //perform the rotation
        B->right = A;
        *root = B;
    
        //Assign B's right child to A->left as it must be smaller than A else if C = NULL sets A->left = NULL
        A->left = C;
    
        //call this to update balance factors of the moved nodes.
        balance(&(*root));
    }
    
    void dlr(Bin_Node **root)
    {
        Bin_Node *A = *root;
        Bin_Node *B = A->right;
        Bin_Node *C = B->left;
        Bin_Node *CL = C->left;
        Bin_Node *CR = C->right;
    
        A->right = CL;
        B->left = CR;
        C->left = A;
        C->right = B;
    
        *root = C;
    
        balance(&(*root));
    }
    
    void drr(Bin_Node **root)
    {
        Bin_Node *A = *root;
        Bin_Node *B = A->left;
        Bin_Node *C = B->right;
        Bin_Node *CL = C->left;
        Bin_Node *CR = C->right;
    
        B->right = CL;
        A->left = CR;
        C->left = B;
        C->right = A;
    
        *root = C;
    
        balance(&(*root));
    }
    
    void balance( Bin_Node **parent )
    {
        int balance = differences( *parent );
    
        if ( balance > 1 )
        {
           //if ( differences( (*parent)->left ) > 0 )
           if ((*parent)->left->balance_factor > 0)
           {
            printf("parent->left is > 0 'single rotate right'\n");
            srr(&(*parent));
           }
           else
           {
            // some rotation here( parent )
            printf("parent->left <= 0 'double rotate right'\n");
            drr(&(*parent));
           }
        }
        else if ( balance < -1 )
        {
           //if ( differences( (*parent)->right ) > 0 )
           if ((*parent)->right->balance_factor > 0)
           {
            printf("parent->right > 0 'double rotate left'\n");
            dlr(&(*parent));
           }
           else
           {
            printf("parent->right <= 0 'single rotate left\n");
            slr(&(*parent));
           }
        }
    }
    
    int differences( Bin_Node *node )
    {
        int lh = countlevels( node->left );
        int rh = countlevels( node->right );
    
        node->balance_factor = lh - rh;
    
        return node->balance_factor;
    }
    
    int countlevels(Bin_Node *node)
    {
        if (!node)
        {
            return 0;
        }
    
        int lh = countlevels( node->left );
        int rh = countlevels( node->right );
    
        return max( lh, rh ) + 1;
    
    }
    
    int max(int x, int y)
    {
        if (x > y)
        {
            return x;
        }
    
        return y;
    }

  3. #78
    Registered User
    Join Date
    May 2019
    Posts
    179
    Congrats, that works!

    I ran one test putting nodes in order, 0 to 250, which makes the worst tree imbalance possible. This balanced the tree exactly. I also ran 250 to 0, 500 random, 0 to 250 + 500 random + 1000 to 750 in one run, all with exact AVL behavior as I can see it.

    Are you calling that done for study, or do you intend to go down the rabbit hole to sort user structures with user supplied comparison functions?

  4. #79
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    did the balance factor work out for you it always printed out the old ones for me. i think thats about as deep as i need to go. i think the next stage is graphs but im not sure i am going to treat myself to an arduino in the very near future so i might start playing with that.

    i think i owe you a few beers for all your help
    coop

  5. #80
    Registered User
    Join Date
    May 2019
    Posts
    179
    If you add a call to differences after each rotation, that updates the balance factors.

    Cheers!

  6. #81
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    with these numbers
    Code:
    nums[] = {9, 5, 10, 1, 7, 8};
    after the double right rotation i get

    Code:
    parent->left <= 0 'double rotate right'
    node data = 1 (0)
    searching left child of 5
    node data = 5 (-1)
    searching left child of 7
    node data = 7 (0)
    node data = 8 (0)
    searching left child of 9
    node data = 9 (2)
    node data = 10 (0)
    searching right child of 9
    searching right child of 7
            .---1
        .---5
    ---7
       |    .---8
        `---9
            `---10
    
    there are 6 nodes in the tree
    
    node deleted
    node deleted
    node deleted
    node deleted
    node deleted
    node deleted
    
    Process returned 0 (0x0)   execution time : 0.001 s
    Press ENTER to continue.
    it still doesnt seem to update the balance factor of each node after the rotation despite putting differences(*root); at the end of every rotate function

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 8
    Last Post: 08-19-2011, 06:53 PM
  2. Working with memory addresses
    By Fujy in forum C++ Programming
    Replies: 7
    Last Post: 01-18-2010, 09:31 AM
  3. Memmory Issues and Threads
    By ddod in forum Windows Programming
    Replies: 2
    Last Post: 08-13-2004, 10:30 AM
  4. Freeing memmory - Automatic?
    By Vber in forum C Programming
    Replies: 4
    Last Post: 04-23-2003, 04:43 AM
  5. Memmory Allocation
    By MethodMan in forum C Programming
    Replies: 4
    Last Post: 04-16-2002, 01:56 PM

Tags for this Thread