DOMANDA Problema con albero binario senza ribilanciamento

dani24181

Nuovo Utente
3
0
Giorno a tutti, io ho un piccolo problema con il seguente codice:
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:
file1.PNG

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

Utente Attivo
653
279
CPU
Intel i5 3570K @ 4,5Ghz
Dissipatore
Scythe Mugen 2
Scheda Madre
Gigabyte Z77X-UD3H
HDD
Samsung 840 PRO 256GB + Sandisk Ultra 250GB + Sandisk Plus 960GB
RAM
2x8GB Crucial Ballistix Tactical @2000Mhz CL9
GPU
XFX RX480 GTR Black Edition
Audio
Auzentech X-Fi Forte
Monitor
AOC i2369VW
PSU
Seasonic P660
Case
eh?
Periferiche
Razer Naga HEX v2
OS
Windows 10 64bit - Linux Mint 18
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
Codice:
//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)
 
Ultima modifica:

dani24181

Nuovo Utente
3
0
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
Codice:
//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

Utente Attivo
653
279
CPU
Intel i5 3570K @ 4,5Ghz
Dissipatore
Scythe Mugen 2
Scheda Madre
Gigabyte Z77X-UD3H
HDD
Samsung 840 PRO 256GB + Sandisk Ultra 250GB + Sandisk Plus 960GB
RAM
2x8GB Crucial Ballistix Tactical @2000Mhz CL9
GPU
XFX RX480 GTR Black Edition
Audio
Auzentech X-Fi Forte
Monitor
AOC i2369VW
PSU
Seasonic P660
Case
eh?
Periferiche
Razer Naga HEX v2
OS
Windows 10 64bit - Linux Mint 18
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:
Codice:
//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.
 
Ultima modifica:

Entra

oppure Accedi utilizzando

Hot: Quale crypto per il futuro?

  • Bitcoin

    Voti: 37 55.2%
  • Ethereum

    Voti: 24 35.8%
  • Cardano

    Voti: 13 19.4%
  • Polkadot

    Voti: 2 3.0%
  • Monero

    Voti: 7 10.4%
  • XRP

    Voti: 10 14.9%
  • Uniswap

    Voti: 0 0.0%
  • Litecoin

    Voti: 6 9.0%
  • Stellar

    Voti: 6 9.0%
  • Altro (Specifica)

    Voti: 10 14.9%

Discussioni Simili