Albero binario "abbastanza" bilanciato [RISOLTO]

[Giova411]

Abbiamo un albero binario: per ogni nodo $t$ abbiamo una funzione $c(t)$ (che non è implementata ma da realizzare) che fornisce il numero di nodi.
Ossia $c(t)$ da il numero di nodi contenuti nel sottoalbero radicato in $t$ sapendo che $c(NIL) = 0$.
Sappiamo che è abbastanza bilanciato se rispetta per ogni nodo $t$:
c(t.left)<=c(t.right)*2+1 e che c(t.right)<= c(t.left)*2+1
Trovare il miglior algoritmo che prende in input un nodo $t$ e verifica se l'albero radicato in $t$ è abbastanza bilanciato (seguendo la suddetta formula data)

[apatriarca]

Direi che \(c(t) = c(left) + c(right) + 1.\) Puoi quindi calcolare il valore in modo ricorsivo e calcolare nello stesso codice anche il valore di quella formula e propagarlo ai nodi superiori. Non credo sia possibile fare di meglio considerando che la formula non è stata calcolata e devi comunque visitare tutti i nodi.

[Giova411]

Sì Apa! = )
Il problema è ritornare due valori: integer (usando pseudocodice) ed un valore boolean.
Come si potrebbe fare facendo anche, per esempio, una post-visita?

[apatriarca]

Non vedo quale sia il problema di restituire più valori (per esempio usando una tupla o struttura), in che linguaggio stai lavorando?

[Giova411]

No semplice pseudo-linguaggio.
Pensavo al consumo di memoria ma ho dubbi:
faccio la funzione che prende in input l'albero e basta e la voglio fare ricorsiva per una "classica" postvisita.
Poi, però, devo restituire un numero ed un booleano... Non è così banale per me

[apatriarca]

Per quanto riguarda il numero ti ho già fornito la formula. Devi fare le chiamate ai figli e poi sommare i valori restituiti dai figli più uno. Per quanto riguarda il valore booleano devi guardare i valori restituiti dai figli, se almeno uno dei due è falso restituisci falso, altrimenti ti calcoli quella condizione sui valori interi restituiti dai figli.

[Giova411]

Sì mi stai aprendo la capoccia come sempre: imparo più qui che coi libri...
La formula io l'avevo trovata così:
c(t.right)*2 + 1 >= 0 -- e -- c(t.left)*2 + 1 >= 0
quindi si arriva a
c(t.right) + c(t.left) + 1 >= 0

Questo valore c(t) = c(t.right) + c(t.left) + 1
dovrei inserlo in campi dei nodi da quel che mi consigli.

integer contanodi(TREE t)
 if t = nul then return 0
 else
    integer somma <-- 1 + contanodi(t.left()) + contanodi(t.right())
    t.write(somma)          // scrivo, con postvisita, in ciascun nodo il numero di nodi sottostanti
    return somma

Fin qui ci sono

[apatriarca]

Devi memorizzarti il valore restituito dalle chiamate ricorsive in delle variabili e non usarle subito per calcolarti il valore perché le devi poi riutilizzare.

[Giova411]

No niente Apa, non ci arrivo...
Sono fermo a...

boolean bilancia(TREE t)
 if t = nil then 
    t.write( 0 )
    return true

...

Forse dovrei usare una coda? (ecco... ho detto la caXXata..)

[apatriarca]

In haskell sarebbe qualcosa come segue:

data Tree a = Leaf | Branch a a

