Fattore di bilanciamento AVL

[matteo1095]

Salve ragazzi sono nuovo del forum spero mi possiate aiutare. Sono un po di giorni che cerco di capire il fattore di bilanciamento ma proprio non ci riesco. Per esempio vi mostro un'albero preso da wikipedia che vi ho allegato.
Da quanto ho capito i figli inesistenti dovrebbero avere altezza -1 mentre le foglie altezza 0. Tenendo conto di ciò e facendo altezza sottoAlbero sinistro - altezza sottoAlbero destro a me il nodo con chiave 9 esce con un Fdb=−2 perchè a sinistra non ha figli quindi -1 e gli sottraggo -1 che dovrebbe essere il FdB del nodo con chiave 14
mentre il Fdb di 9 dovrebbe essere +2. Potete aiutarmi a capire i procedimenti

Grazie in anticipo

[cortinico]

Ciao.

Allora le questioni sono 2:
1) Secondo me la didascalia dell'immagine di wikipedia è sbagliata. I valore del fattore di bilanciamento sono tutti in segno sbagliati. Ho lasciato un messaggio per segnalare il problema nella pagina di discussione: https://it.wikipedia.org/wiki/Discussione:Albero_AVL Fra qualche giorno modifico

2) Il fattore di bilanciamento si calcola come la differenza fra l'altezza del sottoalbero sx e dx. Per esempio nel caso del nodo (9), non ha figli nel sottoalbero sx (quindi 0), ed ha un sottoalbero a destra alto 2. Quindi il risultato fa -2. Il nodo (76) ha coefficiente di bilanciamento 3.

In realtà la questione del segno importa poco in quanto a te interessa il modulo del fattore di bilanciamento; in particolare il fattore di bilanciamento di ogni nodo deve essere al più 1. Questo sta a dire che, se prendi ogni nodo, l'altezza dei suoi sottoalberi sx e dx deve differire al più di 1.

[matteo1095]

Grazie cortinico per i chiarimenti, si in effetti anche io alla fine mi ero convinto di un loro errore

[M_A_W_ 1968]

Personalmente consiglio di evitare del tutto wikipedia (in special modo quella italiana) quando si tratta di argomenti del genere, meravigliosamente spiegati nei testi sacri dell'algoritmica come pure in centinaia di dispense universitarie (che normalmente si rifanno più o meno esplicitamente a tali testi), tutte pubblicamente disponibili - talora anche in lingua italiana.

Tra l'altro, trattandosi di strutture dati piuttosto ordinarie, c'è chi ha pensato bene di chiudere il cerchio: esistono apposite librerie opensource che, cogliendo appieno la magistrale lezione di Knuth sull'idea di literate programming, sono anche documentate in modo sufficientemente ampio e sostanzialmente corretto, tale quindi da consentire almeno un primo approccio teorico all'argomento da parte di studenti e practitioners, i quali poi eventualmente approfondiranno grazie alla vastissima letteratura esistente.