Pagina 1 di 1

[Algoritmi] Esercizi su algoritmi

MessaggioInviato: 12/07/2019, 05:47
da Lexor
Ciao a tutti. Mi stavo esercitando per l'esame di algoritmi facendo tracce degli scorsi esami, purtroppo però ho qualche problema nel risolverli, o meglio intuitivamente so come risolverli ma non sono sicuro di come li ho implementati.
In totale sono due esercizi:

Esercizio 1:
Un BST esteso T è un BST in cui ogni nodo x di T ha, oltre ai campi standard, un campo n[x] che memorizza il numero di nodi presenti nel sottoalbero di T radicato in x (incluso x).
Si risponda ai seguenti quesiti.
a. Scrivere lo pseudocodice di una procedura efficiente InsertIntoExtendedBST(T, k) che inserisce la chiave intera k nel BST esteso T. Si calcoli la complessità e si dimostri la correttezza della procedura proposta.
b. Si consideri il problema dell’inserimento di una chiave in un BST esteso che è contemporaneamente un red-black tree. Quali modifiche sono necessarie? Si mostri come rispettare le proprietà dei BST estesi nel caso di una rotazione a sinistra.

Per quanto riguarda il punto a avevo pensato di modificare la funzione inserimento di un BST che mentre inserisce un nodo incrementa il campo n[x].

Codice:
InsertIntoExtendedBST(T, k)
{
   y = NIL
   x = T.root
   
   while x!=NIL
   {
      y = x
      T.n[x] = T.n[x]+1

      if z.key < x.key
         x = x.left
      else
         x = x.right
   }

   z.p = y

   if y == NIL
      T.root = z
   elseif z.key < y.key
      y.left = z
   else
      y.right = z
}


La complessità rimane la stessa della funzione originale quindi O(h)

Il punto b invece ho qualche problema a trovare cosa devo aggiungere per rendere la funzione compatibile con i red black tree.
Per quanto riguarda le rotazioni a sinistra avevo invece notato che basta scambiare tra di loro i valori n[x] e n[y] (x è il nodo che dopo la rotazione "sale" di livello mentre y quello che "scende")

Esercizio 2:
Sia G = (V, E) un grafo orientato e aciclico.
Dato un nodo x ∈ V , l’altezza h[x] di x in G è definita come la lunghezza massima di un qualsiasi percorso da x ad una foglia (i.e., nodo senza archi uscenti) di G.
a. Scrivere lo pseudocodice di una procedura Height(G) che, dato G in input, calcoli, per ogni x ∈ V , l’altezza h[x] di x in G.
b. Si determini la complessità e si dimostri la correttezza della procedura proposta.

Qui non sono per nulla sicuro dello svolgimento che ho fatto

Codice:
Height(G)
{
   for(each v in G.V)
   {
      G.h[v] = 0
   }
   
   for(each v in G.V)
   {
      BFS(G, v)   // Calcola il vettore delle distanze
      
      for(each u in V)
      {
         if(u.adj == NIL && u != v) // Se la lista di adiacenza è nulla allora il nodo è una foglia
         {
            if(v.d[u] > h[v])
               h[v] = v.d[u]
         }
      }
   }
}


Qui avevo pensato di inizializzare l'array delle altezze a 0 e poi sfruttare l'array delle distanze ricavato da BFS, scorrerlo e vedere per i nodi con lista di adiacenza nulla (foglia) se l'altezza ricavata è maggiore di quella memorizzata in quel momento.

Questi sono gli esercizi, avviso che non mi son messo a guardare la complessità in quanto prima volevo essere sicuro dello svolgimento corretto. E' corretto quello che ho fatto oppure è completamente da rifare?