DOMANDA Problema con albero binario senza ribilanciamento

[dani24181]

Giorno a tutti, io ho un piccolo problema con il seguente codice:

[COLOR=#148022][FONT=Monaco]struct alb{[/FONT][/COLOR]
[COLOR=#148022][FONT=Monaco]   unsigned int chiave;[/FONT][/COLOR]
[COLOR=#148022][FONT=Monaco]   alb *sx, *dx;[/FONT][/COLOR]
[COLOR=#148022][FONT=Monaco]};[/FONT][/COLOR]

[COLOR=#148022][FONT=Monaco]void Inserisci(alb *&a, unsigned int chiave){[/FONT][/COLOR]
[COLOR=#148022][FONT=Monaco]   if (a == NULL){[/FONT][/COLOR]
[COLOR=#148022][FONT=Monaco]      a = new alb;[/FONT][/COLOR]
[COLOR=#148022][FONT=Monaco]      a->chiave = chiave;[/FONT][/COLOR]
[COLOR=#148022][FONT=Monaco]      a->sx = a->dx = NULL;[/FONT][/COLOR]
[COLOR=#148022][FONT=Monaco]      return;[/FONT][/COLOR]
[COLOR=#148022][FONT=Monaco]   }[/FONT][/COLOR]
[COLOR=#148022][FONT=Monaco]   if (chiave < a->chiave)[/FONT][/COLOR]
[COLOR=#148022][FONT=Monaco]      Inserisci(a->sx, chiave);[/FONT][/COLOR]
[COLOR=#148022][FONT=Monaco]   if (chiave > a->chiave)[/FONT][/COLOR]
[COLOR=#148022][FONT=Monaco]      Inserisci(a->dx, chiave);[/FONT][/COLOR]
[COLOR=#148022][FONT=Monaco]}[/FONT][/COLOR]

[COLOR=#148022][FONT=Monaco]int Stampa_S_D(alb *&a, const unsigned int K){[/FONT][/COLOR]
[COLOR=#148022][FONT=Monaco]   unsigned int ssx = 0, sdx = 0;[/FONT][/COLOR]
[COLOR=#148022][FONT=Monaco]   if (a->sx != NULL)[/FONT][/COLOR]
[COLOR=#148022][FONT=Monaco]      ssx = Stampa_S_D(a->sx, K);[/FONT][/COLOR]
[COLOR=#148022][FONT=Monaco]   if (a->dx != NULL)[/FONT][/COLOR]
[COLOR=#148022][FONT=Monaco]      sdx = Stampa_S_D(a->dx, K);[/FONT][/COLOR]
[COLOR=#148022][FONT=Monaco]   if (ssx*K < sdx)[/FONT][/COLOR]
[COLOR=#148022][FONT=Monaco]      cout << a->chiave << '\n';[/FONT][/COLOR]
[COLOR=#148022][FONT=Monaco]   return ssx + sdx + a->chiave;[/FONT][/COLOR]
[COLOR=#148022][FONT=Monaco]}[/FONT][/COLOR]

Il problema mi chiede questo:


Ovviamente il seguente codice non mi stampa in ordine crescente le chiavi dei nodi che rispettano la regola P, perché dovrei inserire la "cout" nel mezzo alle due visite.
Però non posso farlo perché prima di fare il confronto della regola P devo per forza visitare il sottoalbero destro di ogni nodo.


Avevo pensato di aggiungere nella struct 2 variabili 'S' e 'D' cosi da poterle calcolare con una specie di funzione di refresh ricorsiva e dopo stampare le chiavi che rispettavano la regola P con un'altra funzione di stampa molto semplice:
Visita sinistra
cout
Visita destra


Però non credo sia accettato nel compito d'esame e se la complessità rimane lineare nel numero di nodi.


Secondo voi cosa potrei fare? che alternative ho?
Vi ringrazio per l'aiuto.

- - - Updated - - -

Inserito duplicato per errore, a causa di problemi di connessione.
Scusate

 

[1nd33d]

La ricorsione per il calcolo della proprietà P è giusta, per quanto riguarda l'ordine potresti aggiungere alla struct una variabile P che è vera (!=0) se per quel nodo P è verificata, falsa (=0) altrimenti.
Durante il calcolo della proprietà non stampi nulla, ma imposti P. Successivamente effettui una normale ricerca in profondità introducendo un cout tra l'esplorazione del sottoalbero sinistro e destro (se P è vera per quel nodo).
La fase di calcolo di P richiede tempo lineare, così come la ricerca in profondità. Complessità totale O(2n) quindi lineare.

Una cosa del genere

//Funzione che verifica la proprietà P su nodo u
P(u, K)
  s = d = u.P = 0;
  if u.sx != null then  //ricorsione figlio sinistro
    s = P(u.sx)  //s è la somma dei valori del sottoalbero radicato in u.sx
  if u.dx != null then  //ricorsione figlio destro
    d = P(u.dx) //d è la somma dei valori del sottoalbero radicato in u.dx
  if s*K < d then 
    u.P = 1
  return u.key + s + d 

//Funzione che stampa i nodi per cui P è vera
S(u)
  if u.sx != null then  //ricorsione figlio sinistro
    S(u.sx)
  if u.P != 0 then
    print u.key
  if u.dx != null then  //ricorsione figlio destro
    S(u.dx)

 

[dani24181]

La ricorsione per il calcolo della proprietà P è giusta, per quanto riguarda l'ordine potresti aggiungere alla struct una variabile P che è vera (!=0) se per quel nodo P è verificata, falsa (=0) altrimenti.
Durante il calcolo della proprietà non stampi nulla, ma imposti P. Successivamente effettui una normale ricerca in profondità introducendo un cout tra l'esplorazione del sottoalbero sinistro e destro (se P è vera per quel nodo).
La fase di calcolo di P richiede tempo lineare, così come la ricerca in profondità. Complessità totale O(2n) quindi lineare.

Una cosa del genere

//Funzione che verifica la proprietà P su nodo u
P(u, K)
  s = d = u.P = 0;
  if u.sx != null then  //ricorsione figlio sinistro
    s = P(u.sx)  //s è la somma dei valori del sottoalbero radicato in u.sx
  if u.dx != null then  //ricorsione figlio destro
    d = P(u.dx) //d è la somma dei valori del sottoalbero radicato in u.dx
  if s*K < d then 
    u.P = 1
  return u.key + s + d 

//Funzione che stampa i nodi per cui P è vera
S(u)
  if u.sx != null then  //ricorsione figlio sinistro
    S(u.sx)
  if u.P != 0 then
    print u.key
  if u.dx != null then  //ricorsione figlio destro
    S(u.dx)

Non sarebbe per niente male, però da quanto ho appreso dai miei colleghi, lui non vuole che venga modificata la struct...

 

[1nd33d]

Capisco... ti serve comunque un'altra struttura, e per mantenere la complessità O(n) bisogna "sporcarsi" un po'...
La prima cosa che mi è venuta in mente:

//Funzione che verifica la proprietà P su nodo u 
P(u, K, L)
  s = d;
  if u.sx != null then 
    s = P(u.sx, K, L) 
  ind = L.accoda(u.key) //inserisce ordinatamente il valore nella lista e ritorna l'indirizzo di inserimento  
  if u.dx != null then 
    d = P(u.dx, K, L) 
  if !(s*K < d) then //P *non* verificata
    L.rimuovi(ind)  //rimuovi il valore inserito 4 righe sopra se il nodo non rispetta P
  return u.key + s + d

Perchè accodamenti e rimozioni siano O(1) ti serve una lista concatenata doppia, che costruirai da te con un'altra struttura (non è difficile).
Per gli accodamenti ti servirà avere un puntatore all'ultimo elemento della lista, per le delezioni invece hai già l'indirizzo (ritornato in fase di accodamento) per cui ti basta "bypassare" il nodo da rimuovere modificando il puntatore "a successivo" del nodo precedente e il puntatore "a precedente" del nodo successivo. Per l'output ti basterà leggere la lista ordinatamente.
Alternativamente, potresti anche usare un vettore di lunghezza pari alla dimensione dell'albero, cambierebbero un po' di cose ma si può fare, ma avrebbe una complessità leggermente superiore probabilmente, sempre lineare comunque.