Thread: what this function does..(i tried to trace it)

  1. #1
    Banned
    Join Date
    Oct 2008
    Posts
    1,535

    what this function does..(i tried to trace it)

    i understand what each line does here

    but i cant see what this function does in general??

    Code:
    typedef struct node node;         //node is alias for struct node
    struct node{                               
        int value,count;
        node *lc,*rc;
    };
    
    node *what(node *tree){
        node *save,*temp;
        int flag;
        if(!tree)return NULL;          //if root is null the program stops and return null
        if(!tree->lc && !tree->rc){ 
               free(tree);
               return NULL;
        }                                         //if the sons of root is null then we free the root and 
                                                   //return null
    
    
        save=temp=tree;                // save and temp point to the same place as the root
     
        if(save->lc) {flag=1;            //if (*save).lc differs null 
    
                       save=save->lc;    //save points to the same place as its left son
     
                       while(save->rc){ //while saves right son differs null
                           flag=0;        
                           temp=save;
                           save=save->rc;  //save point to the same place where save right son
                       }
        }
        else{ flag=0;               //if (*save).lc equals null 
               save=save->rc;    //save points to the same place as its right son
               while(save->lc){  //while saves left son differs null
                   flag=0;
                   temp=save;   
                   save=save->rc; //save points to the same place as its right son
               }
    
        }
        if(!flag)
              temp->rc=save->lc;
         else
               temp->lc=save->rc;
         tree->value=save->value;
         return tree;
    }
    Last edited by transgalactic2; 10-28-2008 at 04:25 AM.

  2. #2
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    what is the process of determining what this big function does in general?

  3. #3
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    First it test the head node of the tree for NULL, continuing if false
    Second it test the head node for children, continuing if true
    Then if there is a left child, it finds the right most descendant
    else on the right child it finds the left most descendant.

    Finally it returns the value of that descendant.


    after this he does this:

    Code:
    if(!flag)                                      //if flag=0
              temp->rc=save->lc;
         else
               temp->lc=save->rc;
         tree->value=save->value;
         return tree;
    }
    what is the purpose of this last part??

  4. #4
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Is this for making a self-balancing tree? That is kinda what it looks like. Though it uses sort of a convoluted and retarded algorithm to do so.

  5. #5
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    i figured out most of the code
    i dont know what does this last part
    Code:
    if(!flag)                                      //if flag=0
              temp->rc=save->lc;
         else
               temp->lc=save->rc;
         tree->value=save->value;
         return tree;
    }

  6. #6
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    It is rebalancing a branch of the tree. Draw a picture... or get some noodles out or something if you need to... I think perhaps you may be more wondering why moreso than what.

  7. #7
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    what does
    " rebalancing a branch of the tree"?

  8. #8
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    something like this....

    Code:
    ..........    ..........
    .../..\...    .../..\...
    ....../.\. => ./\.../.\.
    ..../\....    .../\.....

  9. #9
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    That ascii interpretation is horrid... but I am not changing it.

  10. #10
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    i am puzzled regarding this last part
    because all the code from the start till that part was only
    about a tree called "save"

    but now it mixes up with other trees
    i cant see the logic of this
    Code:
    if(!flag)                                      //if flag=0
              temp->rc=save->lc;
         else
               temp->lc=save->rc;
         tree->value=save->value;
         return tree;
    }
    Last edited by transgalactic2; 10-28-2008 at 01:50 PM.

  11. #11
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    i forgot to mention that the input is BST tree

    does it give some clue regarding what the purpose of this function?
    Last edited by transgalactic2; 10-28-2008 at 01:50 PM.

  12. #12
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    in this bst tree the function does:
    it references the input tree root to save.
    first it looks at the left son (smaller then root) then checks if it differ null
    then it takes the biggest object in this branch
    and references it to node temp.

    but if the left son of the root is null then it checks the branch of the right son
    and takes the smallest member from this branch and put it to temp.

    the problem is when i try to go to the last part
    in every case
    we put the end of a tree to temp and save.
    so how can they ask for temp.lc
    save.rc

    they are surely null
    ??

    the answer is that it finds the smallest member it the tree
    i dont know how they got it

  13. #13
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    There's no earthly reason why temp.lc or save.rc should be null. In case (1) you take the left side, and then as many right sides as you can; at the end you take a left side. In case (2) you switch left and right.

    On the other hand, you don't seem to do anything with temp, once you have it.

  14. #14
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    Code:
    while(save->lc)
    the loop stops when save.lc=null (when we reach the end of the tree)

    so when we reference this member
    and ask its left or right side we surely get null
    Last edited by transgalactic2; 10-28-2008 at 02:51 PM.

  15. #15
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    I don't know what the algorithm is supposed to do for sure -- I know what it is close to doing, but it is not doing so. (That is to say, left and right are not being treated symmetrically, possible segfaults are being created, and so on.) Part of that, apparently, is that temp is just ... there ... and not being used. You're right that what's there is probably not wanted, but who knows what it's supposed to be.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Lame null append cause buffer to crash
    By cmoo in forum C Programming
    Replies: 8
    Last Post: 12-29-2008, 03:27 AM
  2. Seg Fault in Compare Function
    By tytelizgal in forum C Programming
    Replies: 1
    Last Post: 10-25-2008, 03:06 PM
  3. Another syntax error
    By caldeira in forum C Programming
    Replies: 31
    Last Post: 09-05-2008, 01:01 AM
  4. Replies: 28
    Last Post: 07-16-2006, 11:35 PM
  5. const at the end of a sub routine?
    By Kleid-0 in forum C++ Programming
    Replies: 14
    Last Post: 10-23-2005, 06:44 PM