memmory addresses not working out or me screwing somthing up

i have broken my code down a little so it is more manageable
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;
    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

---

i have added some printf statements in the print tree function to get the address of the node and its children's address's lines 69 and 70 of the following code

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->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;
        return true;
    }
    else
    {
        //printf("the value of nodes root = %d the address of node root = %p\n",(*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
        {
            return insert_node(&(*root)->right, node);
        }
        else if ((*root)->data != node->data)
        {
            return insert_node(&(*root)->left, node);
        }
    }
    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("\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 deleated\n");
    }
}

void insert(Bin_Tree *tree, int node_data)
{
    Bin_Node *root = tree->root, *node;

    node = create_node();
    assert(node != NULL);
    node = initalize_node(node, node_data);


    if (!insert_node(&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;

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

// 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);

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

---

and lastly main

Code:

---

#include "bst.h"

void insert_trunk(Bin_Tree *tree);

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);
    destroy(tree);
    //tree_trunk = create_tree();
    //insert_trunk(tree_trunk);
    //print(tree_trunk);
    //destroy(tree_trunk);
    free(tree);
    //free(tree_trunk);

    return 0;
}

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 run this i get the following out put

Code:

---


node data = 1 node address = 0x7ffc6249a268
node left = (nil) node right = 0x5630434472a0

node data = 2 node address = 0x7ffc6249a248
node left = (nil) node right = 0x5630434472c0

node data = 3 node address = 0x7ffc6249a228
node left = (nil) node right = (nil)
searching right child of 2
searching right child of 1
---1
    `---2
        `---3

there are 3 nodes in the tree

node deleated
node deleated
node deleated

Process returned 0 (0x0)  execution time : 0.001 s
Press ENTER to continue.

---

the output doesn't make any sense to me as the tree is obviously connected together yet the address's (if i have got them correctly ) are different to the left/right pointers of the node above. ie suppose the node with the data of 2 right pointer points to x then the address of the node with the data of 3 should be x
coop

> printf("\nnode data = %d node address = %p\n", root->data, &root);
Remove the & from the last parameter.

thank you. i read in the book the other day that anyone who understand pointers loves c anyone who doesn't understand pointers hates c and is wasting their time. i just cant seem to get my head around when to use which version. I had this issue in my maths a level. there were a couple of things i just couldn't grasp we spent ages on them and no matter what i tried i always came up with the wrong answer. in the end we had to leave it and just hope it didn't come up in the exam

im confusing myself now i have changed 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->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;
        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
        {
            return insert_node(&(*root)->right, node);
        }
        else if ((*root)->data != node->data)
        {
            return insert_node(&(*root)->left, node);
        }
    }
    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("\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 deleated\n");
    }
}

