Drzewo zrównoważone i idealnie zrównoważone


(Kornicameister) #1

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 :confused:

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


([alex]) #2

Idealnie zrównoważone to takie w którym minimalna głębokość liścia różni się od maksymalnej głębokości co najwyżej o jeden.

Natomiast pojęcie "zrównoważone" zależy od przyjętego algorytmu równoważenia: R&B, AVL, Squeeze itp

To co jest zrównoważone wg R&B nie koniecznie jest zrównoważone wg AVL, a to co zrównoważone wg AVL nie koniecznie jest zrównoważone wg Squeeze.


(Kornicameister) #3

no to precyzuję, u mnie jest to algorytm AVL


([alex]) #4
C

   / \

  B E

 / / \

A D G

        /

       F

Wg AVL to drzewo jest zrównoważone, ale nie jest zrównoważone idealnie: min głębokość - 3; max - 5;


(Marcin 110) #5

alex , Twoje jest akurat idealnie zrównoważone.

Poniżej przykład drzewa AVL, ktore nie jest zrównoważone idealnie.

c58cd449a7b788f6.png


([alex]) #6

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?

D

     / \

    C E

   / \

  B F

 / \

A G

(Kornicameister) #7

przepraszam, dlaczego tutaj maks wysokość jest 5 ?


([alex]) #8

Jeżeli coś podczepimy pod F (lewo lub prawo) - będzie na poziomie 5

Jeżeli coś podczepimy pod B (prawo) - będzie na poziomie 3


(Kornicameister) #9

nie chcę być niemiły, ale dlaczego tutaj rozpatrujemy hipotetyczną sytuację, jeśli podczepimy ?


([alex]) #10

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.


(Kornicameister) #11

czyli ostatnie węzły z jakąś wartością w AVL to jeszcze nie liść, a dopiero NULL to liść ?


([alex]) #12

Przecież napisałem w poprzednim poście że dla AVL akurat nie ważne.


(Kornicameister) #13

a sorki, nie doczytałem

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 ?


([alex]) #14

Nie zupełnie, w AVL liczy się wysokość lewego i prawego poddrzewa a wysokość poddrzewa liczy się jako maksymalna głębokość liścia.

Natomiast dla drzewa idealnie zrównoważonego liczy się maksymalna i minimalna głębokość wszystkich liści.


(Marcin 110) #15

Przeczytaj sobie np. tu http://pl.wikipedia.org/wiki/Drzewo_%28matematyka%29, http://wazniak.mimuw.edu.pl/index.php?title=Metody_programowania_/Drzewa, http://wazniak.mimuw.edu.pl/index.php?title=Algorytmy_i_struktury_danych/S%C5%82owniki

W dwóch pierwszych artykułach liśćmi nazywa się węzły (istniejące!), które nie mają synów - nie jakieś cudaczne NULL dowiązania.

alex , nie gadaj głupot, bo Cię zgłoszę :stuck_out_tongue:


(Kornicameister) #16

7

    / \

   3 9

  / \ /

  1 6 8

    /

   5

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

zgadza się ?


([alex]) #17

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:

  • NULL na prawo od 9-ki ma głębokość 3;

  • NULL'ie po obu stronach 5-ki mają głębokości 5;

różnica o 2 poziomy.


(Marcin 110) #18

Jest zrównoważone IDEALNIE :twisted:

http://forum.dobreprogramy.pl/drzewo-zrownowazone-idealnie-zrownowazone-t378564.html#p2447822


([alex]) #19

To jak wytłumaczysz fakt istnienia drzewa lepiej zrównoważonego niż to IDEALNE wg ciebie?

6

   / \

  3 8

 / \ / \

 1 5 7 9

(Kornicameister) #20

panowie, to w końcu który ma rację ;p