What do the following lines of code do?

Question

I have this code:

Arvore*   arv_insere   (Arvore* arvore, Registro* registro){  
  if (arvore == NULL){  
    printf(COLOR_RED     "ERROR: Arvore não inicializada"     COLOR_RESET "\n");  
    exit(1);  
  }  

  float direction = reg_compare(arvore->label, registro);  
  if (direction == 0.0){  
    printf(COLOR_RED     "ERROR: Não permitimos chaves repetidas"     COLOR_RESET "\n");  
    exit(1);  
  }  

  bool isTaller; // Avisa se a árvore filha que foi modificada ficou  
         // maior ou menor.  
  if (direction < 0) {  
      if (arvore->esq == NULL){  
    arvore->esq = arv_cria(registro);  
    // Ajustando balanceamento do nó criado e do nó atual.  
    arvore->esq->balanceamento = 0;  
    isTaller  = true;  
    arvore->balanceamento      = arvore->balanceamento - 1;  
      } else {  
    arvore->esq = arv_insere(arvore->esq, registro);  
    isTaller    = arvore->esq->sizeChanged;  
    if (isTaller) {  
      arvore->balanceamento    = arvore->balanceamento -1 ;  
    }  
      }  
  } else {  
      if (arvore->dir == NULL){  
    arvore->dir = arv_cria(registro);  
    // Ajustando balanceamento do nó criado e do nó atual.  
    arvore->dir->balanceamento = 0;  
    isTaller  = true;  
    arvore->balanceamento      = arvore->balanceamento + 1;  
      } else {
    arvore->dir = arv_insere(arvore->dir, registro);
    isTaller    = arvore->dir->sizeChanged;
    if (isTaller) {
      arvore->balanceamento      = arvore->balanceamento + 1;  
    }  
      }  
  }  
  // Nos veremos se geramos um balanceamento neste no da arvore. Se  
  // tivermos gerado, então balancearemos a árvore.  
  Arvore* nArvore = performRotations(arvore);  




if (isTaller && nArvore->balanceamento == 0) {  

    nArvore->sizeChanged = false;  

  } else {  

    nArvore->sizeChanged =  isTaller; 

  }  

  printf("SIZE CHANGED: %d \n" , nArvore->sizeChanged);  
  return nArvore;  
}

In this code, which makes the following excerpt?

if (isTaller && nArvore->balanceamento == 0) { 

    nArvore->sizeChanged = false;  

} else {  

    nArvore->sizeChanged =  isTaller; 

}  

Answer 1

The code is not the best, starting with bad identation (but also not the worst). Looking at what it does, it’s clearly the insertion procedure in a self-balancing tree, probably (but not necessarily) a avl tree.

Well, let’s start by trying to simplify this code:

if (isTaller && nArvore->balanceamento == 0) { 

    nArvore->sizeChanged = false;  

} else {  

    nArvore->sizeChanged =  isTaller; 

}  

In both cases, something is attributed to nArvore->sizeChanged. We will assemble a truth table to know what will be assigned to nArvore->sizeChanged:

+----------+-----------------------------+----------------------+
| isTaller | nArvore->balanceamento == 0 | nArvore->sizeChanged |
+----------+-----------------------------+----------------------+
| true     | true                        | false                |
| true     | false                       | true                 |
| false    | true                        | false                |
| false    | false                       | false                |
+----------+-----------------------------+----------------------+

I mean, we can replace that with this:

nArvore->sizeChanged = isTaller && nArvore->balanceamento != 0;

The meaning of the variable balanceamento is something that is clear when you work with AVL trees and seems to me to be implemented correctly (if you move the left node, it may be subtract 1, but if you move the right node, it may be that you add 1). The case of isTaller is a little more obscure, the name should mean that the height of the tree has changed, but below you will see that the name of the variable does not exactly reflect its meaning.

The variable isTaller by default has the value false. She can be true on four occasions:

• A) When direction < 0 and arvore->esq == NULL - in this case, the node in question on the pointer arvore has no left child and now has. Next we have arvore->balanceamento = arvore->balanceamento - 1;.

• B) When direction >= 0 and arvore->dir == NULL - in this case, the node in question on the pointer arvore has no right child and now has. Then we have arvore->balanceamento = arvore->balanceamento + 1;.

• C) When direction < 0, arvore->esq != NULL and arvore->esq->sizeChanged - in this case, we also have to arvore->balanceamento = arvore->balanceamento -1 ;.

• D) When direction >= 0, arvore->dir != NULL and arvore->dir->sizeChanged - in this case, we also have to arvore->balanceamento = arvore->balanceamento + 1;.

Note that this means that in all ways where the isTaller becomes true, the arvore->balanceamento changes. What if the isTaller allow false, the arvore->balanceamento will be unchanged. Therefore, this variable indicates if the balance changed, and a better name for it would be balanceamentoMudou.

So back to that:

nArvore->sizeChanged = isTaller && nArvore->balanceamento != 0;

If we rename isTaller we’ll have it:

nArvore->sizeChanged = balanceamentoMudou && nArvore->balanceamento != 0;

Which means that nArvore->sizeChanged will be true if the node balance changed and still remained unbalanced, being false otherwise. This explains the purpose of this code which was what you wanted to know.

The name sizeChanged is not suitable because the meaning of this field does not reflect it. A better name would be necessitaRebalanceamento. This makes sense when this variable is read in cases C and D, because if the child node needs rebalancing, then the balancing of the parent node must change, which can cause the occurrence of rotations to rebalance.

Finally, I say use exit(1); It’s not good programming practice, and there are very few cases where that’s the best thing to do. However, without seeing the context in which your tree is used, it is difficult to define an alternative.