Drzewa AVL …
Sunday, May 18th, 2008
Co to jest AVL?? Jest to zrównoważone drzewo poszukiwań binarnych ( BST ), w którym wysokość lewego i prawego poddrzewa każdego węzła różni się maxymalnie o jeden. Tyle w wielkim skrócie.
Jakie zalety ?
Otóż maksymalna wysokość drzewa AVL składającego się z n “danych” wynosić 1,44*log2(n), a drzewa BST niezrównoważonego n.
Wady ( jeśli można to tak nazwać )
Potrzeba wykonania rotacji ( 2 typy po 2 rotacje ):
RR - rotacja pojedyncza prawa
LL - rotacja pojedyncza lewa
RL - rotacja podwójna lewa ( najpierw prawa potem lewa )
LR - rotacja podwójna prawa ( najpierw lewa potem prawa )
(more…)