void insert(Bin_Tree *tree, int node_data)
{
    Bin_Node *root = tree->root, *node;

    node = create_node();
    assert(node != NULL);
    node = initalize_node(node, node_data);


    if (!insert_node(&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);
}

// 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);

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

---

i have un-commented line 43 and added in the value of the node to be added into the tree and un-commented line 109.

i get the following output

Code:

---

tree->root = 0x564a9c6d2280
the value of the node = 2 the value of nodes root = 1 the address of node root = 0x564a9c6d2280
the value of the node = 3 the value of nodes root = 1 the address of node root = 0x564a9c6d2280
the value of the node = 3 the value of nodes root = 2 the address of node root = 0x564a9c6d26b0
address of the root is 0x564a9c6d2280

node data = 1 node address = 0x564a9c6d2280
node left = (nil) node right = 0x564a9c6d26b0

node data = 2 node address = 0x564a9c6d26b0
node left = (nil) node right = 0x564a9c6d26d0

node data = 3 node address = 0x564a9c6d26d0
node left = (nil) node right = (nil)
searching right child of 2
searching right child of 1
---1
    `---2
        `---3

there are 3 nodes in the tree

node deleated
node deleated
node deleated

Process returned 0 (0x0)  execution time : 0.001 s
Press ENTER to continue.

---

what i am trying to achieve with all these printf's is where i can put a line of code to update another member in the node struct so it knows what its parent is so when i come to do rotations i don't loose where i am.
coop

@cooper1200,

Working backwards (most recent post)....

I'm not 100% sure what the question is here, at least specifically....as in what is confusing?

Since we're on different compilers we may have slightly different results to expect, but there's a details about %p in printf formatting you should attend. They should be cast to a void *, because of the way the compiler pushes the arguments on the stack. For example, you may be pushing a Bin_Node *, but printf doesn't have a clue what a Bin_Node is.

Now, I get the same results with or without these casts, but technically the behavior is "undefined" if the type being pushed isn't a void *.

I'm guessing, but maybe you're confused by the fact the printout declares root "moved"?

That's normal, because during recursion, each recursion thinks of the "root" as a descendent, not "The" root of the entire tree.

Actually, where you mention concern for where the parent is, usually the algorithms of a tree structure track the parent by the recursion itself. Is it clear in your mind that each recursive call has it's own memory of the state of things? Is it clear that's due to the stack?

I'm not sure what you're specifically confused about though, so let's discuss.

As to pointers being tough to "get", that's rather common.

I think the situation you fixed recently was the confusion as to when to provide the address of the pointer, or the pointer.

This is understandable, but with practice and experience it becomes more familiar.

Since that can wind through all tributaries, I'll ask that you pose specific inquiries on the subject.

C, being an assembler (historically), does work with pointers frequently, so familiarity is essential for your own comfort. A dedicated exercise may be in order, perhaps at another time unless you find it gets in the way here.

Factually, the subject is nearly identical to that of assembly programming, in that you have the same basic confusing notions, but it is worse only in that the assembly language(s) have little to give you any hint, where C has a little.

im confused because i don't seem to get the right results tree root points to the first node.... so node 1's parent should be the tree root node two's parent should be node 1 and node three's parent should be node 2 but i dont think i am getting that

im also wondering that if the addresses are correct if i can replace the printf's with node->parent (when it exists) = *root

@cooper1200,

The printout is confusing because of where the printf's are reporting. You're getting "in process" information that may confuse.

I tried this, see if you like the (crowded) result:

In print_tree_and_trunk, where the printf prints the data of the node, I added:

Code:

---

    printf("%d A:%p L:%p R:%p\n", root->data, (void *)root, (void *)root->left, (void *)root->right);

---

Which shows in the tree diagram what the node addresses are.

To be clear, AVL should not require the node holds the parent.

Are you choosing to do that just for display?

It would pose an uneccesary burden on the algorithm, and could confuse your efforts to maintain "parent" correctly during rotations.

i need to find away of assigning the parent node to the child's nodes parent pointer. the tree at the moment is unbalanced i need to do a left rotate and to do that i need to know which node is parent of which node so i dont loos track of them (i think)

No, you don't.

Seriously, unless you just want to have the parent for your own purpose, I promise you (and I've had my coffee, reviewed the material, I'm clear on this) the parent member of the node will only serve to confuse and confound.

Don't do it because you think it is the way the AVL algorithm should be implemented. It isn't.

The rotations happen from the parent's perspective, which is defined by the point of the recursion where it is performed.

Did you "get" my questions on what the stack is? Are you clear on what the stack is and how it works with recursion?

ok it looks like i am getting the parent node address or at least the results from your line match the results from mine.. trouble is with this is every time i run it i get slightly differing addresses so its hard to visualize and confirm my findings

@cooper1200,

Quote:

---

Originally Posted by cooper1200

ok it looks like i am getting the parent node address or at least the results from your line match the results from mine.. trouble is with this is every time i run it i get slightly differing addresses so its hard to visualize and confirm my findings

---

HAHA....well, yes, you will (get different addresses from one run to another).

Everything will be relative - it's tough to make that stick from run to run.

Ok, so is the stack firm and clear in your mind?

i think the stack is last in first out and you can only work at the top level, this imaginary block is like a magazine in a rifle you can only load it from the top 1 round at a time and you can only empty it 1 round at a time. when you remove a round the ones below it are pushed up one slot (sorry for the mixed metaphore)

my understanding of recurstion is at the point of calling its self the value computed is put on the stack and so on untill it reaches its conclustion then it pops each value off the stack as it unwinds. for example

Code:

---

int myrecurse(int x)
{
    if (x == 3)
    {
        return x;
    }
    return x + myrecurse(x + 1)
}

---

if i send x = 1 into the function
x=1 gets put on the stack x now = 2
x=2 gets put on the stack x now = 3
x = 3 so return 3
get the 2 off the stack and add three to it x=5
get the 1 off the stack and add the 1 to x so x = 6
return 6

@cooper1200,

That's fairly good. I tend to think of it as a stack of cards. You deal out, say, 5 cards, one atop the other face up. The top card is current. It is popped by tossing it away, revealing the card underneath.

Last in First out...LIFO. Like a stack of cards.


...but I want to expand on the subject a little.

The stack is implemented in modern CPUs (we'll assume Intel for now) with a devoted register. It points to the memory allocated at launch for the stack.

Every function call involves the stack. This is the part I want to be clear about. It is not just the data involved.

When a function call is made the most important thing that happens is that the address of the program machine code is pushed onto the stack. This is how the computer knows where to return when the call is completed.

In theory, the parameters going into the function are pushed on the stack. Technically, the optimizer may fiddle with this, but in theory they go on the stack as part of calling the function.

When the function is entered, all locally allocated data is placed on the stack. This is key because it is how recursion works in your example. You could say each recursion (or each function call) naturally creates a structure of data involving everything from the return address to the parameters to the local data allocated inside the function.

This is how AVL "knows" the parent. It happens to be the parameter pushed onto the stack to make the function call. You got that part correctly.

In AVL, the parent rotates the children. When I saw you thought you needed the node to "know" the parent, it seemed to me that you were thinking the children rotate themselves.

It is the stack that remembers the structure of the tree during insertion/deletion/search/traversal.

Is is also how AVL rotates.

I'll be interested as you get to the point of introducing balance, and your plan to do it. There's quite a bit I can see that needs attention in the existing code to facilitate it.

Does your debugger have a call stack view? It can be helpful for the development phase you're entering.

i was just working on the rotating functions for the moment. but i was thinking of having three more members in the node left height , right height and balance factor of the node (left height - right height) that can then be checked for the range -1 to 1. calculating the height of the parent of those node(s) can be calculated (i think) by adding the left height of each node together + 1 same for the right. i think the height of each node can be done recursively a little like my example above.

further on rotation in the example on my other post i needed to rotate the 20 to the left. so the 15 right pointer has to point at the 30 so i need someway of accessing the 15 to set its right pointer to 30.

if 20 stored its parent pointer it is then "just" a case of making it point to the 30.
here is what i am basing my theory on
YouTube 4,00 is where it starts

Do you want to design the algorithm from description, or do you want a booster from example?

AVL only requires one member, a balance (integer usually).

@cooper1200,

I understand your point about 15 pointing to 30, but you don't need a way to access the 15. The rotation will be conducted from the recursion point where the 15 is current, not the 20. There's no need for the nodes to know the parents, because you're conducting the work while 15 "is in hand"

Factually, the balancer works from the level of the insertion upwards, AT EACH LEVEL of the tree.

You get back to 15 at the end (since it's the root of the tree) for the final balance sequence.

Balance is recursive, too.

I hesitate to post any code examples, you seem to want to feel this out yourself, but let me know if you need more of a push over the hump.

Further hint....some algorithms use a design where there's no additional data in the nodes, it studies the tree each time (which is slower but takes less space).

Also, I watched the video, and their use of the parent node is going to be more trouble to you than you want to invite.

i want to have a crack at it first if you don't mind thanks. i look for videos for ideas on how to solve an issue and to understand what the issue is. then i try to write a solution.

the issue i cant get my head around is how i can join the rotated nodes back onto the tree.

lets pick print tree.on my way through the left hand side continually passing in node->left which becomes *root until its a node with no children.

so i am thinking by slightly altering the paramteters of insert node i can "save" the parent node or keep the function parameters the same and then declare a pointer "parent" and make that point at the right nodeby use of a parent member in the node struct

this is what i was asking earlier on. what nodes do i need to know.

also if the call for rotate 20 left is done from 15 how does 15 know the balance factor of twenty

ie how can it be done with a node only knowing about itself.

Before you get to that point, though, do you have a plan on determining the balance?

That's how the algorithm knows what to rotate. Is that already clear?

Well, 15 knows 20...it has a pointer to it, so it can inquire (even if it has to descend)

im not worrying about the balance factor right now. as said that can be achived by adding up the left and right heights from the children i think. or i think i saw a video somewhere of doing it recursivly it started off with x at 1 for the current node and for every node it found on the left it added 1 to x and for every node on the right it subtracted 1 from x the really hard part i can see me loosing the plot over is the rotation trying to make each nodes pointers point at the right node and not loose any nodes. and not screwing up * ** and &

Ok, I'll leave balance factor / height alone for now.

I'm holding back, but asking questions to push you toward the right track here.

Do you want to go over * ** and &? Or just take those as they come to you (and stop worrying about them, whatever gets screwed up gets fixed :) )


Let me put it this way. A rotation, say a left rotation, is about 4 or 5 lines of code.

my plan is to start of with three nodes to the right. set some variable to 1st 2nd and 3rd nodes and see if i can make it do what i want. then the next stage is to add a node to the root nodes left and try rotate to the left. each time adding nodes till i end up with 5 or 6 nodes with the node being moved to the left is somewhere in the middle. then once i have mastered that do it all with right rotation. then see if i can call the same function twice for double left... if not sit and work out that from the beginning. to do all this weather the tree is balanced or not is unimportant at this stage its just about getting the rotation functions correct

then once all that is working i can start work on the actual balancing factors and only have to plug in the appropriate function

let me go and draw a diagram and some psudo code to what i think should be happening

Quote:

---

I'm holding back, but asking questions to push you toward the right track here.

---

So, in that direction, I'd have to wonder if you have the direction out of order, but like I said, I'll leave balance alone for now.

Let me give this hint, though. Take a look at insert_node.

Let's say you read the recursive call to "insert_node( &(*root)->right, node );" - that's when a right node was inserted.

Instead of returning right then, check that insert returned true and if so, call balance ON ROOT ( not root->right ).

Balance (I know, you want to avoid balance for now)....it's what rotates. You'll assume to start that you're doing a right rotation.

Later, balance will incorporate the balance value, but for now you'll call for a right rotation.

Balance, and rotate, only need one parameter - the root from the caller (as a **).

The right rotation is performed on the root, and it performs a simple operation on a few of the right/left pointers

ok heres the drawing Attachment 15785
we start off with a tree A and attach node 2's left pointer to 1. ie root->right->left = root fig B
then we make the tree root point to node 2 fig c
then we set node 1's right pointer to null fig d
if node two had a left child as well rather than setting node 1's right to null i would point it at the left child of 2

what i am struggeling to grasp is how we get the 2nd stage ie get tr to point to 2

@cooper1200,

There is no spoon (from "The Matrix").

In other words, there is no tr. I know, you have one, it's Bin_Tree, but look at your insert_node. It takes a Bin_Node **. Inside insert_node, there is no tr, no Bin_Tree.

You don't need it.

Bin_Tree has a root, I know.

When you call insert_node, you call that from insert (where you do have Bin_Tree). But look at that call.

Code:

---

insert_node( &root, node );

---

Actually, that's a mistake. It shouldn't be the temporary Bin_Node *root;

That call should be

Code:

---

insert_node( &( tree->root ), node );

---

I had not noticed that before. Actually, I recall mentioning it, but never mind...it should be changed to the tree->root, not root.

Now, look at the insert_node signature:

Code:

---

bool insert_node( Bin_Node ** root, Bin_Node *node )....

---

root is a pointer to a pointer, which is modified with something like

*root = node;

Or whatever context is appropriate. That will assign Bin_Tree's node. Insert_Node has (or will have when you fix that as I pointed out) Bin_Tree's root.

Via pointer to a pointer (the **)

I thought I'd go over *, ** and &* a bit.

A pointer

Code:

---

    int *p
p = malloc( sizeof( int ) );

---

To assign an integer to this pointer I must use:

Code:

---

*p = 5;

---

That's because 5 is an integer, while p is a pointer to an integer. To copy 5 into what's stored at p it must be de-referenced with *

Let's say I have another,

Code:

---

int * i;

---

Since i is a pointer, I can write

Code:

---

i = p;

---

Now, i and p point to the same integer.

However, if instead I wrote

Code:

---

*i = *p

---

I'd have a crash. That's because i was uninitialized, but this code copies what's stored at p into what's store at i, but i doesn't have storage - I didn't call malloc for it. If I had called malloc, this would work and I'd have two integers pointed to by i and p, both with the same value given to p earlier.

Now, let's say I have a function

Code:

---

void f( int ** x ) { *(*x) = 6; }

---

Why the *(*x)?

x is a pointer to a pointer. *x is "what's stored at x", the de-referenced pointer to a pointer. The type of what's stored at x is a pointer to an integer. To store an integer there I must de-reference again.

To call it, I must provide a **, a pointer to a pointer to an integer.

Code:

---

f( &i );

---

or

Code:

---

f( &p );

---

That function is taking the address of the pointer i (or p). The address of a pointer is a pointer to a pointer, or **.

Now, I have another function,

Code:

---

void f2( int ** x, int *n ) { *x = n; }

---

I could call it with

Code:

---

f2( &i, p );

---

Notice that in f2 only *x is required. That is because n is a pointer to an int, not an int. This is the situation you most commonly face in your code.

When f2 returns, the pointer i will be changed. f2 essentially duplicates i = p above. Note: Not ( *i = *p )

That is like what happens to (&(tree->root)) or ( &((*root)->right ) )

changed that....

at some point in the rotation i am going to have to set what ever is pointing at 1 to point to 2 the node that is being inserted doesn't know what its parent is just like 1 doesn't know what its parent is. every thing has to be done from the node that is moving to the left as its that one thats balance factor is off.

this is why im trying to deal with this in small chunks otherwise i have to worry about calculating the balance factor calculating the height of each node calculating what type of rotation work out what node im looking at weather the one below it has a left child and make sure i don't screw up the pointers. (my head just went pop thinking about what i would have to do)

The problem is in your phrase:

Quote:

---

the node that is being inserted doesn't know

---

It doesn't have to.

The recursive call knows what it's parent is. The node doesn't need to know.

That's the point of the ** as I mention above.

im not getting this. why is i changed it was set to p

Which part?

Oh, I see.....yes, if all of the snippets were thought to be one body of code, sure.....but whatever p may be, i will be changed to it by f2, same as i = p would do.

I supposed I should have suggested that p might have changed in the meantime, and i is updated to p through f2, same as i = p would do.

tree is empty
i send in node 1
it returns

were not done yet as i kept finding out
i then have to set tree->root to node 1

i send in node 2
it finds node one and goes to node 1's right and sends in node 1's address
inserts 2 by *root = node
returns
i send node three in
it finds node 1 and goes to node 1's right and sends in node 1's address
it finds node 2 and goes to node 2's right and sends in node 2's address
inserts 3 by *root = node
returns

each time i have sent in the address of the parent node.... r more precisely i have sent in the address of where the parent nodes right pointer is

Let me be a little more obvious. Let's say I have

Code:

---

Bin_Tree *tr = create_tree();

---

I then call

Code:

---

set_root( &(tr->root), node );

---

Code:

---

void set_root( Bin_Node **root, Bin_Node *n )
{
  *root =n->left;
}

---

tr's root was changed to n's left node.

like you did with your function you sent in a pointer to a pointer and then changed the value it pointed at... ie in the case of the tree it was pointing at null but once we get to the point of insertion it gets set to point to the node

If I follow you, yes, that's it.

were typing at the same time here lol

so following that train of thought to set the tree root to point to two i have to know what was pointing at 1

Yes, and you will because at the entrance to the function you'll have the ** representing tree->root. It will be 1, and when you rotate that will modify tree->root, though it will only know it as a Bin_Node **

The point there is that later, when you have a larger tree, your rotation may be anywhere in the tree, much lower, not affecting tree->root. The function will work the same, though, as the parameter will be passed as &((*root)->left) or &((*root)->right) in the recursive calls of insert_node

In other words, at each level of the tree, descending, the subtree is not special, it looks like any tree (just smaller and smaller the more you descend), and should function the same at all levels, whether the source was Bin_Tree's root, or a deeply seated Bin_Node's left or right.

oh wait i think the penny has dropped (yes there was a loud echoing clang) i am rotating node to the left.... so **root is whats pointing at node
in other words 1 is node node->left is 2 and node->left->left is 3
so to make what ever is pointing at node 1 i would make *root point at 2

you beat me to it lol

In yet another way to say it, &(tree->root) looks like a parent inside insert_node, and &((*root)->left) makes that Bin_Node's left look like a parent inside insert_node

ok to take your examples further....

Code:

---

f1( **p) { f2(&(*p))??
f2 (**p) or (***p)

---

*** is gettin' a little nuts :D


I'm going to have to think about f2 or ***p over another cup of coffee....the earlier ones are all used 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"

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.

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.

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

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

Attachment 15786

When 3 is added, this exists

Attachment 15787

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

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.

Quote:

---

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.

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

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

@cooper1200

Another double post thing...glitch.

Ok, this is the sequence you specified:

Attachment 15788

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.

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

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

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

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

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

something is off here:
suppose i have the following numbers

Code:

---

nums[] = {9, 5, 10, 1, 7, 6};

---

both the example and avl say it should be a "double rotate right"
however my code prints out its a double left rotate

ok i havent fully tested this yet as my head is beginning to thump and i need t get off the pc and sit quite for a while. But although i still need to make it update the balance factor (im not sure why it isn't) i think i have severely broken the back of the issues

a new main

Code:

---

#include "bst.h"

void slr(Bin_Node **root); //root is the troubled node
void srr(Bin_Node **root);
void dlr(Bin_Node **root);
void drr(Bin_Node **root);

int main()
{                  //10,6, 3, 9, 2, 3, 13, 54, 20, 43
    int i, nums[] = {9, 5, 10, 1, 7, 8};
    Bin_Tree *tree;//, *tree_trunk;

    tree = create_tree();
    for (i = 0; i < 6; i++)
    {
        insert(tree, nums[i]);
    }
    print(tree);
    destroy(tree);

    return 0;
}

void slr(Bin_Node **root) //single left rotate
{
    Bin_Node *A = *root;
    Bin_Node *B = A->right;
    Bin_Node *C = B->left;

    //perform the rotation
    B->left = A;
    *root = B;

    // assigns B's left child to A->right as it must be bigger than A else if C = NULL sets A->right = NULL
    A->right = C;

    //call this to update balance factors of the moved nodes.
    balance(&(*root));

}

void srr(Bin_Node **root)
{
    Bin_Node *A = *root;
    Bin_Node *B = A->left;
    Bin_Node *C = B->right;

    //perform the rotation
    B->right = A;
    *root = B;

    //Assign B's right child to A->left as it must be smaller than A else if C = NULL sets A->left = NULL
    A->left = C;

    //call this to update balance factors of the moved nodes.
    balance(&(*root));
}

void dlr(Bin_Node **root)
{
    Bin_Node *A = *root;
    Bin_Node *B = A->right;
    Bin_Node *C = B->left;
    Bin_Node *CL = C->left;
    Bin_Node *CR = C->right;

    A->right = CL;
    B->left = CR;
    C->left = A;
    C->right = B;

    *root = C;

    balance(&(*root));
}

void drr(Bin_Node **root)
{
    Bin_Node *A = *root;
    Bin_Node *B = A->left;
    Bin_Node *C = B->right;
    Bin_Node *CL = C->left;
    Bin_Node *CR = C->right;

    B->right = CL;
    A->left = CR;
    C->left = B;
    C->right = A;

    *root = C;

    balance(&(*root));
}

void balance( Bin_Node **parent )
{
    int balance = differences( *parent );

    if ( balance > 1 )
    {
      //if ( differences( (*parent)->left ) > 0 )
      if ((*parent)->left->balance_factor > 0)
      {
        printf("parent->left is > 0 'single rotate right'\n");
        srr(&(*parent));
      }
      else
      {
        // some rotation here( parent )
        printf("parent->left <= 0 'double rotate right'\n");
        drr(&(*parent));
      }
    }
    else if ( balance < -1 )
    {
      //if ( differences( (*parent)->right ) > 0 )
      if ((*parent)->right->balance_factor > 0)
      {
        printf("parent->right > 0 'double rotate left'\n");
        dlr(&(*parent));
      }
      else
      {
        printf("parent->right <= 0 'single rotate left\n");
        slr(&(*parent));
      }
    }
}

int differences( Bin_Node *node )
{
    int lh = countlevels( node->left );
    int rh = countlevels( node->right );

    node->balance_factor = lh - rh;

    return node->balance_factor;
}

int countlevels(Bin_Node *node)
{
    if (!node)
    {
        return 0;
    }

    int lh = countlevels( node->left );
    int rh = countlevels( node->right );

    return max( lh, rh ) + 1;

}

int max(int x, int y)
{
    if (x > y)
    {
        return x;
    }

    return y;
}

---

Congrats, that works!

I ran one test putting nodes in order, 0 to 250, which makes the worst tree imbalance possible. This balanced the tree exactly. I also ran 250 to 0, 500 random, 0 to 250 + 500 random + 1000 to 750 in one run, all with exact AVL behavior as I can see it.

Are you calling that done for study, or do you intend to go down the rabbit hole to sort user structures with user supplied comparison functions?

did the balance factor work out for you it always printed out the old ones for me. i think thats about as deep as i need to go. i think the next stage is graphs but im not sure i am going to treat myself to an arduino in the very near future so i might start playing with that.

i think i owe you a few beers for all your help
coop

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

Cheers!