Różnica między kompletnym drzewem binarnym i zbalansowanym drzewem binarnym

Question

Jaka jest różnica między zrównoważonym drzewem binarnym a pełnym drzewem binarnym? Czy to prawda, że ​​każde pełne drzewo binarne jest zrównoważonym drzewem? A może odwrotnie?

Answer 1

zrównoważony drzewo binarne jest drzewo binarne, gdzie głębokość dwóch poddrzew każdego węzła nie różnią się o więcej niż 1.

A całkowitego drzewa binarnego jest binarne drzewo, którego wszystkie poziomy z wyjątkiem ostatni poziom jest całkowicie wypełniony, a wszystkie liście na ostatnim poziomie są po lewej stronie.

Poniżej znajduje się zbalansowane drzewo binarne, ale nie pełne drzewo binarne. Każde pełne drzewo binarne jest zrównoważone, ale nie na odwrót.

 1 
    1  1 
    1 1  1 
1 

Jak wskazuje, w kompletnym drzewie, zawsze różnica poziomów będzie nie więcej niż 1, więc jest zawsze zrównoważony.