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

  1. #16
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    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

  2. #17
    Registered User
    Join Date
    May 2019
    Posts
    209
    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).

  3. #18
    Registered User
    Join Date
    May 2019
    Posts
    209
    @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.
    Last edited by Niccolo; 06-13-2019 at 03:07 PM.

  4. #19
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    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

  5. #20
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    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.

  6. #21
    Registered User
    Join Date
    May 2019
    Posts
    209
    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)

  7. #22
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    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 &

  8. #23
    Registered User
    Join Date
    May 2019
    Posts
    209
    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.
    Last edited by Niccolo; 06-13-2019 at 03:36 PM.

  9. #24
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    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

  10. #25
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    let me go and draw a diagram and some psudo code to what i think should be happening

  11. #26
    Registered User
    Join Date
    May 2019
    Posts
    209
    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
    Last edited by Niccolo; 06-13-2019 at 03:46 PM.

  12. #27
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    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

  13. #28
    Registered User
    Join Date
    May 2019
    Posts
    209
    @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 **)

  14. #29
    Registered User
    Join Date
    May 2019
    Posts
    209
    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 ) )
    Last edited by Niccolo; 06-13-2019 at 04:46 PM.

  15. #30
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    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)

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 8
    Last Post: 08-19-2011, 06:53 PM
  2. Working with memory addresses
    By Fujy in forum C++ Programming
    Replies: 7
    Last Post: 01-18-2010, 09:31 AM
  3. Memmory Issues and Threads
    By ddod in forum Windows Programming
    Replies: 2
    Last Post: 08-13-2004, 10:30 AM
  4. Freeing memmory - Automatic?
    By Vber in forum C Programming
    Replies: 4
    Last Post: 04-23-2003, 04:43 AM
  5. Memmory Allocation
    By MethodMan in forum C Programming
    Replies: 4
    Last Post: 04-16-2002, 01:56 PM

Tags for this Thread