Drzewa AVL: Obroty, Wstawianie, Usuwanie za pomocą C++ Przykład
Sara Chen
Czym są drzewa AVL?
Drzewa AVL to drzewa wyszukiwania binarnego, w których różnica między wysokością lewego i prawego poddrzewa wynosi -1, 0 lub +1.
Drzewa AVL nazywane są również samobalansującymi się drzewami wyszukiwania binarnego. Drzewa te pomagają zachować logarytmiczny czas wyszukiwania. Został nazwany na cześć swoich wynalazców (AVL) Adelsona, Velsky'ego i Landisa.
Jak działa drzewo AVL?
Aby lepiej zrozumieć potrzebę stosowania drzew AVL, przyjrzyjmy się pewnym wadom prostych drzew wyszukiwania binarnego.
Rozważ następujące klucze wstawione w podanej kolejności do drzewa wyszukiwania binarnego.
Wysokość drzewa rośnie liniowo, gdy wstawiamy klucze w kolejności rosnącej ich wartości. Zatem operacja wyszukiwania, w najgorszym przypadku, zajmuje O(n).
Wyszukiwanie elementu zajmuje czas liniowy; dlatego nie ma sensu używać Drzewo wyszukiwania binarnego struktura. Z drugiej strony, jeśli wysokość drzewa jest zrównoważona, uzyskujemy lepszy czas wyszukiwania.
Przyjrzyjmy się teraz tym samym klawiszom, ale umieszczonym w innej kolejności.
Tutaj klucze są takie same, ale ponieważ są włożone w innej kolejności, zajmują różne pozycje, a wysokość drzewa pozostaje zrównoważona. Dlatego wyszukiwanie nie zajmie więcej niż O(log n) dla dowolnego elementu drzewa. Obecnie jest oczywiste, że jeśli wstawianie zostanie wykonane prawidłowo, wysokość drzewa można utrzymać w równowadze.
W drzewach AVL sprawdzamy wysokość drzewa podczas operacji wstawiania. Modyfikacje są wprowadzane w celu utrzymania zrównoważonej wysokości bez naruszania podstawowych właściwości Binary Search Tree.
Współczynnik równowagi w drzewach AVL
Współczynnik równowagi (BF) jest podstawową cechą każdego węzła w drzewach AVL, która pomaga monitorować wysokość drzewa.
Właściwości współczynnika równowagi
- Współczynnik równowagi nazywany jest różnicą pomiędzy wysokością lewego i prawego poddrzewa.
- Współczynnik równowagi (węzeł) = wysokość (węzeł->lewy) – wysokość (węzeł->prawy)
- Dozwolone wartości BF to –1, 0 i +1.
- Wartość –1 wskazuje, że prawe poddrzewo zawiera jedno dodatkowe drzewo, tj. drzewo jest odpowiednio ciężkie.
- Wartość +1 wskazuje, że lewe poddrzewo zawiera jedno dodatkowe, tj. drzewo pozostaje ciężkie.
- Wartość 0 oznacza, że drzewo zawiera równe węzły po obu stronach, czyli drzewo jest doskonale zrównoważone.
Rotacje AVL
Aby drzewo AVL samo się zrównoważyło, podczas wstawiania lub usuwania węzła z drzewa wykonywane są rotacje.
Wykonujemy następujące rotacje LL, rotacje RR, rotacje LR i rotacje RL.
- W lewo – obrót w lewo
- Prawo – obrót w prawo
- Prawo – obrót w lewo
- Obrót w lewo – w prawo
W lewo – obrót w lewo
Ten obrót jest wykonywany, gdy nowy węzeł jest wstawiany po lewej stronie potomka lewego poddrzewa.
Wykonywany jest pojedynczy obrót w prawo. Ten typ rotacji jest identyfikowany, gdy węzeł ma współczynnik równowagi wynoszący +2, a jego lewe dziecko ma współczynnik równowagi wynoszący +1.
Prawo – obrót w prawo
Ten obrót jest wykonywany, gdy nowy węzeł jest wstawiany po prawym dziecku prawego poddrzewa.
Wykonywany jest pojedynczy obrót w lewo. Ten typ rotacji jest identyfikowany, gdy węzeł ma współczynnik równowagi wynoszący -2, a jego prawe dziecko ma współczynnik równowagi wynoszący -1.
Prawo – obrót w lewo
Ten obrót jest wykonywany, gdy nowy węzeł jest wstawiany w prawym dziecku lewego poddrzewa.
Ten obrót jest wykonywany, gdy węzeł ma współczynnik równowagi wynoszący –2, a jego prawe dziecko ma współczynnik równowagi wynoszący +1.
Obrót w lewo – w prawo
Ten obrót jest wykonywany, gdy nowy węzeł jest wstawiany w lewym dziecku prawego poddrzewa.
Ten obrót jest wykonywany, gdy węzeł ma współczynnik równowagi wynoszący +2, a jego lewe dziecko ma współczynnik równowagi wynoszący -1.
Wstawienie do drzew AVL
Operacja wstawiania jest niemal taka sama jak w prostych drzewach wyszukiwania binarnego. Po każdym wstawieniu wyrównujemy wysokość drzewa. Operacja wstawiania zajmuje O(log n) najgorszej złożoności czasowej.
Krok 1: Wstaw węzeł do drzewa AVL, używając tego samego algorytmu wstawiania co BST. W powyższym przykładzie wstaw 160.
Krok 2: Po dodaniu węzła aktualizowany jest współczynnik równowagi każdego węzła. Po wstawieniu liczby 160 aktualizowany jest współczynnik równowagi każdego węzła.
Krok 3: Teraz sprawdź, czy którykolwiek węzeł narusza zakres współczynnika równowagi, jeśli współczynnik równowagi został naruszony, a następnie wykonaj rotacje, korzystając z poniższego przypadku. W powyższym przykładzie zostaje naruszony współczynnik równowagi wynoszący 350 i zaczyna obowiązywać tam przypadek 1, wykonujemy rotację LL i drzewo zostaje ponownie zbilansowane.
- Jeśli BF(węzeł) = +2 i BF(węzeł -> lewe dziecko) = +1, wykonaj obrót LL.
- Jeśli BF(węzeł) = -2 i BF(węzeł -> prawe dziecko) = 1, wykonaj obrót RR.
- Jeśli BF(węzeł) = -2 i BF(węzeł -> prawe dziecko) = +1, wykonaj obrót RL.
- Jeśli BF(węzeł) = +2 i BF(węzeł -> lewe dziecko) = -1, wykonaj obrót LR.
Usuwanie w drzewach AVL
Usuwanie jest również bardzo proste. Usuwamy stosując tę samą logikę, co w prostych drzewach wyszukiwania binarnego. Po usunięciu, w razie potrzeby, przebudowujemy drzewo, aby zachować jego zrównoważoną wysokość.
Krok 1: Znajdź element w drzewie.
Krok 2: Usuń węzeł zgodnie z usunięciem BST.
Krok 3: Możliwe są dwa przypadki: -
Sprawa 1: Usuwanie z prawego poddrzewa.
- 1A. Jeśli BF(węzeł) = +2 i BF(węzeł -> lewe dziecko) = +1, wykonaj obrót LL.
- 1B. Jeśli BF(węzeł) = +2 i BF(węzeł -> lewe dziecko) = -1, wykonaj obrót LR.
- 1C. Jeśli BF(węzeł) = +2 i BF(węzeł -> lewe dziecko) = 0, wykonaj obrót LL.
Case 2: Usuwanie z lewego poddrzewa.
- 2A. Jeśli BF(węzeł) = -2 i BF(węzeł -> prawe dziecko) = -1, wykonaj obrót RR.
- 2B. Jeśli BF(węzeł) = -2 i BF(węzeł -> prawe dziecko) = +1, wykonaj obrót RL.
- 2C. Jeśli BF(węzeł) = -2 i BF(węzeł -> prawe dziecko) = 0, wykonaj obrót RR.
C++ Przykład drzew AVL
Poniżej znajduje się C++ który implementuje drzewa AVL:
#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;
struct node {
struct node *left;
int data;
int height;
struct node *right;
};
class AVL
{
private:
public:
struct node * root;
AVL(){
this->root = NULL;
}
int calheight(struct node *p){
if(p->left && p->right){
if (p->left->height < p->right->height)
return p->right->height + 1;
else return p->left->height + 1;
}
else if(p->left && p->right == NULL){
return p->left->height + 1;
}
else if(p->left ==NULL && p->right){
return p->right->height + 1;
}
return 0;
}
int bf(struct node *n){
if(n->left && n->right){
return n->left->height - n->right->height;
}
else if(n->left && n->right == NULL){
return n->left->height;
}
else if(n->left== NULL && n->right ){
return -n->right->height;
}
}
struct node * llrotation(struct node *n){
struct node *p;
struct node *tp;
p = n;
tp = p->left;
p->left = tp->right;
tp->right = p;
return tp;
}
struct node * rrrotation(struct node *n){
struct node *p;
struct node *tp;
p = n;
tp = p->right;
p->right = tp->left;
tp->left = p;
return tp;
}
struct node * rlrotation(struct node *n){
struct node *p;
struct node *tp;
struct node *tp2;
p = n;
tp = p->right;
tp2 =p->right->left;
p -> right = tp2->left;
tp ->left = tp2->right;
tp2 ->left = p;
tp2->right = tp;
return tp2;
}
struct node * lrrotation(struct node *n){
struct node *p;
struct node *tp;
struct node *tp2;
p = n;
tp = p->left;
tp2 =p->left->right;
p -> left = tp2->right;
tp ->right = tp2->left;
tp2 ->right = p;
tp2->left = tp;
return tp2;
}
struct node* insert(struct node *r,int data){
if(r==NULL){
struct node *n;
n = new struct node;
n->data = data;
r = n;
r->left = r->right = NULL;
r->height = 1;
return r;
}
else{
if(data < r->data)
r->left = insert(r->left,data);
else
r->right = insert(r->right,data);
}
r->height = calheight(r);
if(bf(r)==2 && bf(r->left)==1){
r = llrotation(r);
}
else if(bf(r)==-2 && bf(r->right)==-1){
r = rrrotation(r);
}
else if(bf(r)==-2 && bf(r->right)==1){
r = rlrotation(r);
}
else if(bf(r)==2 && bf(r->left)==-1){
r = lrrotation(r);
}
return r;
}
void levelorder_newline(){
if (this->root == NULL){
cout<<"\n"<<"Empty tree"<<"\n";
return;
}
levelorder_newline(this->root);
}
void levelorder_newline(struct node *v){
queue <struct node *> q;
struct node *cur;
q.push(v);
q.push(NULL);
while(!q.empty()){
cur = q.front();
q.pop();
if(cur == NULL && q.size()!=0){
cout<<"\n";
q.push(NULL);
continue;
}
if(cur!=NULL){
cout<<" "<<cur->data;
if (cur->left!=NULL){
q.push(cur->left);
}
if (cur->right!=NULL){
q.push(cur->right);
}
}
}
}
struct node * deleteNode(struct node *p,int data){
if(p->left == NULL && p->right == NULL){
if(p==this->root)
this->root = NULL;
delete p;
return NULL;
}
struct node *t;
struct node *q;
if(p->data < data){
p->right = deleteNode(p->right,data);
}
else if(p->data > data){
p->left = deleteNode(p->left,data);
}
else{
if(p->left != NULL){
q = inpre(p->left);
p->data = q->data;
p->left=deleteNode(p->left,q->data);
}
else{
q = insuc(p->right);
p->data = q->data;
p->right = deleteNode(p->right,q->data);
}
}
if(bf(p)==2 && bf(p->left)==1){ p = llrotation(p); }
else if(bf(p)==2 && bf(p->left)==-1){ p = lrrotation(p); }
else if(bf(p)==2 && bf(p->left)==0){ p = llrotation(p); }
else if(bf(p)==-2 && bf(p->right)==-1){ p = rrrotation(p); }
else if(bf(p)==-2 && bf(p->right)==1){ p = rlrotation(p); }
else if(bf(p)==-2 && bf(p->right)==0){ p = llrotation(p); }
return p;
}
struct node* inpre(struct node* p){
while(p->right!=NULL)
p = p->right;
return p;
}
struct node* insuc(struct node* p){
while(p->left!=NULL)
p = p->left;
return p;
}
~AVL(){
}
};
int main(){
AVL b;
int c,x;
do{
cout<<"\n1.Display levelorder on newline";
cout<<"\n2.Insert";
cout<<"\n3.Delete\n";
cout<<"\n0.Exit\n";
cout<<"\nChoice: ";
cin>>c;
switch (c)
{
case 1:
b.levelorder_newline();
// to print the tree in level order
break;
case 2:
cout<<"\nEnter no. ";
cin>>x;
b.root = b.insert(b.root,x);
break;
case 3:
cout<<"\nWhat to delete? ";
cin>>x;
b.root = b.deleteNode(b.root,x);
break;
case 0:
break;
}
} while(c!=0);
}
Działający przykład powyższego kodu:
- Skopiuj powyższy kod i wklej w „avl.cpp”.
- Skompiluj kod:
g++ avl.cpp -o run
- Uruchom kod.
./run
Zalety drzew AVL
- Wysokość drzewa AVL jest zawsze zrównoważona. Wysokość nigdy nie przekracza log N, gdzie N jest całkowitą liczbą węzłów w drzewie.
- Zapewnia lepszą złożoność czasu wyszukiwania w porównaniu do prostych drzew wyszukiwania binarnego.
- Drzewa AVL mają zdolność samorównoważenia.
Podsumowanie
- Drzewa AVL to samobalansujące się drzewa wyszukiwania binarnego.
- Współczynnik równowagi jest podstawową cechą drzew AVL
- Współczynnik równowagi węzła definiuje się jako różnicę między wysokością lewego i prawego poddrzewa tego węzła.
- Prawidłowe wartości współczynnika równowagi to -1, 0 i +1.
- Operacje wstawiania i usuwania wymagają wykonania obrotów po naruszeniu współczynnika równowagi.
- Złożoność czasowa operacji wstawiania, usuwania i wyszukiwania wynosi O(log N).
- Drzewa AVL podążają za wszystkimi właściwościami drzew wyszukiwania binarnego.
- Lewe poddrzewo ma węzły mniejsze niż węzeł główny. Prawe poddrzewo ma węzły, które są zawsze większe niż węzeł główny.
- Drzewa AVL są używane w sytuacjach, w których operacje wyszukiwania są częstsze niż operacje wstawiania i usuwania.
