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

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

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;
}

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?

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

If you add a call to differences after each rotation, that updates the balance factors.

Cheers!

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