AVL-puud: pööramised, sisestamine, kustutamine koos C++ Näide
Mis on AVL-puud?
AVL puud on binaarsed otsingupuud, milles vasaku ja parema alampuu kõrguse vahe on kas -1, 0 või +1.
AVL-puid nimetatakse ka isetasakaalustavaks binaarseks otsingupuuks. Need puud aitavad säilitada logaritmilist otsinguaega. See on nime saanud selle leiutajate (AVL) Adelsoni, Velsky ja Landise järgi.
Kuidas AVL Tree töötab?
AVL-puude vajaduse paremaks mõistmiseks vaatleme lihtsate kahendotsingupuude mõningaid puudusi.
Mõelge järgmistele võtmetele, mis on binaarsesse otsingupuusse antud järjekorras sisestatud.
Puu kõrgus kasvab lineaarselt, kui sisestame võtmed nende väärtuse suurenevas järjekorras. Seega võtab otsinguoperatsioon halvimal juhul O(n).
Elemendi otsimiseks kulub lineaarne aeg; seega ei ole selle kasutamisest kasu Binaarotsingupuu struktuur. Teisest küljest, kui puu kõrgus on tasakaalus, saame parema otsimisaja.
Vaatame nüüd samu võtmeid, kuid sisestatud erinevas järjekorras.
Siin on klahvid samad, kuid kuna need sisestatakse erinevas järjekorras, võtavad need erineva positsiooni ja puu kõrgus jääb tasakaaluks. Seega ei võta otsing puu ühegi elemendi jaoks rohkem kui O(log n). Nüüd on selge, et kui sisestamine on õigesti tehtud, saab puu kõrgust hoida tasakaalus.
AVL puude puhul kontrollime puu kõrgust sisestamise ajal. Muudatused tehakse tasakaalustatud kõrguse säilitamiseks, ilma binaarse otsingupuu põhiomadusi rikkumata.
Tasakaalutegur AVL-puudes
Tasakaalutegur (BF) on AVL-puude iga sõlme põhiatribuut, mis aitab jälgida puu kõrgust.
Tasakaaluteguri omadused
- Tasakaalutegurit nimetatakse vasaku alampuu ja parempoolse alampuu kõrguse erinevuseks.
- Tasakaalutegur (sõlm) = kõrgus (sõlm->vasak) – kõrgus (sõlm->parem)
- BF lubatud väärtused on –1, 0 ja +1.
- Väärtus –1 näitab, et parempoolses alampuus on üks lisapuu, st puu on parajalt raske.
- Väärtus +1 näitab, et vasakpoolne alampuu sisaldab ühte lisa, st puu on jäetud raskeks.
- Väärtus 0 näitab, et puu sisaldab mõlemal küljel võrdseid sõlmi, st puu on täiesti tasakaalus.
AVL-i pöörded
AVL-puu enda tasakaalustamiseks tehakse puust sõlme sisestamisel või kustutamisel pööramised.
Teostame järgmisi LL-pöördeid, RR-pöördeid, LR-pöördeid ja RL-i pööramisi.
- Vasak – vasakule pööramine
- Paremale – paremale pööramine
- Paremale – vasakule pööramine
- Vasak – parem pööramine
Vasak – vasakule pööramine
See pööramine toimub siis, kui uus sõlm lisatakse vasaku alampuu vasakpoolsesse alampuusse.
Tehakse üks parempööre. Seda tüüpi pöörlemine tuvastatakse, kui sõlme tasakaalustatud tegur on +2 ja selle vasakpoolsel lapsel on tasakaalutegur +1.
Paremale – paremale pööramine
See pööramine toimub siis, kui uus sõlm sisestatakse parema alampuu paremasse alampuusse.
Tehakse üks vasakule pööramine. Seda tüüpi pöörlemine tuvastatakse, kui sõlme tasakaalustatud tegur on -2 ja selle parempoolsel alamüksusel on tasakaalutegur -1.
Paremale – vasakule pööramine
See pööramine toimub siis, kui uus sõlm lisatakse vasaku alampuu paremasse alampuusse.
See pööramine toimub siis, kui sõlme tasakaalutegur on –2 ja selle parempoolsel alamüksusel on tasakaalutegur +1.
Vasak – parem pööramine
See pööramine toimub siis, kui parempoolse alampuu vasakpoolsesse alampuusse lisatakse uus sõlm.
See pööramine toimub siis, kui sõlme tasakaalutegur on +2 ja selle vasakpoolsel lapsel on tasakaalutegur -1.
Sisestamine AVL Puudesse
Sisestamisoperatsioon on peaaegu sama, mis lihtsate binaarsete otsingupuude puhul. Pärast iga sisestamist tasakaalustame puu kõrguse. Sisestamisoperatsioon võtab O(log n) halvima aja keerukuse.
Samm 1: Sisestage sõlm AVL-i puusse, kasutades sama BST-i sisestusalgoritmi. Ülaltoodud näites sisestage 160.
Samm 2: kui sõlm on lisatud, värskendatakse iga sõlme tasakaalutegurit. Pärast 160 sisestamist värskendatakse iga sõlme tasakaalutegurit.
Samm 3: Nüüd kontrollige, kas mõni sõlm rikub tasakaaluteguri vahemikku, kui tasakaalutegurit rikutakse, ja seejärel pöörake allolevat juhtumit kasutades. Ülaltoodud näites rikutakse tasakaalutegurit 350 ja seal hakkab kehtima juhtum 1, teostame LL-pöörde ja puu tasakaalustatakse uuesti.
- Kui BF(sõlm) = +2 ja BF(sõlm -> vasakpoolne laps) = +1, sooritage LL-i pööramine.
- Kui BF(sõlm) = -2 ja BF(sõlm -> parempoolne laps) = 1, teostage RR pööramine.
- Kui BF(sõlm) = -2 ja BF(sõlm -> parempoolne laps) = +1, sooritage RL-i pööramine.
- Kui BF(sõlm) = +2 ja BF(sõlm -> vasakpoolne laps) = -1, sooritage LR pööramine.
Kustutamine AVL-puudest
Kustutamine on samuti väga lihtne. Kustutame sama loogikaga nagu lihtsate binaarsete otsingupuude puhul. Pärast kustutamist struktureerime puu vajaduse korral ümber, et säilitada selle tasakaalustatud kõrgus.
Samm 1: Leidke puust element.
Samm 2: Kustutage sõlm vastavalt BST kustutamisele.
Samm 3: Võimalikud on kaks juhtumit:
Case 1: Kustutamine parempoolsest alampuust.
- 1A. Kui BF(sõlm) = +2 ja BF(sõlm -> vasakpoolne laps) = +1, sooritage LL-i pööramine.
- 1B. Kui BF(sõlm) = +2 ja BF(sõlm -> vasakpoolne laps) = -1, sooritage LR pööramine.
- 1C. Kui BF(sõlm) = +2 ja BF(sõlm -> vasakpoolne laps) = 0, sooritage LL-i pööramine.
Kohtuasi 2: kustutamine vasakust alampuust.
- 2A. Kui BF(sõlm) = -2 ja BF(sõlm -> parempoolne laps) = -1, sooritage RR pööramine.
- 2B. Kui BF(sõlm) = -2 ja BF(sõlm -> parempoolne laps) = +1, sooritage RL-i pööramine.
- 2C. Kui BF(sõlm) = -2 ja BF(sõlm -> parempoolne laps) = 0, sooritage RR-pööramine.
C++ AVL-puude näide
Allpool on C++ mis rakendab AVL-puid:
#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); }
Näide ülaltoodud koodist:
- Kopeerige ülalolev kood ja kleepige see kausta "avl.cpp".
- Koostage kood:
g++ avl.cpp -o run
- Käivitage kood.
./run
AVL-puude eelised
- AVL-puu kõrgus on alati tasakaalus. Kõrgus ei kasva kunagi üle log N, kus N on puu sõlmede koguarv.
- Võrreldes lihtsate binaarotsingu puudega, on see lihtsam otsinguaega.
- AVL-puudel on isetasakaalustamise võimalused.
kokkuvõte
- AVL-puud on isetasakaaluvad binaarsed otsingupuud.
- Tasakaalutegur on AVL-i puude põhiatribuut
- Sõlme tasakaalutegurit defineeritakse kui selle sõlme vasaku ja parema alampuu kõrguste erinevust.
- Tasakaaluteguri kehtivad väärtused on -1, 0 ja +1.
- Sisestamise ja kustutamise toiming nõuab pärast tasakaaluteguri rikkumist pööramist.
- Sisestamise, kustutamise ja otsimise ajaline keerukus on O(log N).
- AVL-puud järgivad kõiki binaarsete otsingupuude omadusi.
- Vasakpoolses alampuus on sõlmed, mis on juursõlmest väiksemad. Paremal alampuul on sõlmed, mis on alati suuremad kui juursõlm.
- AVL-puid kasutatakse seal, kus otsinguoperatsioon on sagedasem kui sisestamise ja kustutamise toimingud.