5° Appello – 10/09/2018 - Domanda 1

A

int cerca(tree* root){
    int maxSx;
    int maxDx;
    if(root==NULL)
        return NULL;

    maxSx = cerca(root->sx);
    maxDx = cerca(root->dx);

    if(root->dato>maxSx){
        if(root->dato>maxDx){
            return root->dato;
        }else{
            return maxDx;
        }
    }else{
        if(maxSx>maxDx){
            return maxSx;
        }else{
            return maxDx;
        }
    }


}

B

int cerca(tree* root){
    if(root==NULL){return NULL;}

    if(root->dx==NULL){
        return root;
    }
    cerca(root->dx);
}

CASO A
Nel caso A l’albero binario non è BST. L’algoritmo deve quindi attraversare tutti i nodi. Per ogni foglia viene eseguito numero 1 confronto. Per ogni nodo interno vengono invece eseguiti al più 3 confronti.
Di conseguenza è possibile indicare T(N) come un O(N), con N numero di nodi dell’albero

CASO B
In questo caso invece la complessità è proporzionale all’altezza dell’albero.
Quindi nel caso l’albero sia un BST T(N) = O(h) con h altezza dell’albero.

Mi verrebbe da suggerire due funzioni del genere, giusto per confronto:

B

int cerca(tree* root) {
  tree* cur = root;

  while (cur->rx != nullptr)
    cur = cur->rx;

  return cur->dato;
}

Un poco più facile e più da C/C++, con O(n), caso migliore T(n) = 1 e caso peggiore T(n) = h

A

int max(int a, int b) {
  return (a > b) ? a : b;
}

int cerca(tree* root) {
  if (root == nullptr) return -999;

  int maxSx = cerca(root->sx);
  int maxDx = cerca(root->dx);

  // Returna il max confrontato tra il dato del nodo corrente e il max dei due sottorami
  return max(root->dato, max(maxSx, maxDx));
}

Questa l’ho solo semplificata con una funzione int max(int, int)