How Binary Tree Removal Works in C

Question

I have several doubts about the operation of binary tree in C.

I have a code and I’m having second thoughts about how the tree removal works. Could someone explain to me better what is happening in each line on the removal part?

Struct

struct No{
    int numero;
    struct No *esquerda;
    struct No *direita;
};
typedef struct No No;

Insertion

void inserir(No **pRaiz, int numero){
    if(*pRaiz == NULL){
        *pRaiz = (No *) malloc(sizeof(No));
        (*pRaiz)->esquerda = NULL;
        (*pRaiz)->direita = NULL;
        (*pRaiz)->numero = numero;
    }else{
        if(numero < (*pRaiz)->numero)
            inserir(&(*pRaiz)->esquerda, numero);
        if(numero > (*pRaiz)->numero)
            inserir(&(*pRaiz)->direita, numero);
    }
}

Removal

No *MaiorDireita(No **no){
    if((*no)->direita != NULL) 
       return MaiorDireita(&(*no)->direita);
    else{
       No *aux = *no;
       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;
       return aux;
       }
}

No *MenorEsquerda(No **no){
    if((*no)->esquerda != NULL) 
       return MenorEsquerda(&(*no)->esquerda);
    else{
       No *aux = *no; 
       if((*no)->direita != NULL) // se nao houver essa verificacao, esse nó vai perder todos os seus filhos da direita!
          *no = (*no)->direita;
       else
          *no = NULL;
       return aux;
       }
}

void remover(No **pRaiz, int numero){
    if(*pRaiz == NULL){   // esta verificacao serve para caso o numero nao exista na arvore.
       printf("Numero nao existe na arvore!");
       getch();
       return;
    }
    if(numero < (*pRaiz)->numero)
       remover(&(*pRaiz)->esquerda, numero);
    else 
       if(numero > (*pRaiz)->numero)
          remover(&(*pRaiz)->direita, numero);
       else{    // se nao eh menor nem maior, logo, eh o numero que estou procurando! :)
          No *pAux = *pRaiz;     // quem programar no Embarcadero vai ter que declarar o pAux no inicio do void! :[
          if (((*pRaiz)->esquerda == NULL) && ((*pRaiz)->direita == NULL)){         // se nao houver filhos...
                free(pAux);
                (*pRaiz) = NULL; 
               }
          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;
                    }
                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;   
                   }
                }
             }
          }
}

Answer 1

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

So come on:

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

The removal 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 switch to the calling function 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 correct behavior. If you have an element that doesn’t exist removed from a structure, it does nothing, and you can assume that element no longer exists in the structure. Whether he existed before or not makes no difference.

Then he compares the number to know which sub-tree he is in. For this, he tests a set of conditions in order, and discards the possibilities methodically. Personally, I wouldn’t 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 number sought is less than the number of the current node:

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

If it is, it must 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 number sought is greater 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 of the number being higher or lower, we conclude that the number is located at the root of this tree. So pRaiz is the node to be removed! We proceed therefore 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 commentary refers to the fact that compilers that do not meet the C99 standard require that all local variables are declared in the principle of functions. This is 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’re handling the case of pRaiz be a leaf, that is, have no children neither left nor right. In this case, just erase the knot and run for the hug:

            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 this knot that you’re erasing, and the subtrees will hang on this new knot.

This new node has to 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, simply replace the node with the existing subtree.

            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. Then it’s not enough to simply replace the knot with one of the two trees, you have to choose either the biggest knot on the left or the smallest knot on the right of the guy you want to erase. In this case, the author chose the largest node on the left. He then "takes a step to the left" and goes down the tree to the right until he finds a node that has no right subtree. This was encapsulated in function MaiorDireita().

After that, he takes the right subtree of the knot and hangs it on 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 take a tree (which is going to be the left subtree of a knot that we want to erase), and go down to the right until he can’t do it anymore. The knot we stop at is the knot we want to return to, but first we need to remove it from the tree.

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

No *MaiorDireita(No **no){

We start walking recursively right until we can no longer;

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

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

        No *aux = *no;

We take 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 return the knot.

        return aux;
    }
}

To MenorDireita() is equal, mutatis mutandis.

Answer 2

You are removing a value within a binary search tree (it always maintains sorting after removal, so it is necessarily sorted). Take a look at the Wikipedia binary search tree article, will help your understanding.

These various ifs and elses are there to test how the reinsertion of the node’s child values will be done. For example, it checks if it is a leaf (case Leaf removal): does not need to reinsert anything; if he possesses only a single child (case Removing knot with a child): reinseres the subtree in place of the removed node; if it has two children (case Removal of node with two children): in this case, it puts the smallest child element of the removed node in its place (equal to the example from Wikipedia).

The binary tree data structure works the same in any 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 (Java, Python, C++). Depending on the paradigm, you can write more or less, you can be more or less flexible, but the central idea is the same in all of them.