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

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"

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"

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.

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

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

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.

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...

yes the bstlib and bst.h are the same just removed all the superfluous printf's

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):



When 3 is added, this exists



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.

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

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

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