AVL fák: elforgatások, beszúrás, törlés C++ Példa
Sarah Chen
Mik azok az AVL fák?
AVL fák olyan bináris keresőfák, amelyekben a bal és a jobb oldali részfa magassága közötti különbség -1, 0 vagy +1.
Az AVL fákat önkiegyensúlyozó bináris keresőfának is nevezik. Ezek a fák segítenek fenntartani a logaritmikus keresési időt. Nevét feltalálóiról (AVL) Adelsonról, Velskyről és Landisről kapta.
Hogyan működik az AVL Tree?
Hogy jobban megértsük az AVL-fák szükségességét, nézzük meg az egyszerű bináris keresőfák néhány hátrányát.
Tekintsük a következő kulcsokat a megadott sorrendben beszúrva a bináris keresési fába.
A fa magassága lineárisan nő, ha a kulcsokat értékük növekvő sorrendjében helyezzük be. Így a keresési művelet legrosszabb esetben O(n).
Egy elem keresése lineáris időt vesz igénybe; ezért nincs értelme a Bináris keresési fa szerkezet. Másrészt, ha a fa magassága kiegyensúlyozott, jobb keresési időt kapunk.
Nézzük most ugyanazokat a kulcsokat, de más sorrendben beillesztve.
Itt a billentyűk ugyanazok, de mivel eltérő sorrendben vannak behelyezve, eltérő pozíciót foglalnak el, és a fa magassága kiegyensúlyozott marad. Ezért a keresés nem vesz igénybe O(log n)-nél többet a fa egyetlen eleménél sem. Ma már nyilvánvaló, hogy ha a beillesztést helyesen végezzük, a fa magassága egyensúlyban tartható.
Az AVL fákban a beillesztési művelet során ellenőrizzük a fa magasságát. Módosításokat végeznek a kiegyensúlyozott magasság fenntartása érdekében a Bináris keresőfa alapvető tulajdonságainak megsértése nélkül.
Balance Factor az AVL fákban
Az egyensúlytényező (BF) az AVL-fák minden csomópontjának alapvető tulajdonsága, amely segít a fa magasságának figyelésében.
Az egyensúlytényező tulajdonságai
- Az egyensúlytényező a bal oldali részfa és a jobb oldali részfa magassága közötti különbség.
- Egyensúlytényező(csomópont) = magasság(csomópont->bal) – magasság(csomópont->jobb)
- A BF megengedett értékei –1, 0 és +1.
- A –1 érték azt jelzi, hogy a jobb oldali részfa tartalmaz egy pluszt, azaz a fa megfelelő nehéz.
- A +1 érték azt jelzi, hogy a bal oldali részfa tartalmaz egy pluszt, azaz a fa nehéz marad.
- A 0 érték azt mutatja, hogy a fa mindkét oldalán egyenlő csomópontokat tartalmaz, azaz a fa tökéletesen kiegyensúlyozott.
AVL forgások
Annak érdekében, hogy maga az AVL-fa egyensúlyba kerüljön, egy csomópont beillesztésekor vagy törlésekor a rendszer elforgatásokat hajt végre.
A következő LL-forgatást, RR-forgatást, LR-forgatást és RL-forgatást hajtjuk végre.
- Balra – Balra forgatás
- Jobbra – Jobbra forgás
- Jobbra – Balra forgatás
- Balra – Jobbra Forgatás
Balra – Balra forgatás
Ez a forgatás akkor történik meg, amikor egy új csomópontot szúrnak be a bal oldali részfa bal oldali gyermekéhez.
Egyetlen jobbra forgatás történik. Az ilyen típusú forgatást akkor azonosítjuk, ha egy csomópont kiegyensúlyozott tényezője +2, a bal oldali gyermeké pedig +1.
Jobbra – Jobbra forgás
Ezt a forgatást akkor hajtják végre, ha egy új csomópontot szúrnak be a jobb oldali részfa jobb gyermekéhez.
Egyetlen balra forgatás történik. Az ilyen típusú forgatást akkor azonosítjuk, ha egy csomópont kiegyensúlyozott tényezője -2, és jobb gyermeke egyensúlyi tényezője -1.
Jobbra – Balra forgatás
Ez a forgatás akkor történik meg, amikor egy új csomópontot szúrnak be a bal oldali részfa jobb oldali gyermekéhez.
Ezt a forgatást akkor hajtják végre, ha egy csomópont egyensúlytényezője –2, a jobboldali gyermeké pedig +1.
Balra – Jobbra Forgatás
Ezt a forgatást akkor hajtják végre, amikor egy új csomópontot szúrnak be a jobb oldali részfa bal oldali gyermekéhez.
Ezt a forgatást akkor hajtják végre, ha egy csomópont egyensúlyi tényezője +2, a bal oldali gyermeké pedig -1.
Beillesztés az AVL fákba
A beszúrási művelet majdnem ugyanaz, mint az egyszerű bináris keresőfákban. Minden behelyezés után kiegyensúlyozzuk a fa magasságát. A beszúrási művelet O(log n) legrosszabb időbonyolultságot igényel.
1 lépés: Szúrja be a csomópontot az AVL fába a BST beillesztési algoritmusával. A fenti példában illessze be a 160-at.
2 lépés: A csomópont hozzáadása után az egyes csomópontok egyensúlytényezője frissül. A 160 beillesztése után minden csomópont egyensúlyi tényezője frissül.
3 lépés: Most ellenőrizze, hogy valamelyik csomópont nem sérti-e az egyensúlytényező tartományát, ha az egyensúlytényező sérül, majd hajtsa végre a forgatást az alábbi esettel. A fenti példában a 350-es egyensúlytényező sérül, és ott az 1-es eset válik alkalmazhatóvá, végrehajtjuk az LL forgatást és a fa újra kiegyensúlyozódik.
- Ha BF(csomópont) = +2 és BF(csomópont -> bal-gyermek) = +1, hajtsa végre az LL elforgatását.
- Ha BF(csomópont) = -2 és BF(csomópont -> jobb oldali gyermek) = 1, hajtsa végre az RR forgatást.
- Ha BF(csomópont) = -2 és BF(csomópont -> jobb oldali gyermek) = +1, hajtsa végre az RL elforgatását.
- Ha BF(csomópont) = +2 és BF(csomópont -> bal oldali gyermek) = -1, hajtsa végre az LR elforgatását.
Törlés az AVL-fákban
A törlés is nagyon egyszerű. Ugyanazzal a logikával töröljük, mint az egyszerű bináris keresési fákban. A törlés után szükség esetén átstrukturáljuk a fát, hogy megtartsuk kiegyensúlyozott magasságát.
Lépés 1: Keresse meg az elemet a fában.
Lépés 2: Törölje a csomópontot a BST törlés szerint.
Lépés 3: Két eset lehetséges: -
Case 1: Törlés a jobb oldali részfáról.
- 1A. Ha BF(csomópont) = +2 és BF(csomópont -> bal-gyermek) = +1, hajtsa végre az LL elforgatását.
- 1B. Ha BF(csomópont) = +2 és BF(csomópont -> bal oldali gyermek) = -1, hajtsa végre az LR elforgatását.
- 1C. Ha BF(csomópont) = +2 és BF(csomópont -> bal-gyermek) = 0, hajtsa végre az LL elforgatását.
Case 2: Törlés a bal oldali részfából.
- 2A. Ha BF(csomópont) = -2 és BF(csomópont -> jobb oldali gyermek) = -1, hajtsa végre az RR forgatást.
- 2B. Ha BF(csomópont) = -2 és BF(csomópont -> jobb oldali gyermek) = +1, hajtsa végre az RL elforgatását.
- 2C. Ha BF(csomópont) = -2 és BF(csomópont -> jobboldali gyermek) = 0, hajtsa végre az RR forgatást.
C++ Példa az AVL fákra
Az alábbiakban a C++ amely AVL fákat valósít meg:
#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);
}
Példa a fenti kód futtatására:
- Másolja ki a fenti kódot, és illessze be az „avl.cpp” fájlba.
- Állítsd össze a kódot:
g++ avl.cpp -o run
- Futtassa a kódot.
./run
Az AVL fák előnyei
- Az AVL fa magassága mindig kiegyensúlyozott. A magasság soha nem nő log N fölé, ahol N a fa csomópontjainak teljes száma.
- Jobb keresési időt biztosít az egyszerű bináris keresési fákhoz képest.
- Az AVL fák önkiegyensúlyozó képességekkel rendelkeznek.
Összegzésként
- Az AVL fák önkiegyensúlyozó bináris keresőfák.
- Az egyensúlytényező az AVL fák alapvető tulajdonsága
- Egy csomópont egyensúlyi tényezője az adott csomópont bal és jobb oldali részfájának magassága közötti különbség.
- Az egyensúlytényező érvényes értékei -1, 0 és +1.
- A beszúrás és törlés művelet az egyensúlyi tényező megsértése után forgatást igényel.
- A beszúrási, törlési és keresési művelet időbeli összetettsége O(log N).
- Az AVL fák követik a bináris keresőfák összes tulajdonságát.
- A bal oldali részfának olyan csomópontjai vannak, amelyek kisebbek, mint a gyökércsomópont. A jobb oldali részfának vannak olyan csomópontjai, amelyek mindig nagyobbak, mint a gyökércsomópont.
- Az AVL fákat ott használják, ahol a keresési műveletek gyakoribbak, mint a beszúrási és törlési műveletek.
