How Binary tree removal works in C

This is a binary tree that holds integers in intermediate nodes, in addition to the leaves, and with the property that all numbers in the left subtree of a given node are strictly smaller than the node number. Numbers equal or greater are in the right subtree.

So let's go:

void remover(No **pRaiz, int numero){

The remove function receives a pointer to a pointer to a node; this is necessary if the number to be removed (listed in the second parameter) is found in the root node itself: in this case, the address of pRaiz has to change to the function that calls remover() .

The first thing you do is test to see if the tree is empty, and if it is, finish:

    if(*pRaiz == NULL){   // esta verificacao serve para caso o numero nao exista na arvore.
       printf("Numero nao existe na arvore!");
       getch(); // getch() é fogo, mas tudo bem
       return;
    }

Although he writes an "error" message, this is a correct behavior. If you do remove an element that does not exist in a structure, it does nothing, and you can assume that that element no longer exists in the structure. Whether it existed before or not, it makes no difference.

Then it compares the number to know what subtree it is in. For this, it tests a set of conditions in order, and it discards the possibilities methodically. Personally, I would not do this kind of indentation and keep everything on the same level, but let's explain the code that exists, not what I would write:

The first case is if the searched number is less than the number of the current node:

    if(numero < (*pRaiz)->numero)
       remover(&(*pRaiz)->esquerda, numero);

If it is, it should be, by construction, in the left subtree. We then run the same algorithm recursively in the left subtree.

If it is not, then we check if the searched number is greater than the current number. If it is, it will be in the right subtree, and we run the algorithm recursively in the right subtree.

    else 
        if(numero > (*pRaiz)->numero)
            remover(&(*pRaiz)->direita, numero);

Finally, having eliminated the possibility that the number is greater or less, we conclude that the number is located at the root of this tree. Then pRaiz is the node to be removed! We therefore proceeded with the removal process:

        else{    // se nao eh menor nem maior, logo, eh o numero que estou procurando! :)

First we create an auxiliary variable to manipulate the nodes. The comment refers to the fact that compilers that do not meet the C99 standard require all local variables to be declared at the beginning of the functions. It's what I usually do for portability, but others do not like ...

            No *pAux = *pRaiz;     // quem programar no Embarcadero vai ter que declarar o pAux no inicio do void! :[

Now we treat the case of pRaiz being a leaf, that is, it has no children, neither on the left nor on the right. In this case, just delete the node and run to the embrace:

            if (((*pRaiz)->esquerda == NULL) && ((*pRaiz)->direita == NULL)){         // se nao houver filhos...
                free(pAux);
                (*pRaiz) = NULL; 
            }

Of course, the probability of the node being a leaf is low; in this case, you have to deal with the subtrees. One of the nodes will have to replace that node you're deleting, and the subtrees will hang over this new node.

This new node must be either the largest number of the left subtree, or the smallest number of the right subtree. It starts by treating cases where either one or the other is null: in this case, just replace the node with the subtree that exists.

            else{     // so tem o filho da direita
                if ((*pRaiz)->esquerda == NULL){
                    (*pRaiz) = (*pRaiz)->direita;
                    pAux->direita = NULL;
                    free(pAux); pAux = NULL;
                }
                else{            //so tem filho da esquerda
                    if ((*pRaiz)->direita == NULL){
                        (*pRaiz) = (*pRaiz)->esquerda;
                        pAux->esquerda = NULL;
                        free(pAux); pAux = NULL;
                    }

In this case, the final and more complicated, the item has children on both sides. It is not enough simply to replace the node with one of the two trees, you have to choose either the largest knot on the left or the smallest knot on the right of the face you want to delete. In this case, the author chose the largest node on the left. He then "steps to the left" and goes down the tree to the right until he finds a node that does not have a right subtree. This has been encapsulated in the MaiorDireita() function.

After this, it takes the right subtree of the node and hangs to the right of the new root; and the same with the left subtree. Then just destroy the old root and return.

                    else{       //Escolhi fazer o maior filho direito da subarvore esquerda.
                        pAux = MaiorDireita(&(*pRaiz)->esquerda); //se vc quiser usar o Menor da esquerda, so o que mudaria seria isso:
                        pAux->esquerda = (*pRaiz)->esquerda;          //        pAux = MenorEsquerda(&(*pRaiz)->direita);
                        pAux->direita = (*pRaiz)->direita;
                        (*pRaiz)->esquerda = (*pRaiz)->direita = NULL;
                        free((*pRaiz));  *pRaiz = pAux;  pAux = NULL;   
                     }
                 }
             }
         }
     }

In the case of MaiorDireita() , what he has to do is get a tree (which is going to be the left subtree of a node that we want to erase), and go down right until he can not do it anymore. The node where we stop is the node we want to return, but before we need to remove it from the tree.

Note that it by construction does not have a right subtree, but may have left. In this case, we will do as we did in the analogous case in remover() and replace it with your left child. Now that it is outside the subtree and has no more children hanging on it, it can be returned to replace the root above:

No *MaiorDireita(No **no){

We started recursively on the right until we could no longer do it;

    if((*no)->direita != NULL) 
       return MaiorDireita(&(*no)->direita);
    else{

Not being able to walk to the right, we keep a reference to the node that we will return;

        No *aux = *no;

We get the left subtree of the node, if any, and paste it in place of the current node;

        if((*no)->esquerda != NULL) // se nao houver essa verificacao, esse nó vai perder todos os seus filhos da esquerda!
           *no = (*no)->esquerda;
        else
           *no = NULL;

And we return the node.

        return aux;
    }
}

The MenorDireita() is equal, mutatis mutandis .

You are removing a value inside a binary search tree (it always keeps the order after removal, so it is necessarily ordered). Browse the Wikipedia binary tree search article , will help your understanding.

These various if s and else s are there to test how to reinsert the child values of the node. For example, it checks for a sheet (case Sheet Removal ): you do not need to reinsert anything; if it has only one child (case Node removal with a child ): reinsert the subtree instead of the removed node; if it has two children (case Node removal with two children ): In this case, it places the smallest child element of the removed node in its place (equal to example of Wikipedia ).

The binary tree data structure works the same in any and every chosen programming language. In some, you will need to adapt the object concept and access methods to the procedural paradigm ( C ), while others you can perfectly maintain use as abstract data type < strong>, Python , C ++ ). Depending on the paradigm, you can write more or less, it may be more or less flexible, but the central idea is the same in all of them.