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

  1. #61
    Registered User
    Join Date
    May 2019
    Posts
    209
    At this stage the node need not store a balance factor.

    The balance factor should be a function call returning a number, and you decide how to proceed based on that return.

    I know examples have a balance factor, but you have two issues. One, you're not setting balance factor.

    Second, when height returns zero, you're not going to be working on that side (it is null).

    So, indeed, nothing here discovers that.

    Balance is nothing more than the difference between the left height and the right height.

    Height is nothing more than a traversal of the tree (from the current node into the tree), returning the max depth traversed.

    You can store the result if you like, but the balance factor you store should be the one after balancing. You could do it before, too, but you need the current one when you leave the tree. If you set balance_factor before you rotate, it would be out of date after the rotation. When set, this provides an optimization opportunity, but LEAVE THAT FOR LATER. Get the height working first, and get balance factor first (meaning you'll have a function to get the heights of left and right, calculate the difference - that's the balance).

  2. #62
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    but suppose i had the nodes 10 30 24 22 26 40
    what is the longest route generated and if i did it recursvily in another function it would be right out of wack as i would end up counting numbers twice

  3. #63
    Registered User
    Join Date
    May 2019
    Posts
    209
    @cooper1200

    Another double post thing...glitch.

    Ok, this is the sequence you specified:

    memmory addresses not working out or me screwing somthing up-sequence-jpg

    No rotations were required. That sequence naturally generates a balanced tree.

    This is why I've insisted you change your direction. This kind of thinking is over thinking. You're getting yourself lost.

    No numbers will be counted twice.

    If you inserted 40, it ends up at the tail, to the right of 30.

    Recurse back to 30, get a height. Both are 1. Difference is zero. Balanced.

    Recurse back to 24.

    Left height is 2. right height is 2. Difference is zero. Balanced.

    Look back to step 2. Here, 10, 30 and 24 were entered (step 1's tree). 22 was added.

    At that point, recurse back to 10. Check balance. Left is zero, right is 1, difference is -1, nothing to do (minor imbalance)

    Recurse back up to 24. Left is 2, right is 1. Difference is 1. Nothing to do (minor imbalance)

    These images were generated from screen shots of this site:

    AVL Tree Visualzation

    Height is not about counting nodes or leaves. It's about counting how deep the recursion went. Google for that, or for height of binary tree, not balance.

    I have to head out for a dinner appointment. I'll be back later, but it will be quite late your time zone.
    Last edited by Niccolo; 06-14-2019 at 02:23 PM.

  4. #64
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    ohhhhh i was trying to work the other way round. ie 0 at the top 4 at the bottom most level (assuming a height of 4 of course)

    in your explanation you missed 26 out that might have children so you go down to 26 thats got 27 so you go down 27 your at the bottom so now 26 has height 2 you go back to 30 thats now got height 3 where as it shouldnt have it should have height 2
    Last edited by cooper1200; 06-14-2019 at 04:00 PM.

  5. #65
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    same problem with this
    in main
    Code:
        int x = 0;
    
        if (!node)
        {
            return 1;
        }
    
    
        x += countlevels(node->left);
        x += countlevels(node->right);
    
        return x;
    insert_node
    Code:
    bool insert_node(Bin_Node **root, Bin_Node *node)
    {
        if (!*root) //parent node has no children??
        {
            *root = node;
            (*root)->balance_factor = 0;
            return true;
        }
        else
        {
            //printf("the value of the node = %d the value of nodes root = %d the address of node root = %p\n", node->data, (*root)->data, *root);
            node->height++;
            if ((*root)->data < node->data) //the data of the parent we are looking at is less than the data of the node so go to its right child
            {
               if (insert_node(&(*root)->right, node))
               {
                   (*root)->balance_factor = countlevels(&(*root)->left) - countlevels(&(*root)->right);
                   return true;
               }
            }
            else if ((*root)->data != node->data)
            {
                if (insert_node(&(*root)->left, node))
                {
                    (*root)->balance_factor = countlevels(&(*root)->left) - countlevels(&(*root)->right);
                    return true;
                }
            }
    
        }
        return false; // the node already existed
    }
    try's to access nodes that don't exist
    Last edited by cooper1200; 06-14-2019 at 05:17 PM.

  6. #66
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    this at least ran to the end.
    Code:
    bool insert_node(Bin_Node **root, Bin_Node *node)
    {
        int right = 0, left = 0;
        bool flag = false;
    
        if (!*root) //parent node has no children??
        {
            *root = node;
            (*root)->balance_factor = 0;
            flag  = true;
        }
        else
        {
            //printf("the value of the node = %d the value of nodes root = %d the address of node root = %p\n", node->data, (*root)->data, *root);
            node->height++;
            if ((*root)->data < node->data) //the data of the parent we are looking at is less than the data of the node so go to its right child
            {
               if (insert_node(&(*root)->right, node))
               {
                   left++;
                   flag = true;
               }
            }
            else if ((*root)->data != node->data)
            {
                if (insert_node(&(*root)->left, node))
                {
                    right++;
                    flag = true;
                }
            }
    
        }
        (*root)->balance_factor = left - right;
        return flag; // the node already existed
    }
    but produced
    Code:
    node data = 1 (1)
    node data = 2 (1)
    node data = 3 (0)
    2 out of 3 correct node 1 is wrong (bf is in the brackets) and i suspect the only reason 2 is right is pure chance

  7. #67
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    i was right it just produces all 1's apart from the last node it says 0

  8. #68
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    ok this is weird. i went back to the code in post 65 copied and pasted in the insert_node code so exactly as it was when it was falling over and crying in the corner. went to compile it so its all saved and it threw a warning about implicit deceleration of function count levels so muttering all sorts of things under my breath about what now etc etc.... i added the function prototype to the header file and removed it from main. it then gave warnings about the arguments being passed so removed the & and f me it worked as it should i get the right results. Why the bloody hell it didn't throw out the warnings the first time i don't know. its done this to me before. something missing or extra but it doesn't see the issue then cut and paste it back in and 5000 alarm bells ring.

    all source code below
    header:
    Code:
    #ifndef BST_H_INCLUDED
    #define BST_H_INCLUDED
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <assert.h>
    #include <stdbool.h>
    #include <string.h>
    
    typedef struct Bin_Node
    {
        int data;
        int balance_factor;
        int height;
        struct Bin_Node *left;
        struct Bin_Node *right;
    }Bin_Node;
    
    typedef struct Bin_Tree
    {
        struct Bin_Node *root; //same as head node in a linked list
        int node_count;
    }Bin_Tree;
    
    typedef struct Trunk
    {
        struct Trunk *previous;
        char mystr[20];
    }Trunk;
    
    Bin_Tree *create_tree(void);
    Bin_Tree *initalize_tree(Bin_Tree *tree);
    Bin_Node *create_node(void);
    Bin_Node *initalize_node(Bin_Node *node, int data);
    bool insert_node(Bin_Node **root, Bin_Node *node);
    void print_tree(const Bin_Node *root);
    void destroy_tree(Bin_Node *root);
    void insert(Bin_Tree *tree, int node_data);
    void print(const Bin_Tree *tree);
    void destroy(Bin_Tree *tree);
    int countlevels(Bin_Node *node);
    
    // functions created to use c++ code
    Trunk *create_trunk(void);
    Trunk *initalize_trunk(Trunk *p, char strpassed[]);
    
    // copied from c++ code
    void show_trunks(Trunk *p);
    void print_tree_and_trunk(Bin_Node *root, Trunk *p, bool isleft);
    
    #endif // BST_H_INCLUDED
    bstlib:
    Code:
     #include "bst.h"
    
    Bin_Tree *create_tree(void)
    {
        Bin_Tree *tmp_tree = malloc(sizeof(Bin_Tree));
    
        assert(tmp_tree != NULL);
        tmp_tree = initalize_tree(tmp_tree);
        return tmp_tree;
    }
    
    Bin_Tree *initalize_tree(Bin_Tree *tree)
    {
        tree->node_count = 0;
        tree->root = NULL;
    
        return tree;
    }
    
    Bin_Node *create_node(void)
    {
        return malloc(sizeof(Bin_Node));
    }
    
    Bin_Node *initalize_node(Bin_Node *node, int data)
    {
        node->data = data;
        node->balance_factor = 0;
        node->height = 0;
        node->left = NULL;
        node->right = NULL;
    
        return node;
    }
    
    bool insert_node(Bin_Node **root, Bin_Node *node)
    {
        if (!*root) //parent node has no children??
        {
            *root = node;
            (*root)->balance_factor = 0;
            return true;
        }
        else
        {
            //printf("the value of the node = %d the value of nodes root = %d the address of node root = %p\n", node->data, (*root)->data, *root);
            node->height++;
            if ((*root)->data < node->data) //the data of the parent we are looking at is less than the data of the node so go to its right child
            {
               if (insert_node(&(*root)->right, node))
               {
                   (*root)->balance_factor = countlevels((*root)->left) - countlevels((*root)->right);
                   return true;
               }
            }
            else if ((*root)->data != node->data)
            {
                if (insert_node(&(*root)->left, node))
                {
                    (*root)->balance_factor = countlevels((*root)->left) - countlevels((*root)->right);
                    return true;
                }
            }
    
        }
        return false; // the node already existed
    }
    
    void print_tree(const Bin_Node *root)
    {
        if (!root)
        {
            return;
        }
    
        if (root->left) //parent node has a child to the left
        {
            print_tree(root->left);
            printf("searching left child of %d\n", root->data);
        }
    
        printf("node data = %d (%d)\n", root->data, root->balance_factor);
        //printf("\nnode data = %d node address = %p\n", root->data, root);
        //printf("node left = %p node right = %p\n", root->left, root->right);
    
        if (root->right) //parent node has a child to the right
        {
            print_tree(root->right);
            printf("searching right child of %d\n", root->data);
        }
    }
    
    void destroy_tree(Bin_Node *root)
    {
        if (root) //parent has children
        {
            destroy_tree(root->left);
            destroy_tree(root->right);
            free(root);
            printf("node deleted\n");
        }
    }
    
    void insert(Bin_Tree *tree, int node_data)
    {
        Bin_Node *node;
    
        node = create_node();
        assert(node != NULL);
        node = initalize_node(node, node_data);
    
    
        if (!insert_node(&tree->root, node)) //node already exists
        {
            free(node);
            fprintf(stderr, "value already exists\n");
        }
        else
        {
            if (!tree->root)
            {
                tree->root = node;
                //printf("tree->root = %p\n", tree->root);
            }
            tree->node_count++;
        }
    
    }
    
    void print(const Bin_Tree *tree)
    {
        Bin_Node *root = tree->root;
    
        //printf("address of the root is %p\n", root);
        print_tree(root);
        print_tree_and_trunk(root, NULL, false);
        printf("\nthere are %d nodes in the tree\n\n", tree->node_count);
    }
    
    void destroy(Bin_Tree *tree)
    {
        Bin_Node *root = tree->root;
    
        destroy_tree(root);
        free(tree);
        tree = NULL;
    
    }
    
    // functions created to use c++ code
    Trunk *create_trunk(void)
    {
        return malloc(sizeof(Trunk));
    }
    
    Trunk *initalize_trunk(Trunk *p, char strpassed[])
    {
        Trunk *tmp_trunk = create_trunk();
    
        assert(tmp_trunk != NULL);
        tmp_trunk->previous = p;
        strcpy(tmp_trunk->mystr, strpassed);
        return tmp_trunk;
    }
    
    // functions copied from c++ code
    void show_trunks(Trunk *p)
    {
        if (!p)
        {
            return;
        }
    
        show_trunks(p->previous);
        printf("%s", p->mystr);
    }
    
    void print_tree_and_trunk(Bin_Node *root, Trunk *p, bool isleft)
    {
        if (!root)
        {
            //printf("free memory here?\n");
            //free(p);
            return;
        }
    
        char prev_str[] = "    ";
        Trunk *tmp_trunk = initalize_trunk(p, prev_str); //this line added instead of new Trunk(prev, prev_str);
    
        print_tree_and_trunk(root->left, tmp_trunk, true);
    
        if (!p)
        {
            strcpy(tmp_trunk->mystr, "---");
        }
        else if (isleft)
        {
            strcpy(tmp_trunk->mystr, ".---");
            strcpy(prev_str, "   |");
        }
        else
        {
            strcpy(tmp_trunk->mystr, "`---");
            strcpy(p->mystr, prev_str);
        }
    
        show_trunks(tmp_trunk);
        printf("%d\n", root->data);
        //printf("%d A:%p L:%p R:%p\n", root->data, (void *)root, (void *)root->left, (void *)root->right);
    
        if (p)
        {
            strcpy(p->mystr, prev_str);
        }
    
        strcpy(tmp_trunk->mystr, "   |");
        print_tree_and_trunk(root->right, tmp_trunk, false);
    
        if (tmp_trunk)
        {
            free(tmp_trunk);
        }
    }
    main
    Code:
    #include "bst.h"
    
    void insert_trunk(Bin_Tree *tree);
    void slr(Bin_Node **root, Bin_Node *node); //root is the one pointing at the troubled node, node is the troubled node
    void srr(Bin_Node **root, Bin_Node *node);
    //int countlevels(Bin_Node *node);
    
    int main()
    {                   //10,6, 3, 9, 2, 3, 13, 54, 20, 43
        int i, nums[] = {1, 2, 3};
        Bin_Tree *tree;//, *tree_trunk;
    
        tree = create_tree();
        for (i = 0; i < 3; i++)
        {
            insert(tree, nums[i]);
        }
        print(tree);
        //slr(&tree->root, tree->root);
        //print(tree);
        //srr(&tree->root, tree->root);
        //slr(&tree->root->right, tree->root->right);
        //srr(&tree->root, tree->root);
        //print(tree);
        destroy(tree);
        //tree_trunk = create_tree();
        //insert_trunk(tree_trunk);
        //print(tree_trunk);
        //destroy(tree_trunk);
        assert(tree != NULL);
        //free(tree_trunk);
    
        return 0;
    }
    
    void slr(Bin_Node **root, Bin_Node *node)
    {
        Bin_Node *A = node;
        Bin_Node *B = A->right;
        Bin_Node *C = B->left;
    
        B->left = A;
        *root = B;
    /*
        if (C)
        {
            A->right = C; //if B has a left child set A->right to point to it as it must be larger than A otherwise it would
        }                 //of been on A's left.
        else
        {
            A->right = NULL; //no left child for B so set A->right to null;
        }
    //*/
        A->right = C;
        //assert(A->right != NULL);
    
    }
    
    void srr(Bin_Node **root, Bin_Node *node)
    {
        Bin_Node *A = node;
        Bin_Node *B = A->left;
        Bin_Node *C = B->right;
    
        B->right = A;
        *root = B;
        A->left = C;
    }
    
    void insert_trunk(Bin_Tree *tree)
    {
        Bin_Node *root = tree->root;
    
        root = create_node();
        assert(root != NULL);
        root = initalize_node(root, 1);
        tree->root = root;
    /*
        root->left = create_node();
        assert(root->left != NULL);
        root->left = initalize_node(root->left, 2);
    //*/
        root->right = create_node();
        assert(root->right != NULL);
        root->right = initalize_node(root->right, 3);
    /*
        root->left->left = create_node();
        assert(root->left->left != NULL);
        root->left->left = initalize_node(root->left->left, 4);
        root->left->right = create_node();
        assert(root->left->right != NULL);
        root->left->right = initalize_node(root->left->right, 5);
        root->right->left = create_node();
        assert(root->right->left != NULL);
        root->right->left = initalize_node(root->right->left, 6);
    //*/
        root->right->right = create_node();
        assert(root->right->right != NULL);
        root->right->right = initalize_node(root->right->right, 7);
    //*/
    }
    
    int countlevels(Bin_Node *node)
    {
        int x = 0;
    
        if (!node)
        {
            return 1;
        }
    
    
        x += countlevels(node->left);
        x += countlevels(node->right);
    
        return x;
    }
    coop

  9. #69
    Registered User
    Join Date
    May 2019
    Posts
    209
    @cooper1200

    Hey coop,

    You're having quite a time of it.

    I'm going to have to push you over this hill, because it's going to take you days otherwise.

    Code:
    bool insert_node(Bin_Node **root, Bin_Node *node)
    {
        if (!*root) //parent node has no children??
        {
            *root = node;
            (*root)->balance_factor = 0;
            return true;
        }
        else
        {
            //printf("the value of the node = %d the value of nodes root = %d the address of node root = %p\n", node->data, (*root)->data, *root);
            node->height++;
            if ((*root)->data < node->data) //the data of the parent we are looking at is less than the data of the node so go to its right child
            {
               if (insert_node(&(*root)->right, node))
               {
                   balance( &(*root ) );
                   return true;
               }
            }
            else if ((*root)->data != node->data)
            {
                if (insert_node(&(*root)->left, node))
                {
                    balance( &(*root ) );
                    return true;
                }
            }
     
        }
        return false; // the node already existed
    }
    If you look back at my comments (maybe not, it's quite a scroll), you'll realize I was saying to prepare a balance function here.

    While I'm not opposed to a balance_factor in the Bin_Node (it offers a potential later), you really don't want to stuff more in the node than is required because that overhead is multiplied by every node in the tree. I realize you're doing this for research and debugging purposes, and of course it's not my code, so keep in mind that in a more formal or robust version, balance may appear if it is used for optimization. You're not at that stage yet, so it will serve mainly as a means of display. That makes plenty of sense.

    However, what you have in countlevels....well, read it carefully and think. Then, examine this:

    Code:
    void balance( Bin_Node **parent )
    {
        int balance = differences( *parent );
       
        if ( balance > 1 )
        {
           if ( differences( (*parent)->left ) > 0 )
           {
            //some rotation here( parent )
            //maybe cout << "*************** Rotation 1 << endl;
           }
           else
           {
            // some rotation here( parent )
            //maybe cout << "*************** Rotation 2 << endl;
           }
        }
        else if ( balance < -1 )
        {
           if ( differences( (*parent)->right ) > 0 )
           {
            // some rotation here( parent )
           }
           else
           {
            // some rotation here( 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;
     
    }
    Counting levels is a matter of detemining which is the deepest recursion, left or right, and using that. Not an increment of x as you have it.

    Noting the difference is the balance factor, which I put into the node as it's balance is calculated (upon return).

    This "differences" function I present is not optimized, but it is illustrative. It works.

    Now I come to the whole reason for this. There are 4 rotation options for AVL. It depends on whether balance is >1 or <-1, and THEN which child, left or right, is heaviest.

    There are, here, 4 places for your rotations. That's what I've been driving at.

    You can now create a sequence in your main, as you do now, that is repeatable. It's a nice way to debug/develop this.

    So, at 1,2..there will be no call for rotation in balance.

    When you hit 3, you'll see which rotation that scenario requires. You could set a debug break point if you use a debugger, or you could place cout with some text
    where I have commented "some rotation here", to indicate which of the 4 rotations was called for (and that you've not yet written). When you add a rotation function call for one of the 4 options in the balance function, you can remove that text (you've got that one working, so you don't need a notification).

    When you supply the rotation for the scenario presented by adding 3, and get that working, simply expand your list with random values until another of the 4 rotations is called for that you've not fleshed out.

    You can work the rotations one at a time this way, but get all 4, and know you're complete when these 4 work.

    I don't think the height++ in insert_node works, nor do I think it should remain.
    Last edited by Niccolo; 06-14-2019 at 10:47 PM.

  10. #70
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    sorry to be thick what is max?

  11. #71
    Registered User
    Join Date
    May 2019
    Posts
    209
    @cooper1200,

    It's 5am in my timezone, and the cats woke me up. I refreshed the browser out of habit, but I'm not really awake and I'm going back down for a few hours.

    This was, for some reason, absolutely hilarious to me in that state. Something about thick and max combined just got me giggling.

    max is a function that takes two numbers and returns which is larger. max( 5, 6 ) is 6, max( 3,50 ) is 50.

    I'm not sure why, it may be that you're absolutely not going to give up, or that after some 20 posts of hard won working code you dive right back in to the next brick wall, but I have taken interest in how you're developing.

    Hope it goes well....I'll check in after at least 4 hours and a pot of coffee.

  12. #72
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    i hope your cats dont do what mine does...... if i ignore his slightly polite nudges he decides its a good idea to stick his claw up my nostril and pull HARD

  13. #73
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    @ Niccolo: ok i have added the appropriate functions to the files and removed the level counter that was working in the wrong direction, so another new set im afraid
    header file
    Code:
    #ifndef BST_H_INCLUDED
    #define BST_H_INCLUDED
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <assert.h>
    #include <stdbool.h>
    #include <string.h>
    
    typedef struct Bin_Node
    {
        int data;
        int balance_factor;
        struct Bin_Node *left;
        struct Bin_Node *right;
    }Bin_Node;
    
    typedef struct Bin_Tree
    {
        struct Bin_Node *root; //same as head node in a linked list
        int node_count;
    }Bin_Tree;
    
    typedef struct Trunk
    {
        struct Trunk *previous;
        char mystr[20];
    }Trunk;
    
    Bin_Tree *create_tree(void);
    Bin_Tree *initalize_tree(Bin_Tree *tree);
    Bin_Node *create_node(void);
    Bin_Node *initalize_node(Bin_Node *node, int data);
    bool insert_node(Bin_Node **root, Bin_Node *node);
    void print_tree(const Bin_Node *root);
    void destroy_tree(Bin_Node *root);
    void insert(Bin_Tree *tree, int node_data);
    void print(const Bin_Tree *tree);
    void destroy(Bin_Tree *tree);
    int countlevels(Bin_Node *node);
    int differences( Bin_Node *node );
    void balance( Bin_Node **parent );
    int max(int x, int y);
    
    // functions created to use c++ code
    Trunk *create_trunk(void);
    Trunk *initalize_trunk(Trunk *p, char strpassed[]);
    
    // copied from c++ code
    void show_trunks(Trunk *p);
    void print_tree_and_trunk(Bin_Node *root, Trunk *p, bool isleft);
    
    #endif // BST_H_INCLUDED
    bstlib file
    Code:
     #include "bst.h"
    
    Bin_Tree *create_tree(void)
    {
        Bin_Tree *tmp_tree = malloc(sizeof(Bin_Tree));
    
        assert(tmp_tree != NULL);
        tmp_tree = initalize_tree(tmp_tree);
        return tmp_tree;
    }
    
    Bin_Tree *initalize_tree(Bin_Tree *tree)
    {
        tree->node_count = 0;
        tree->root = NULL;
    
        return tree;
    }
    
    Bin_Node *create_node(void)
    {
        return malloc(sizeof(Bin_Node));
    }
    
    Bin_Node *initalize_node(Bin_Node *node, int data)
    {
        node->data = data;
        node->balance_factor = 0; // does this have to be here as i set the bf to 0 when i add the node????
        node->left = NULL;
        node->right = NULL;
    
        return node;
    }
    
    bool insert_node(Bin_Node **root, Bin_Node *node)
    {
        if (!*root) //parent node has no children??
        {
            *root = node;
            (*root)->balance_factor = 0;
            return true;
        }
        else
        {
            //printf("the value of the node = %d the value of nodes root = %d the address of node root = %p\n", node->data, (*root)->data, *root);
            if ((*root)->data < node->data) //the data of the parent we are looking at is less than the data of the node so go to its right child
            {
               if (insert_node(&(*root)->right, node))
               {
                   balance( &(*root ) );
                   return true;
               }
            }
            else if ((*root)->data != node->data)
            {
                if (insert_node(&(*root)->left, node))
                {
                    balance( &(*root ) );
                    return true;
                }
            }
    
        }
        return false; // the node already existed
    }
    
    void print_tree(const Bin_Node *root)
    {
        if (!root)
        {
            return;
        }
    
        if (root->left) //parent node has a child to the left
        {
            print_tree(root->left);
            printf("searching left child of %d\n", root->data);
        }
    
        printf("node data = %d (%d)\n", root->data, root->balance_factor);
        //printf("\nnode data = %d node address = %p\n", root->data, root);
        //printf("node left = %p node right = %p\n", root->left, root->right);
    
        if (root->right) //parent node has a child to the right
        {
            print_tree(root->right);
            printf("searching right child of %d\n", root->data);
        }
    }
    
    void destroy_tree(Bin_Node *root)
    {
        if (root) //parent has children
        {
            destroy_tree(root->left);
            destroy_tree(root->right);
            free(root);
            printf("node deleted\n");
        }
    }
    
    void insert(Bin_Tree *tree, int node_data)
    {
        Bin_Node *node;
    
        node = create_node();
        assert(node != NULL);
        node = initalize_node(node, node_data);
    
    
        if (!insert_node(&tree->root, node)) //node already exists
        {
            free(node);
            fprintf(stderr, "value already exists\n");
        }
        else
        {
            if (!tree->root)
            {
                tree->root = node;
                //printf("tree->root = %p\n", tree->root);
            }
            tree->node_count++;
        }
    
    }
    
    void print(const Bin_Tree *tree)
    {
        Bin_Node *root = tree->root;
    
        //printf("address of the root is %p\n", root);
        print_tree(root);
        print_tree_and_trunk(root, NULL, false);
        printf("\nthere are %d nodes in the tree\n\n", tree->node_count);
    }
    
    void destroy(Bin_Tree *tree)
    {
        Bin_Node *root = tree->root;
    
        destroy_tree(root);
        free(tree);
        tree = NULL;
    
    }
    
    // functions created to use c++ code
    Trunk *create_trunk(void)
    {
        return malloc(sizeof(Trunk));
    }
    
    Trunk *initalize_trunk(Trunk *p, char strpassed[])
    {
        Trunk *tmp_trunk = create_trunk();
    
        assert(tmp_trunk != NULL);
        tmp_trunk->previous = p;
        strcpy(tmp_trunk->mystr, strpassed);
        return tmp_trunk;
    }
    
    // functions copied from c++ code
    void show_trunks(Trunk *p)
    {
        if (!p)
        {
            return;
        }
    
        show_trunks(p->previous);
        printf("%s", p->mystr);
    }
    
    void print_tree_and_trunk(Bin_Node *root, Trunk *p, bool isleft)
    {
        if (!root)
        {
            //printf("free memory here?\n");
            //free(p);
            return;
        }
    
        char prev_str[] = "    ";
        Trunk *tmp_trunk = initalize_trunk(p, prev_str); //this line added instead of new Trunk(prev, prev_str);
    
        print_tree_and_trunk(root->left, tmp_trunk, true);
    
        if (!p)
        {
            strcpy(tmp_trunk->mystr, "---");
        }
        else if (isleft)
        {
            strcpy(tmp_trunk->mystr, ".---");
            strcpy(prev_str, "   |");
        }
        else
        {
            strcpy(tmp_trunk->mystr, "`---");
            strcpy(p->mystr, prev_str);
        }
    
        show_trunks(tmp_trunk);
        printf("%d\n", root->data);
        //printf("%d A:%p L:%p R:%p\n", root->data, (void *)root, (void *)root->left, (void *)root->right);
    
        if (p)
        {
            strcpy(p->mystr, prev_str);
        }
    
        strcpy(tmp_trunk->mystr, "   |");
        print_tree_and_trunk(root->right, tmp_trunk, false);
    
        if (tmp_trunk)
        {
            free(tmp_trunk);
        }
    }
    lastly main
    Code:
    #include "bst.h"
    
    void insert_trunk(Bin_Tree *tree);
    void slr(Bin_Node **root); //root is the troubled node
    void srr(Bin_Node **root);
    
    int main()
    {                   //10,6, 3, 9, 2, 3, 13, 54, 20, 43
        int i, nums[] = {5, 3, 10, 1, 4, 2};
        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 insert_trunk(Bin_Tree *tree)
    {
        Bin_Node *root = tree->root;
    
        root = create_node();
        assert(root != NULL);
        root = initalize_node(root, 1);
        tree->root = root;
    /*
        root->left = create_node();
        assert(root->left != NULL);
        root->left = initalize_node(root->left, 2);
    //*/
        root->right = create_node();
        assert(root->right != NULL);
        root->right = initalize_node(root->right, 3);
    /*
        root->left->left = create_node();
        assert(root->left->left != NULL);
        root->left->left = initalize_node(root->left->left, 4);
        root->left->right = create_node();
        assert(root->left->right != NULL);
        root->left->right = initalize_node(root->left->right, 5);
        root->right->left = create_node();
        assert(root->right->left != NULL);
        root->right->left = initalize_node(root->right->left, 6);
    //*/
        root->right->right = create_node();
        assert(root->right->right != NULL);
        root->right->right = initalize_node(root->right->right, 7);
    //*/
    }
    
    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\n");
            srr(&(*parent));
           }
           else
           {
            // some rotation here( parent )
            printf("parent->left <= 0\n");
           }
        }
        else if ( balance < -1 )
        {
           //if ( differences( (*parent)->right ) > 0 )
           if ((*parent)->right->balance_factor > 0)
           {
            printf("parent->right > 0\n");
           }
           else
           {
            printf("parent->right <= 0\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;
    }
    as you can see i have added your extra functions to main. Also i have made a max function as it didn't know what max was (is it in a libary somewhere?) the other change is i altered your if statements in the balance function to make use of the data stored in the node rather than recalculate it. i have also altered my slr (single left rotate) and srr (single right rotate) to accept 1 parameter.

    All this seems to work on the whole as in it rotates the nodes and prints the resulting tree which i checked against your link that drew the trees. however it doesn't seem to update the balance factor of the altered nodes.

    many many thanks for all your help
    coop

  14. #74
    Registered User
    Join Date
    May 2019
    Posts
    209
    @cooper1200,

    Well that sounds like good progress. I'm waking up and almost conscious. I'll load the code for a build in a short while.

    In an earlier post I detailed that once balance is called upon to rotate the tree, a RE-call of the diff/height is required to keep the data updated, but in the code examples I posted I was only getting the ball rolling, well...pushed over that hill this had you stuck on.

    I'm surprised that max wasn't already in the library, but I admit I don't know if that's the full standard for C (maybe it requires a spec for C11 in the compiler settings, I don't know). In C++ std::max (and std::min) are part of the standard library, and here the example worked from the standard C libraries you already included, but then I'm on VS.

  15. #75
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    its no issue i just made the function it was easy enough

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