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

  1. #46
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    sorry i was just thinking when i jump out of insert node to do a rotation i would need it so i could point it at the new "root node"

  2. #47
    Registered User
    Join Date
    May 2019
    Posts
    209
    Ok, leaving *** aside a moment (I'll let you expand as long as you like on that).....
    Code:
    .    (3)
    .    /
    .  (2)
    .  / 
    .(1)
    All are node->right's here. (Geez that's hard to format right on these posts - the dots are just to keep things still).


    Ok, &(tree->root) gives us a **p, as in void f( Bin_Node **p )

    So *p is a pointer to Bin_Node 1

    Inside f, *p = (*p)->right, which means Bin_Tree's root now points to node 2

    In order not to lose node 1, I need first to make a Bin_Node *temp = *p

    Because Node 1's right is no longer to point to anything, (it was pointing at 2), temp->right = NULL

    To finish, *p->left = temp

    I think that's done.

    Just got the next cup, I'll review and fix if I'm wrong.
    Last edited by Niccolo; 06-13-2019 at 05:37 PM.

  3. #48
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    sorry i was just thinking when i jump out of insert node to do a rotation i would need it so i could point it at the new "root node"

  4. #49
    Registered User
    Join Date
    May 2019
    Posts
    209
    That double post thing happens to me too, and lately I think the server for the site is under service - it went out last night.

  5. #50
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    i had it earlier it wouldn't let me post something because it thought i had open code tags i had to delete all the code tags and put them back in. im afraid its time for me to hit my pit its 1 am again lol...... thanks for all your help i should be able to make a real stab at this tomorrow
    coop

  6. #51
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,859
    Just as a side note - using assert to test if malloc succeeded is not a good idea.

    If you are using this code later on and NDEBUG is defined, that assert is switched off and you are no longer checking for NULL

  7. #52
    Registered User
    Join Date
    May 2019
    Posts
    209
    Good point @Click_here, I skipped over noticing that.

    @Cooper1200, Click_here's right. It's ok to assert for a debug break, but it isn't a release build concept - it is disabled in release builds via NDEBUG.

  8. #53
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    here is the new 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
    
    int main()
    {                   //10,6, 3, 9, 2, 3, 13, 54, 20, 43
        int i, nums[] = {5, 3, 10, 9, 12, 8};
        Bin_Tree *tree;//, *tree_trunk;
    
        tree = create_tree();
        for (i = 0; i < 6; i++)
        {
            insert(tree, nums[i]);
        }
        print(tree);
        //slr(&tree->root, tree->root);
        slr(&tree->root->right, tree->root->right);
        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 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);
    //*/
    }
    if i have the tree 1->right 2->right 3 using the first call of slr (the commented out one) i get
    Code:
    //rotated
        .---1
    ---2
        `---3
    all correct
    if i call the same function with the numbers in the code i get
    Code:
    //unrotated
        .---3
    ---5
       |        .---8
       |    .---9
        `---10
            `---12
    
    //rotated
            .---3
        .---5
       |   |    .---8
       |    `---9
    ---10
        `---12
    which i think is correct
    however if i now use the slr version on line 18 and comment out the one on line 17. get results that kinda make sense if you work your way through the code but not what i was hoping for i wanted the 5 to stay where it was and the 9 to become its right child.

    am i doing the wrong rotation or is there a flaw in my function or am i passing in the wrong arguments (i did try and pass in tree->root->right->left) but that fails because then A has no right child and causes an exception when i try to set C = B->left as B is null
    coop
    Last edited by cooper1200; 06-14-2019 at 09:08 AM.

  9. #54
    Registered User
    Join Date
    May 2019
    Posts
    209
    Hey @cooper1200,

    I'm back up...nice nap (hey, I'm a 50 something - heavy on the something)...coffee in hand and I have a few hours. Just now looking. This new main fits into the previous source I assume?

    More shortly...sipping...

  10. #55
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    yes the bstlib and bst.h are the same just removed all the superfluous printf's

  11. #56
    Registered User
    Join Date
    May 2019
    Posts
    209
    My first reaction is on at least two main point.

    First, you'll not get anywhere pushing 6 nodes in an unbalanced tree, and THEN rotating nodes as you find them. You'd never get a correct AVL tree in the result, and while you may not be expecting that (I assume you're just stuffing in nodes and practicing rotations), you need to realize that in AVL there are a set number of rotation scenario, and you are very likely to see a layout from this approach that the AVL algorithms would never "see". Put another way, this process of development is going to drive you into the wrong direction.

    Second, the call slr( &tree->root->right, tree->root->right ) will never actually appear in real AVL code. The call is going too deep. Actual rotations will happen from the insertion point downward, then recurse on returns going up toward root with re-checks for balance. This call starts with the assumption that there IS a tree->root->right, and while in this exact circumstance that may well be true, you're already moving in that direction that I can tell from here is going to derail your thinking.

    For the moment I'll leave the exact list of rotations AVL requires to reference (I'll whip that out later if I sense you're getting really lost about that).

    The name slr indicates you're working the "left-right" rotation. AVL has one. If that's not the rotation you're expecting, the name should change to reflect which rotation you're using.

    To avoid derailing your thought/design process, it would be best to us a visualization of AVL that develops to the one rotation you're really focused upon, and that's an entry sequence of 1, 2, 3 in that order (it presents one rotation scenario).

    When 2 is entered, you have this (and I know you've done this, I'm walking through):

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

    When 3 is added, this exists

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

    Now, here's where you must pause in order to re-orient your approach to developing rotation code. You're thinking in terms of the very top down, which has you generating this call

    Code:
    slr( &tree->root, tree->root );
    However, you have no idea at that moment which node has just been added. You're already out of the insert function. No rotations will make sense at this point. You're putting your test(s) in the wrong place.

    I know, you're just evaluating, but your approach is going to derail your thought process as you proceed, and I can see that from here.

    In AVL rotation, which this eventually must become, the balance/rotation code must happen inside insert, just after the RETURN from the recursive insert on a left or right node. To be clear....

    Code:
    bool insert_node(Bin_Node **root, Bin_Node *node)
    {
        if (!*root) //parent node has no children??
        {
            *root = node;
            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, (void *)*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/rotate here
                    balance_rotate_or_whatever_you_call_it( &root );
                    return true;
                   }
            }
            else if ((*root)->data != node->data)
            {
                if ( insert_node(&(*root)->left, node) )
                   {
                    // ********** balance/rotate here
                    balance_rotate_or_whatever_you_call_it( &root );
                    return true;
                   }
            }
        }
        return false; // the node already existed
    }
    Notice there's only one parameter. That's all that's needed. Remember how long it was before you realized you didn't need a parent pointer inside node? This is another one of those moments. Balance/rotate only requires the Bin_Node ** (given as &root) at this point in the recursive algorithm.

    Further, you need to orient your thinking at this point in the recursion, realizing that the rest of the tree going upward will be balance/rotated as required going upwards (one might say backwards out of the recursion), so that rotation will be applied wherever it is required.

    I know you fixated yourself on the notion of getting the rotations first, and I've cautioned against this approach. I caution against this approach again.

    It is at the call to "balance" that you need to know the balance factor, because that is what defines the rotation required. You're driving your process by discovery, that is, you're presenting a scenario, like the 1-2-3 list above, that requires a rotation. It is at this moment that a balance factor would say so, AND AT THE SAME TIME present all other required rotation signals (which direction and how much to rotate).

    Put another way, if at this call I'm showing, you did stop yourself and get the compass out (that compass is the balance calculation), THAT CALCULATION will drive the rotation scenario's you're discovering.

    This means your balance function (not rotation, I'm seriously telling you to change directions or we'll have to send out a search party to find you), will give you 4 rotation scenarios.

    You're on scenario 1 with 1-2-3.

    Get it right. Rotate under experiment. Ignore the other 3 rotation scenarios, that's fine.

    Then, you'll know you only have 3 left to go, and knock them down 1 at a time.

    What I'm saying is that you must pull that slr out of main. Put a balance function where I've indicated as "balance_rotate_or_whatever_you_call_it".

    That function, balance_rotate....., will check the balance factor for which of the 4 rotation scenarios are possible in AVL.

    Then, in balance, is where you call slr - and continue as you are.

    I'm not 100%, but I don't think the 1-2-3 scenario is a lr rotation (shift left-right, no?). I think this is an rr rotation - right has a right, needs shifting to the left.

    Ok, get back to me on these thoughts when you're ready.

  12. #57
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    slr = single rotate left
    i realise that when this is done for real it will only be on a sub tree.

    working the way i am i only have the tree to work with and no recursive levels to work from hence the top down approach and the slr(&tree->right...... stuff they are simply there to pass in the relevant info to the slr function what would be an absoloute nightmare to work out is if doing a double left rotate on a level below the root node and having a missing pointer or loosing a node or pointing at the wrong node which is then compounded by the wrong bf being calculated for the next level which causes some more rotations......... until we are at the top with a tree that looks like a bramble thicket


    the other issue is trying to create a tree that allows me to test the functions thoroughly hence the unrealistic trees

  13. #58
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    ill try and sort the balance factor stuff first ill have to look see if i can find a sensible video that acctually explains it properly

  14. #59
    Registered User
    Join Date
    May 2019
    Posts
    209
    Oh, it's deceptively simple.

    balance is the difference between the height of the left and the height of the right for any node.

    height is hardly more than a simple traversal, returning the max height (or max depth depending on your perspective) found during that traversal.

    You actually already have that code, sort of.

    what would be an absoloute nightmare to work out is if doing a double left rotate on a level below the root node and having a missing pointer or loosing a node
    That's exactly why I'm insistent on you changing direction. It solves that problem. Completely.

    It's why I know your current approach is going to derail your efforts if you don't.
    Last edited by Niccolo; 06-14-2019 at 12:40 PM.

  15. #60
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    ok it has necessitated in a change of the header and bstlib
    Code:
    //bstlib
     #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 = (*root)->left->height - (*root)->right->height; //this line causes a crash
                   return true;
               }
            }
            else if ((*root)->data != node->data)
            {
                if (insert_node(&(*root)->left, node))
                {
                    (*root)->balance_factor = (*root)->left->height - (*root)->right->height;
                    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);
        }
    }
    
    // header file
    #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);
    
    // 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
    this causes a crash on line 52 also when coding it the auto generator refused to give me anything other than (*root)->balance_factor
    im guessing its because the left child doesn't exist

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