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

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

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

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

i was right it just produces all 1's apart from the last node it says 0

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

sorry to be thick what is max?

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

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

@ 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

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

its no issue i just made the function it was easy enough