AVL Bäume: Rotationen, Einfügen, Löschen mit C++ Beispiel
Sarah Chen
Was sind AVL-Bäume?
AVL-Bäume sind binäre Suchbäume, bei denen der Unterschied zwischen der Höhe des linken und rechten Teilbaums entweder -1, 0 oder +1 beträgt.
AVL-Bäume werden auch als selbstausgleichende binäre Suchbäume bezeichnet. Diese Bäume helfen dabei, die logarithmische Suchzeit einzuhalten. Es ist nach seinen Erfindern (AVL) Adelson, Velsky und Landis benannt.
Wie funktioniert AVL Tree?
Um die Notwendigkeit von AVL-Bäumen besser zu verstehen, schauen wir uns einige Nachteile einfacher binärer Suchbäume an.
Betrachten Sie die folgenden Schlüssel, die in der angegebenen Reihenfolge in den binären Suchbaum eingefügt werden.
Die Höhe des Baums wächst linear, wenn wir die Schlüssel in aufsteigender Reihenfolge ihres Wertes einfügen. Daher dauert die Suchoperation im schlimmsten Fall O(n).
Die Suche nach einem Element dauert linear; Daher hat es keinen Sinn, das zu verwenden Binärer Suchbaum Struktur. Wenn andererseits die Höhe des Baums ausgeglichen ist, verkürzt sich die Suchzeit.
Schauen wir uns nun die gleichen Schlüssel an, die jedoch in einer anderen Reihenfolge eingefügt wurden.
Hier sind die Schlüssel gleich, aber da sie in einer anderen Reihenfolge eingefügt werden, nehmen sie unterschiedliche Positionen ein und die Höhe des Baums bleibt ausgeglichen. Daher wird die Suche für kein Element des Baums mehr als O(log n) erfordern. Es zeigt sich nun, dass bei korrektem Einsetzen die Baumhöhe im Gleichgewicht gehalten werden kann.
Bei AVL-Bäumen kontrollieren wir die Höhe des Baums während des Einfügevorgangs. Es werden Änderungen vorgenommen, um die ausgeglichene Höhe beizubehalten, ohne die grundlegenden Eigenschaften des binären Suchbaums zu verletzen.
Gleichgewichtsfaktor in AVL-Bäumen
Der Balancefaktor (BF) ist ein grundlegendes Attribut jedes Knotens in AVL-Bäumen, das dabei hilft, die Höhe des Baums zu überwachen.
Eigenschaften des Gleichgewichtsfaktors
- Der Ausgleichsfaktor ist als Differenz zwischen der Höhe des linken Teilbaums und des rechten Teilbaums bekannt.
- Ausgleichsfaktor (Knoten) = Höhe (Knoten->links) – Höhe (Knoten->rechts)
- Zulässige Werte für BF sind –1, 0 und +1.
- Der Wert –1 gibt an, dass der rechte Unterbaum einen zusätzlichen Baum enthält, dh der Baum ist rechts schwer.
- Der Wert +1 gibt an, dass der linke Teilbaum einen zusätzlichen Baum enthält, dh der Baum bleibt schwer.
- Der Wert 0 zeigt an, dass der Baum auf jeder Seite gleiche Knoten enthält, dh der Baum ist perfekt ausbalanciert.
AVL-Rotationen
Um den AVL-Baum ins Gleichgewicht zu bringen, werden beim Einfügen oder Löschen eines Knotens aus dem Baum Rotationen durchgeführt.
Wir führen die folgende LL-Rotation, RR-Rotation, LR-Rotation und RL-Rotation durch.
- Links – Linksdrehung
- Rechts – Rechtsdrehung
- Rechts-Links-Rotation
- Links-Rechts-Rotation
Links – Linksdrehung
Diese Drehung wird durchgeführt, wenn ein neuer Knoten am linken untergeordneten Knoten des linken Teilbaums eingefügt wird.
Es wird eine einzelne Rechtsdrehung durchgeführt. Diese Art der Rotation wird erkannt, wenn ein Knoten einen Ausgleichsfaktor von +2 hat und sein linkes untergeordnetes Element einen Ausgleichsfaktor von +1 hat.
Rechts – Rechtsdrehung
Diese Drehung wird durchgeführt, wenn ein neuer Knoten am rechten untergeordneten Knoten des rechten Teilbaums eingefügt wird.
Es wird eine einzelne Linksdrehung ausgeführt. Diese Art der Rotation wird erkannt, wenn ein Knoten einen Ausgleichsfaktor von -2 und sein rechtes Kind einen Ausgleichsfaktor von -1 hat.
Rechts-Links-Rotation
Diese Drehung wird durchgeführt, wenn ein neuer Knoten am rechten untergeordneten Knoten des linken Teilbaums eingefügt wird.
Diese Rotation wird durchgeführt, wenn ein Knoten einen Ausgleichsfaktor von –2 hat und sein rechtes Kind einen Ausgleichsfaktor von +1 hat.
Links-Rechts-Rotation
Diese Drehung wird durchgeführt, wenn ein neuer Knoten am linken untergeordneten Knoten des rechten Teilbaums eingefügt wird.
Diese Drehung wird durchgeführt, wenn ein Knoten einen Ausgleichsfaktor von +2 hat und sein linkes untergeordnetes Element einen Ausgleichsfaktor von -1 hat.
Einfügen in AVL-Bäume
Der Einfügevorgang ist fast derselbe wie bei einfachen binären Suchbäumen. Nach jedem Einfügen gleichen wir die Höhe des Baums aus. Der Einfügevorgang hat die höchste Zeitkomplexität O(log n).
Schritt 1: Fügen Sie den Knoten mit demselben Einfügealgorithmus wie BST in den AVL-Baum ein. Geben Sie im obigen Beispiel 160 ein.
Schritt 2: Sobald der Knoten hinzugefügt wurde, wird der Ausgleichsfaktor jedes Knotens aktualisiert. Nachdem 160 eingefügt wurde, wird der Ausgleichsfaktor jedes Knotens aktualisiert.
Schritt 3: Überprüfen Sie nun, ob ein Knoten den Bereich des Ausgleichsfaktors verletzt, wenn der Ausgleichsfaktor verletzt wird, und führen Sie dann Drehungen unter Verwendung des folgenden Falls durch. Im obigen Beispiel wird der Balancefaktor von 350 verletzt und Fall 1 wird dort anwendbar, wir führen eine LL-Rotation durch und der Baum wird wieder balanciert.
- Wenn BF(Knoten) = +2 und BF(Knoten -> linkes untergeordnetes Element) = +1, führen Sie eine LL-Rotation durch.
- Wenn BF(Knoten) = -2 und BF(Knoten -> rechtes untergeordnetes Element) = 1, führen Sie eine RR-Rotation durch.
- Wenn BF(Knoten) = -2 und BF(Knoten -> rechtes untergeordnetes Element) = +1, führen Sie eine RL-Rotation durch.
- Wenn BF(Knoten) = +2 und BF(Knoten -> linkes untergeordnetes Element) = -1, führen Sie eine LR-Rotation durch.
Löschen in AVL-Bäumen
Auch das Löschen ist sehr einfach. Wir löschen mit der gleichen Logik wie in einfachen binären Suchbäumen. Nach dem Löschen strukturieren wir den Baum bei Bedarf neu, um seine ausgeglichene Höhe beizubehalten.
Schritt 1: Suchen Sie das Element im Baum.
Schritt 2: Löschen Sie den Knoten gemäß der BST-Löschung.
Schritt 3: Zwei Fälle sind möglich:-
Bei 1: Löschen aus dem rechten Teilbaum.
- 1A. Wenn BF(Knoten) = +2 und BF(Knoten -> linkes untergeordnetes Element) = +1, führen Sie eine LL-Rotation durch.
- 1B. Wenn BF(Knoten) = +2 und BF(Knoten -> linkes untergeordnetes Element) = -1, führen Sie eine LR-Rotation durch.
- 1C. Wenn BF(Knoten) = +2 und BF(Knoten -> linkes untergeordnetes Element) = 0, führen Sie eine LL-Rotation durch.
Fall 2: Aus dem linken Teilbaum löschen.
- 2A. Wenn BF(Knoten) = -2 und BF(Knoten -> rechtes untergeordnetes Element) = -1, führen Sie eine RR-Rotation durch.
- 2B. Wenn BF(Knoten) = -2 und BF(Knoten -> rechtes untergeordnetes Element) = +1, führen Sie eine RL-Rotation durch.
- 2C. Wenn BF(Knoten) = -2 und BF(Knoten -> rechtes untergeordnetes Element) = 0, führen Sie eine RR-Rotation durch.
C++ Beispiel für AVL-Bäume
Unten ist die C++ das AVL-Bäume implementiert:
#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);
}
Beispiel für den obigen Code ausführen:
- Kopieren Sie den obigen Code und fügen Sie „avl.cpp“ ein.
- Kompilieren Sie den Code:
g++ avl.cpp -o run
- Führen Sie den Code aus.
./run
Vorteile von AVL Trees
- Die Höhe des AVL-Baums ist immer ausgeglichen. Die Höhe wächst nie über log N hinaus, wobei N die Gesamtzahl der Knoten im Baum ist.
- Es bietet eine bessere Suchzeitkomplexität im Vergleich zu einfachen binären Suchbäumen.
- AVL-Bäume verfügen über selbstausgleichende Fähigkeiten.
Zusammenfassung
- AVL-Bäume sind selbstausgleichende binäre Suchbäume.
- Der Gleichgewichtsfaktor ist das grundlegende Attribut von AVL-Bäumen
- Der Ausgleichsfaktor eines Knotens ist definiert als die Differenz zwischen der Höhe des linken und rechten Teilbaums dieses Knotens.
- Die gültigen Werte des Ausgleichsfaktors sind -1, 0 und +1.
- Der Einfüge- und Löschvorgang erfordert die Durchführung von Rotationen nach Verletzung des Balancefaktors.
- Die zeitliche Komplexität von Einfüge-, Lösch- und Suchvorgängen beträgt O(log N).
- AVL-Bäume folgen allen Eigenschaften von binären Suchbäumen.
- Der linke Teilbaum hat Knoten, die kleiner als der Wurzelknoten sind. Der rechte Teilbaum hat Knoten, die immer größer als der Wurzelknoten sind.
- AVL-Bäume werden dort verwendet, wo Suchvorgänge häufiger sind als Einfüge- und Löschvorgänge.