balanced :: Tree a -> Bool
balanced t = fst (balanced' t)

balanced' :: Tree a -> (Bool, Int)
balanced' Leaf = (True, 0)
balanced' (Branch left right) = (bL && bR && cond, bL + bR + 1)
   where (bL, cL) = balanced' left
         (bR, cR) = balanced' right
         cond = cL <= 2*cR + 1 && cR <= 2*cL + 1

[Giova411]

[Giova411]

Mi hai tirato fuori sto haskell!!!!
Non eri un appassionato del C++?!?!?!?!??!?!?!??!?!?!??!

[apatriarca]

Era semplice da scrivere.. Ma forse non è molto leggibile se non si conosce il linguaggio. In generale questo genere di cose sono più facili da scrivere in linguaggi funzionali. In ogni caso l'idea è la stessa qualsiasi sia il linguaggio.. Ma in realtà il codice è sbagliato.. La prima riga in cui definisco l'albero avrebbe dovuto essere:

data Tree a = Leaf | Branch a (Tree a) (Tree a)

e poi deve essere cambiata anche la riga

balanced' (Branch left right) = (bL && bR && cond, bL + bR + 1)

con

balanced' (Branch _ left right) = (bL && bR && cond, bL + bR + 1)

L'idea è di usare una seconda funzione che restituisce in qualche modo due valori, un booleano che serve per sapere se il sottoalbero rispetta la condizione e un numero intero che rappresenta il numero di nodi nel sottoalbero. Se il nodo è nullo, allora questa funzione deve restituire semplicemente true e 0. Se invece non è nullo si deve per prima cosa ottenere i valori dei rami figli e a questo punto restituire i valori che ho scritto nella riga sopra:
+ Il valore booleano sarà uguale a (bL and bR and cL <= 2*cR + 1 and cR <= 2*cL + 1)
+ Il valore intero sarà uguale a (cR + cL + 1)
dove (bL, cL) sono i valori restituiti dal ramo sinistro e (bR, cR) quelli restituiti dal ramo destro.

Avrai quindi qualcosa come il seguente:

boolean bilanciato(TREE t)
   (b, c) = bilanciato2(t)
   return b

(boolean, integer) bilanciato2(TREE t)
   if t == nul 
      then return (true, 0)
      else (bL, cL) = bilanciato2(t.left)
             (bR, cR) = bilanciato2(t.right)
             return (bL && bR && cL <= 2*cR + 1 && cR <= 2*cL + 1, cR + cL + 1)

[Giova411]

APA SEI UN GENIO!!!!!

(integer, boolean) bilanciato(TREE t)
 if t = nil then return ( 0 , true )
 else 
   ( cL , bilanciaL ) <-- bilanciato( t.left() )
   ( cR , bilanciaR ) <-- bilanciato( t.right() )
   return ( cL + cR + 1 , bilanciaL AND bilanciaR AND cL < 2*cR + 1 AND cR < 2*cL + 1 )

Ma volevo un'altra versione a sto punto!!!
Quella dove memorizzavo (senza badare allo spreco di memoria)
PRIMA O POI MI MANDERAI A QUEL PAESE CMQ

[apatriarca]

Non ho capito quale versione vorresti..

[Giova411]

Effettivamente ricordo d'aver studiato O'caml una decina di anni fa.....
Quindi questo tipo di "visione" del codice conviene!
Qui restituisco una tupla in modo un po' moderno direi. Fin qui OK
Per capire meglio sti alberi vorrei lavorare sui nodi proprio come dicevi all'inizio:
utilizzare proprio la memorizzazione sui nodi!
Lo so che non è efficiente. APA NON TI INCAbeep!
(non è affatto banale pero'!!!)

[apatriarca]

Intendi dire memorizzare c(t) in t? In questo caso allora non hai bisogno di una seconda funzione e devi semplicemente restituire il valore booleano (scrivendo invece il valore intero nel corrispondente campo della struttura).

boolean bilanciato(TREE t)
 if t = nil then return true
 else 
   bilanciaL <-- bilanciato( t.left() )
   bilanciaR <-- bilanciato( t.right() )
   t.setC(t.left().c() + t.right().c() + 1)
   return bilanciaL AND bilanciaR AND t.left().c() < 2*t.right().c() + 1 AND t.right().c() < 2*t.left().c() + 1

[Giova411]

Apa ma lavori alla NASA?
= )
Cacchio in un paio d'ore mi hai insegnato + cose tu che in una settimana di studi vari

Cosa fai esattamente qui?
t.setC(t.left().c() + t.right().c() + 1)
definisci la funzione c(), giusto?

PS: correttamente si assume c(nil) = 0

[apatriarca]

Sì, setto il valore di c().

[Giova411]

Quanto ti devo?
La lezione privata dico...
Posso versare su PayPal?

[Giova411]

"apatriarca":

boolean bilanciato(TREE t)
 if t = nil then return true
 else 
   bilanciaL <-- bilanciato( t.left() )
   bilanciaR <-- bilanciato( t.right() )
   t.setC(t.left().c() + t.right().c() + 1)
   return bilanciaL AND bilanciaR AND t.left().c() < 2*t.right().c() + 1 AND t.right().c() < 2*t.left().c() + 1

Pensavo.... Complessità??
Mi viene da "sparare" un O(n) ma forse qualcosina in più