Thread: Comparision of binary trees, balance.

  1. #16
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by blunt View Post
    Code:
    p->right=tmp->right;
    Right my bad, obviously, there should be
    @edit: No, I'd rather kill myself than finish that project. Now rotations doesn't work...
    That edit is correct. With that one line change, your left rotation is 100% correct. You need to make the corresponding change for the right rotation as well.
    Of course neither of these will appear to work correctly until you have a way of modifying the head. E.g. you need to pass your pointers by pointer, so that you can modify them.

    If this were C++ then you'd use references in which case you could add an "&" and you'd be done.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  2. #17
    Registered User
    Join Date
    Jan 2012
    Posts
    29
    Code:
    int leftrotate(two **p) {  
    	struct tree *tmp;
    	int data;
    	if(*p==0 || (*p)->right==0)
    		return 0; //no right node
    
    
    	tmp=(*p)->right; 
    	(*p)->right=tmp->left; //move node
    	tmp->left=(*p);
    	(*p)=tmp;
    	return 1;
    }
    Seem to be okey, not sure of it.

  3. #18
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Nailed it! you can remove the unused variable too though

    How's the rest of it coming? Did you check out that link I posted earlier? It had an implementation of exactly the algorithm you wanted.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #19
    Registered User
    Join Date
    Jan 2012
    Posts
    29
    Yes I did, and it's confusing. All I need now from that article is vine_to_tree and tree_to_vine functions right? It's probably because of C/C++ differences, but there are some things I don't get. So:
    Code:
    void DSW::tree_to_vine ( BasePtr root, int &size )
    {
        BasePtr vineTail, remainder, tempPtr;
        vineTail = root;
        remainder = vineTail->Right;
        size = 0;
        while ( remainder != NULL )
        {//If no leftward subtree, move rightward
            if ( remainder->Left == NULL )
            {
                vineTail = remainder;
                remainder = remainder->Right;
                size++;
            }    //else eliminate the leftward subtree by rotations
            else  // Rightward rotation
           {
                tempPtr = remainder->Left;
                remainder->Left = tempPtr->Right;
                tempPtr->Right = remainder;
                remainder = tempPtr;
                vineTail->Right = tempPtr;
            }
       }
    }
    RED: 'Size' just counts nodes right? Like in my balance function variable 'nodecount'. So why does the function take &size, then sets it to NULL?
    GREEN: It's rightward rotation so I could use here 'rightrotate()' right?T here are also 2 opposite functions, vine_to_tree, but maybe I will fully understand them when I understand this one above.

    But let's back to my balance function. It works (it should at least ) similarly.
    Code:
    int DSWbalance(two *p)
    {
          struct tree *q;
         int i,k,nodecount;
            
         for(q=p,nodecount=0;q!=0;q=q->right,++nodecount) //spine
              while(rightrotate(&p)==1);
     
         for(i=nodecount/2;i>0;i/=2)
             for(q=p,k=0;kleft) //balance
                 leftrotate(&p);}
    But effect is the same like in case of rotation before I've straighten up pointers problem. But why? Rotations do all damn job.
    Last edited by blunt; 02-17-2012 at 11:05 AM.

  5. #20
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Firstly the size variable is not set to null, it is set to zero. NULL is a pointer constant. Or at least it should be, which is why in later editions of the C++ standard they introduced the type strict nullptr. Anyway, from now on, say zero when you are talking about the number zero and not a pointer constant. To get to your actual question, size plays a huge role in the other function, vine_to_tree. The size variable is basically the height of the tree that the function makes. size is a reference because in this implementation, the function needs to give size back to the caller.

    Yes you can use rightrotate(). The code that you are referencing follows the original description of the algorithm in the paper. Yours is only differently implemented.

    You have to keep in mind that rebalancing changes the entire tree and this means that the root node can change too. So you should return the whole tree back to the caller. (Go back to your pointers lesson.)
    Last edited by whiteflags; 02-17-2012 at 12:05 PM.

  6. #21
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    I'm beginning to think I might have been wrong about your spine part not flattening the list fully, and the balance part might not be that far off also.

    Currently it wont even compile though because the for-loop is missing one of its semicolons and I have no idea where kleft comes from.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #22
    Registered User
    Join Date
    Jan 2012
    Posts
    29
    Ah that's my bad, I must have missclicked something: that's what I have:

    Code:
    int DSWbalance(two *p){  
        struct tree *q;
        int i,k=0,nodecount; 
        
        for(q=p,nodecount=0;q!=0;q=q->right) //spine
        {
            while(rightrotate(&p)==1)
                nodecount++;
        }
        for(i=nodecount/2;i>0;i/=2)
            for(q=p,k;k<i;++k,q=q->left) //balance
                leftrotate(&p);
    }
    This part is in 'constant motion' so I don't even remember the first concept, having new ideas makes me confused about what's what now, what's wrong etc
    Last edited by blunt; 02-17-2012 at 01:04 PM.

  8. #23
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Well if you don't know what to ask it's really hard to help you. Did you understand what I said in my last post?

  9. #24
    Registered User
    Join Date
    Jan 2012
    Posts
    29
    Understood but my mind cannot convert it into C. I think I'm to sure what's mine. My balance function should contain return balance()?

  10. #25
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    I need you to look from a birds eye.

    Imagine I want to use your binary trees because they are the best trees ever. I need to balance my tree, so I call DSWbalance.
    Code:
    struct tree* mytree;
    /* I build my tree after this line and need to balance it
     * before I start searching for nodes, based on human input.
     */
    DSWbalance(mytree);
    If DSWbalance changes what mytree points to, how are you going to return the changes to me? You should know two ways because we showed them to you before. Plus we already explained that pointers are passed by value. The mytree that I gave you gives you access to the nodes it points to - so you balance mytree - but you have to give me a way to update my pointer's value, too. (That is the pointer I use when I use your implementation of trees.)

    This would let you verify if the algorithm you implemented works, since you can inspect the same tree you just balanced from the new root.

  11. #26
    Registered User
    Join Date
    Jan 2012
    Posts
    29
    If DSWbalance changes what mytree points to, how are you going to return the changes to me?
    What I have in mind is this: x=x+y (x is from now old x plus change)

    My line of thought goes like this:
    1. My tree points to sth, DSW changes what my tree point to -> DSW changes sth.
    2. Now I need to return it to You. So I do sth like root=DSW(root) (x-root, y-change is function on x). If I'm correct, that was 1st way.
    3. Second way was using extra pointer?

    Sorry for being so unaware what's going on, but it's probably of my deadline or language barrier, I'll buy more patience.
    Last edited by blunt; 02-17-2012 at 05:59 PM.

  12. #27
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Good. You need to pick one of the ways and make it that way.

    Now imagine that you just want to confirm that DSWbalance works. You create a tree and pass it to DSWbalance, and the function gives you back the changes to the tree. To confirm that DSWbalance works correctly, you could then follow all the links and notice the shape of the tree. If the shape of the tree is not what it is supposed to be, there are more mistakes in DSWbalance and you need to investigate. Picking a way to return the changes in the tree makes this all possible.

  13. #28
    Registered User
    Join Date
    Jan 2012
    Posts
    29
    I'm thinking of something like:

    Code:
    struct tree *mytree;
    /*code code*/
    head=DSWbalance(head);
    
    int DSWbalance(struct tree *root)
    {
    /*algorithm*/
    return x;
    }
    What should be x? Root?

  14. #29
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    It should be the root of the balanced tree. Also notice that the return type is not int.

  15. #30
    Registered User
    Join Date
    Jan 2012
    Posts
    29
    So, in this example it will be?

    Code:
    intDSWbalance(structtree *root)
    { /*algorithm*/ return root; }

    Return type should/must be int?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Converting From Binary Tree to Threaded Binary Trees
    By elton_fan in forum C Programming
    Replies: 15
    Last Post: 11-08-2007, 11:41 PM
  2. binary tree balance problem
    By overkill in forum C++ Programming
    Replies: 5
    Last Post: 08-17-2006, 05:52 AM
  3. Binary Trees MINI MAXING, probability trees
    By curlious in forum General AI Programming
    Replies: 3
    Last Post: 09-30-2005, 10:57 AM
  4. balance binary tree
    By xddxogm3 in forum C++ Programming
    Replies: 6
    Last Post: 12-07-2003, 05:33 PM
  5. traversing binary trees or partial trees
    By sballew in forum C Programming
    Replies: 4
    Last Post: 12-05-2001, 09:19 PM

Tags for this Thread