Drzewa
AVL to taki specjalny rodzaj drzew BST (tak drzewo, AVL nadal jest
drzewem BST i posiada jego własności), w którym wierzchołki są
poukładane równomiernie, tzn że drzewo jest zrównoważone.
Zrównoważone drzewo to takie, w którym poziomy, których znajdują
się liście, nie różnią się o więcej niż 1. Czyli to takie
ładne drzewko :). Ale, żeby nasze drzewko urosło ładne i piękne
musimy o nie lepiej dbać niż o BST. Oznacza to, że będziemy
musieli nauczyć się nowych rzeczy, aby pracować na drzewach AVL.
1.Dodawanie
elementu
Samo
dodawanie elementu do drzewa jest takie same jak w drzewie BST, ale
najważniejszymi rzeczami w drzewach AVL są rotacje, czyli takie
przestawienie elementów, aby nasze drzewko było ładne. Wyróżniamy
dwa typy rotacji LL rotacja w prawo (elementy połączone
lewymi odnogami) i RR rotacja w lewo (prawymi odnogami).
Możemy wyróżnić jeszcze dwie RL,LR są to rotacje podwójne,
które składają się właśnie z kombinacji rotacji LL i RR.
ROTACJA
RR
Mamy 2 elementy połączone prawymi odnogami. Rotacja RR polega na tym aby zamienić relacje między tymi elementami w odpowiedni sposób. Rodzicem elementu A staje się element B, natomiast lewym dzieckiem elementu B staje się element A. Należy pamiętać że lewy syn elementu B staje się prawym synem elementu A. i od cała rotacja RR. Jak widać nie jest dość skomplikowana.
ROTACJA
LL
Rotacja LL jest odbiciem lustrzanym rotacji RR. Czyli znowu B staje się ojcem A, ale A teraz staje się prawym synem B. Natomiast prawy syn B staje się lewym A.
Jak
widzimy te rotacje nie są wcale takie trudne, teraz tylko trzeba
dobrze je używać.
ROTACJA
RL
Rotacja RL składa się z rotacji LL i z rotacji RR. Cała trudność polega tylko na tym, aby to dobrze zastosować.
ROTACJA
LR
Rotacja LR składa się z rotacji RR, a potem z rotacji LL użytych\ w taki sposób jak widać na rysunkach.
No
jak już wiemy jak używać rotacji to jeszcze trzeba wiedzieć kiedy
ich używać. Znaczy się my wiem kiedy, ale jeszcze nasz program
musi widzieć. Program tą informację czerpię z dodatkowej zmiennej
tzw. współczynnika równowagi (bf).
Wzór:
bf=wysokość_lewego_poddrzewa
– wysokość_prawego_poddrzewa
gdy
brak któregoś z synów to wstawiamy 0.
W
drzewie AVL ten współczynnik może przyjmować tylko 3 wartości.
0
– gdy oba poddrzewa są równej wysokości
1
– gdy lewa gałąź jest większa
-1
– gdy prawa gałąź jest większa
Należy
pamiętać, aby po każdym wstawienie elementu do drzewa liczyć
współczynnik, ponieważ jest to informacja czy dokonać rotacji.
Tak samo trzeba zrobić po dokonaniu rotacji, ponieważ rotacje
zmieniają wysokość drzewa.
Obecność
nowej zmiennej w strukturze drzewa spowodowało jej zmianę. Teraz
nasza struktura wygląda tak:
struct
treeAVL{
//
nasze wskazania
struct
treeAVL *parent;
struct
treeAVL *left;
struct
treeAVL *right;
//
int
key; // klucz
int
bf; // współczynnik
};
KOD:
void
RR(struct treeAVL **root, struct treeAVL *A){
//
rotacaj RR
struct
treeAVL *B=A->right, *p=A->parent;
A->right
= B->left;
if(A->right)
A->right->parent = A;
B->left=A;
B->parent=p;
A->parent=B;
//
gdy p == NULL to element A był naszym korzeniem
if(p!=NULL){
if(p->left
== A) p->left=B;
else
p->right=B;
}
else
*root=B;
}
/////////////////////////////////////////////////////////////////////////////
void
LL(struct treeAVL ** root, struct treeAVL *A){
//
rotacja LL
struct
treeAVL *B=A->left, *p=A->parent;
A->left=B->right;
if(A->left)
A->left->parent=A;
B->right=A;
B->parent=p;
A->parent=B;
//
gdy p == NULL to element A był naszym korzeniem
if(p){
if(p->left==A)
p->left=B;
else
p->right = B;
}
else
*root = B;
}
Jak
widzimy rotacje nie są zbyt skomplikowane i już raczej nic nie
powinno Cię zaskoczyć. Same rotacje to tak naprawdę przestawienie
elementów. Czyli zmieniamy relacje między elementami. Należy tylko
pamiętać o tym, że rotacja może zmienić nam korzeń dlatego
musimy tego pilnować.
void
wysoko(struct treeAVL *root,int level,int *h){
//
funkcja w zmiennej h będzie dawała nam wysokość poddrzewa
if(root){
if(root->right){
level++;
wysoko(root->right,level,h);
level--;
}
if(level>*h)
*h=level;
if(root->left){
level++;
wysoko(root->left,level,h);
level--;
}
}
}
Funkcją
wysoko
przechodzimy całe drzewo (poddrzewo). Argumentami są korzeń drzewa
albo poddrzewa, level (przy wywołaniu jest 0) oraz wysokość
przekazana jako adres zmiennej dzięki temu będziemy mogli ją
modyfikować tą funkcją i nie potrzebujemy nic zwracać.
void
BF(struct treeAVL *r){
//
funkcja liczy współczynnik po dokonani rotacji
//
argumentem jest element dla którego liczymy bf
int
a=0;
int
b=0;
struct
treeAVL *x=r, *y=x->left, *z=x->right;
if(y)
wysoko(y,1,&a);
if(z)
wysoko(z,1,&b);
x->bf=a-b;
}
Funkcja
ma za zadanie liczenie bf po dokonaniu rotacji. Liczenie bf
dokonuje się według wzoru, czyli liczymy wysokość lewego
poddrzewa potem prawego i liczymy w tym przypadku od 1. Pewnie
istnieją sposoby na policzenie bf w bardziej sprytny sposób.
Uważam jednak, że ten jest dość jasny i zrozumiały, ale
oczywiście zachęcam Cię do poprawienia mojego kodu :).
void
addAVL(struct treeAVL **root, int key){
//
funkcja główna naszego dodawania
struct
treeAVL *nowy_element,*p,*r, *d;
int
t;
//
tworzenie elementu
nowy_element
= (struct treeAVL *)malloc(sizeof(struct
treeAVL));
nowy_element->left
= nowy_element->right = nowy_element->parent = NULL;
nowy_element->key
= key;
nowy_element->bf
= 0;
//
zwykłe iteracyjne dodawanie elementu tak samo jak do BST
d=*root;
if(!d){
nowy_element->parent=NULL;
*root=nowy_element;
}
else{
while(d){
if(d->key
> key){
p=d;
d=d->left;
}else
if(d->key < key){
p=d;
d=d->right;
}else
break;
}
if(!d){
if(p->key>key)
p->left=nowy_element;
else
p->right=nowy_element;
nowy_element->parent=p;
}
r=nowy_element;
while(p){
// pętla liczy bf po dodaniu i sprawdza zgodność z AVL
if(p->left==r)
p->bf+=1;
else
if (p->right==r)p->bf-=1;
if(p->bf==2
|| p->bf==-2) break; // gdy nie zgodne wychodzi
r=p;
p=p->parent;
}
if(p){
// gdy pętla wyszła wcześniej, będą rotacje
if(p->bf
== 2){ // gdy lewe poddrzewo większe
if(p->right
!= r){
if(r->bf
== -1){ // LR, czyli podwójna
RR(root,p->left);
LL(root,p);
}
else
LL(root,p);
}
}
else{
if(p->left
!= r){
if(r->bf
== 1){ // RL, czyli podwójna
LL(root,p->right);
RR(root,p);
}
else
RR(root,p);
}
}
p=p->parent;
// policzenie BF dla elementów powiązanych ze sobą
if(p->right)BF(p->right);
if(p->left)BF(p->left);
BF(p);
}
}
}
Dodawanie
funkcja dodawanie do drzewa na samym początku jest taka sama ja przy
drzewie BST. Następnie obliczamy współczynnik bf potem
przechodzimy pętlą w górę i szukamy takiego miejsca gdzie nasz
współczynnik będzie niezgodny z naszym drzewem AVL. Wtedy wiemy,
że będziemy coś przestawiać. Więc musimy sprawdzić jakiej
rotacji dokonać. Sprawdzamy to poprzez sprawdzenie współczynnika
bf i na jego podstawie ustalamy rotację. Po dokonaniu rotacji
musimy ustalić nową wartość współczynnika bf, ponieważ
uległ zmianie, gdy przestawialiśmy elementy. Więc wywołujemy
funkcję BF dla elementów biorących udział w zamianie.
2.Usuwanie
elementu
Usuwanie
elementu z drzewa AVL jest dość skomplikowane, ale jak już
zrozumiesz to co było wcześniej, nagle okaże się, że to
kasowanie jest całkiem proste. Wystarczy jedynie wykorzystać wiedzę
już zdobytą :). Musisz umieć usuwać element z drzewa BST,
ponieważ samo usunięcie elementu polega na tym samym co przy
drzewach BST. No ale, żeby tak słodko i miło nie było to nie
koniec, bo … bo takie kasowanie może popsuć nasze piękne drzewko
(nie będzie zrównoważone). Ale mu już wiemy co zrobić, by nasze
drzewko było zrównoważone, więc jesteśmy hepi :D. Więc tylko
musimy znaleźć miejsce, w którym nasze drzewko się popsuło (ma
to związek z usuniętym elementem) i dokonać w tym miejscu
odpowiedniej rotacji. Teraz podam przykład kodu, ale nie szykuj się
na jakiś szok, bo nic nowego nie wymyśliłem (może :P).
Kod:
///////////////////////////
struct
treeAVL* delKey(struct treeAVL **root, int key){
if(*root!=
NULL){
if((*root)->key
> key) return delKey(&(*root)->left,key);
else{
if
((*root)->key < key) return delKey(&(*root)->right,
key);
else{
struct
treeAVL *z=*root, *p=z, *r=z,*y;
if(z->left==NULL){
if(z->right)
z->right->parent=(*root)->parent;
*root=z->right;
y=z->parent;
free(z);
z=NULL;
return
y;
}else{
if
(z->right==NULL){
z->left->parent=(*root)->parent;
*root=z->left;
y=z->parent;
free(z);
z=NULL;
return
y;
}else{
p=z->left;
r=z;
while(p->right!=NULL)
{
r=p;
p=p->right;
}
int
temp = p->key;
p->key=z->key;
z->key=temp;
if(r->key!=z->key){
r->right=p->left;
if(r->right!=NULL)
r->right->parent=p->parent;
}
else{
r->left=p->left;
if(r->left!=NULL)r->left->parent=p->parent;
}
y=p->parent;
free(p);
p=NULL;
return
y;
}
}
}
}
}
}
Tak
to jest to co myślisz, znaczy się to jest to co ja myślę, że
myślisz, a jak mam być już taki dokładny to jest to co ja myślę,
że powinieneś
myśleć :P. Czyli jest zwykła funkcja usuwająca element z drzewa
BST taka sama (no prawie) jaką omawiałem przy drzewach BST. Dodałem
tylko jedną małą rzecz, która nam się przyda przy ustalaniu
miejsca rotacji. Funkcja zwraca rodzica usuniętego elementu i od
tego miejsca będziemy szukać ewentualnego miejsca popsucia się
naszego drzewka.
void
removeAVL (struct treeAVL **root, int x){
if(*root){
struct
treeAVL *p=NULL,*r=NULL;
p=delKey(root,x);
// kasujemy nasz węzeł
r=p;
if(*root
&& p){ // jeśli drzewo istnieje, a usunęliśmy jakiś węzeł
while(p){
// szukamy miejsca zepsucia drzewa
BF(p);
if(p->bf==2
|| p->bf==-2) break; // gdy znaleźliśmy
r=p;
p=p->parent;
}
if(r==p){
// gdy pętla wykonała się tylko jeden raz to ustalamy r
// gdy pętla wykonała się tylko jeden raz to ustalamy r
if(!p->right)
r=p->left;
else
if(!p->left) r=p->right;
}
//
ustalamy i wykonujemy rotację tak samo jak przy dodawaniu
if(p){
if(p->bf
== 2){
if(p->right
!= r){
if(r->bf
== -1){ // LR
RR(root,p->left);
LL(root,p);
}
else
LL(root,p);
}
}else{
if(p->left
!= r){
if(r->bf
== 1){ // RL
LL(root,p->right);
RR(root,p);
}
else
RR(root,p);
}
}
//
//
obliczamy bf po rotacji
if(p->parent)
p=p->parent;
if(p->right)BF(p->right);
if(p->left)BF(p->left);
BF(p);
//
}
}
}
}
Tutaj
też cudów nie wymyśliłem. Na początku kasuję węzeł używając
do tego funkcji takiej samej jak przy BST. Funkcja zwraca mi miejsce
rodzica usuniętego elementu. Przypominam, że jak usuwamy element,
który ma dwóch potomków to dokonujemy tam zamiany kluczy, a
rzeczywisty element usuwany jest inny i tu właśnie chodzi nam
o ten rzeczywisty. Jak mamy już ten element to liczymy bf,
bo przecież usuwaliśmy element i szukamy miejsca popsucia.
Gdy znajdziemy to dokonujemy odpowiedniej rotacji i ponownie liczmy bf. Funkcję takie jak LL,RR,BF to są te same funkcje jak przy dodawaniu elementu.
3
Przechodzenia drzewa AVL
Przechodzenie
(szukanie elementu) drzewa AVL jest takie same jak przy drzewach BST.
Ponieważ oba te rodzaje drzewa różnią się tylko tymi rotacjami.
Podam tutaj tylko kod na „narysowanie” drzewa, bo samo wypisanie.
jak przy drzewach BST to nie wiele jednak nam powie o naszym drzewku.
Ponieważ przy drzewach AVL interesuje nas jeszcze rzeczywisty wygląd
naszego drzewa.
Kod:
void
write(struct treeAVL *root,int level){
if(root){
if(root->right){
level++;
write(root->right,level);
level--;
}
int
i;
for(i=0;i<level;i++)
printf(" ");
printf("%d
bf %d \n", root->key, root->bf);
if(root->left){
level++;
write(root->left,level);
level--;
}
}
}
Funkcja
nie jest dość skomplikowana. Liczy poziom na którym znajduje się
element, a potem daje spacje tyle ile wynosi poziom elementu.
Następnie wypisuje klucz i bf naszego elementu i przechodzi do nowej
linii. Funkcji tej można również używać do drzew BST.
Brak komentarzy:
Prześlij komentarz