memmory addresses not working out or me screwing somthing up

**cooper1200** · 06-13-2019

ok to take your examples further....

Code:

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

**cooper1200** · 06-13-2019

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

**cooper1200** · 06-13-2019

ok heres the drawing memmory addresses not working out or me screwing somthing up-rotate-left-jpg

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** · 06-13-2019

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 &

**Niccolo** · 06-13-2019

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.

**Niccolo** · 06-13-2019

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

**Niccolo** · 06-13-2019

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

**cooper1200** · 06-13-2019

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)

**Niccolo** · 06-13-2019

The problem is in your phrase:

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.

**Niccolo** · 06-13-2019

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.

**cooper1200** · 06-13-2019

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"

**Niccolo** · 06-13-2019

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.

**cooper1200** · 06-13-2019

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

**Click_here** · 06-13-2019

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

**Niccolo** · 06-13-2019

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.