What do the following lines of code do?

Question

What do the following lines of code do?

Navigation

#1 by (1 votes)

2

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, what does the following excerpt do?

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

    nArvore->sizeChanged = false;  

} else {  

    nArvore->sizeChanged =  isTaller; 

}

c

asked by anonymous 29.10.2017 / 02:35

1 answer

Multiples environment laravel Validate select with jQuery Validator

score 1 · Accepted Answer

The code is not the best, starting with bad indentation (but not the worst). Looking at what it does, it's clearly the procedure of inserting into a self-balanced 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 assigned to nArvore->sizeChanged . Let's set up 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                |
+----------+-----------------------------+----------------------+

That is, 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 it seems to be implemented correctly (if you move the left node, it might subtract 1, but if you move the right node, you can be that some 1). Since the isTaller case is a little more obscure, the name should mean that the height of the tree has changed, but below you will see that the variable name does not exactly reflect its meaning.

The variable isTaller defaults to false . It can be true on four occasions:

A) When direction < 0 and arvore->esq == NULL - in this case, the node in question in the arvore pointer does not have a left child and has it. Then we have arvore->balanceamento = arvore->balanceamento - 1; .
B) When direction >= 0 and arvore->dir == NULL - in this case, the node in question on the arvore pointer does not have a right child and has it. 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 arvore->balanceamento = arvore->balanceamento -1 ; .
D) When direction >= 0 , arvore->dir != NULL and arvore->dir->sizeChanged - in this case we also have arvore->balanceamento = arvore->balanceamento + 1; .

Note that this means that on all paths where isTaller becomes true, arvore->balanceamento changes. And if isTaller remains false, arvore->balanceamento will be unchanged. So this variable indicates whether the balancing has changed, and a better name for it would be balanceamentoMudou .

Going back to this:

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

If we rename isTaller we will have this:

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

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

The name sizeChanged is not suitable because the meaning of this field does not reflect this. 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 parent node balancing must change, which can cause rotations to rebalance.

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