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

---

what is the process of determining what this big function does in general?

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

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.

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

---

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.

what does
" rebalancing a branch of the tree"?

something like this....

Code:

---

..........    ..........
.../..\...    .../..\...
....../.\. => ./\.../.\.
..../\....    .../\.....

---

That ascii interpretation is horrid... but I am not changing it.

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

---

i forgot to mention that the input is BST tree

does it give some clue regarding what the purpose of this function?

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

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.

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

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.