czy może mi ktoś wytłumaczyć jaka jest różnica między takimi drzewami, bo jak czytam definicję i patrzę na nie, to każde drzewo które jest zrównoważone musi być idealnie zrównowazone ?
jak to poznać, bo już sam nie wiem gdzie szukać, nic nie dało mi satysfakcjonującej odpowiedzi
moje definicje
zrównoważone -> drzewo binarne, w którym dla każdego węzła wysokość jego lewego i prawego podrzewa różni się nie więcej niż o jeden.
idealnie zrównoważone -> drzewo binarne, które jest zrównoważone i w którym wszystkie liście znajdują się na jednym lub na dwóch poziomach
tyle, że ten kawałek liście na 1 lub 2 poziomach, to już jest formalnością z warunku drzewa zrównoważonego
Nie jest ! Musisz patrzeć na liścia czyli na miejsca gdzie może być podczepiony dodatkowy węzeł. Zastanów się czy to też wg ciebie idealnie zrównoważone?
Liśćmi drzew BST nazywane są puste powiązania NULL’ie. Wszystkie dodane do drzewa węzły nie są liśćmi. Takie założenia są niezbędne do zrozumienia R&B, squeeze oraz drzew równoważonych wagowo. Dla AVL akurat nie ważnie co nazwiemy liśćmi a co nie.
to zapytam tak, jak sprawdza się czy jest zrównoważone to sprawdza się wysokości podrzew dla każdego węzła oddzielnie i jeśli każdy spełnia warunek, to drzewo jest zrównoważone, a żeby sprawdzić czy jest idealnie zrównoważone to patrzę na to drzewo, które uznałem za zrównoważone, “globalnie” i jeśli poziomy wszystkich liści nie różnią się o wiecej niż 1, to jest ono też zrównoważone ?
a to drzewo dla przykładu ? jak dla mniej jest ono zrównoważone, ponieważ wysokości lewego i prawego poddrzewa dla każdego węzła nie różnią się o więcej niż 1… i jest też drzewem zrównoważonym idealnie, bo liście tj. 1;8 mają głębokość 3, a liść 5 ma wysokość 4, różnica nie jest większa niż 1, więc jest to również drzewo idealnie zrównoważone
Owszem jest to drzewo zrównoważone wg AVL, natomiast nie jest zrównoważone idealnie. Zobacz trzeci poziom jeszcze nie jest do końca wypełniony a jest już rozpoczęty czwarty. Jak chcesz mówić o równoważeniu idealnym to patrz na NULL’ie: