Qual è la differenza tra un albero binario bilanciato e un albero binario completo? È vero che ogni albero binario completo è un albero equilibrato? E il contrario?Differenza tra albero binario completo e albero binario bilanciato
Un equilibrata albero binario è l'albero binario in cui la profondità dei due sottoalberi di ogni nodo non differisce di oltre 1.
Una completa albero binario è un albero binario cui tutti i livelli tranne la l'ultimo livello è completamente riempito e tutte le foglie nell'ultimo livello sono tutte sul lato sinistro.
Di seguito è riportato un albero binario bilanciato ma non un albero binario completo. Ogni albero binario completo è bilanciato ma non viceversa.
1
1 1
1 1 1
1
come suggerisce, in un albero completo, sempre la differenza di livello non sarà più di 1 quindi è sempre equilibrata.
Attento, non esiste una definizione standard di "albero binario bilanciato" e ci sono variazioni: https://cs.stackexchange.com/questions/3515/two-definitions-of-balanced-binary-trees e l'esempio mostrato a https://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees – huyz