AVL Baum

AVL Baum Bedeutung

Binäre Suchbäume gibt es viele. Allerdings ist der AVL-Baum die älteste Datenstruktur für binäre Suchbäume und wurde im Jahr 1962 von den sowjetischen Mathematikern Georgi Maximowitsch Adelson-Velski und Jewgeni Michailowitsch Landis vorgestellt.

Dabei hat ein AVL-Baum modifizierte Einfügen und Entfernen Operationen, die dafür sorgen, dass die Balance aufrechterhalten bleibt. Das bedeutet, dass nach jeder Operation, die Struktur überprüft wird und je nach Bedürfnis durch sogenannte Rebalancierungs-Operationen, auch Rotationen genannt, der Baum wieder ausgeglichen wird.

Was es mit dem Balancieren und der Rotation auf sich hat, wirst Du in den folgenden Abschnitten erfahren. Zunächst erfährst Du aber etwas über die Struktur eines AVL Baum!

Höhe eines AVL-Baums

Die Ausgeglichenheit eines AVL-Baums sorgt dafür, dass die Höhe des Suchbaumes stets O (log n) ist. Damit sind auch alle anderen Operationen mit O (log n) ausführbar.

Eine Eigenschaft des AVL Baumes ist, dass jeder Knoten einen Balance-Faktor besitzt. Dieser ergibt sich aus folgende Formel:

Höhe (rechter Teilbaum) - Höhe (linker Teilbaum) ∈ {-1, 0, 1}

Es ist wichtig, drei Fälle zu unterscheiden:

1. Rechtslastiger Knoten bei einem Balance-Faktor von > 0
2. Linkslastigen Knoten bei einem Balance-Faktor von < 0
3. Ausgeglichener Knoten bei einem Balance-Faktor von 0

AVL Baum Beispiel

Anhand eines bildlichen AVL Baum Beispiels kannst Du Dir die Datenstruktur etwas deutlicher vorstellen:

In Abb. 1 siehst Du, wie die Balance an jedem Knoten vorgemerkt ist. Beim rechten Baum ist das AVL-Kriterium von (-1 ≤ BF ≤ 1) an Knoten 4 verletzt, weshalb es sich hier nur um einen binären Suchbaum handelt. Der Suchbaum ist nicht balanciert, da die Differenz der Höhe vom rechten und linken Teilbaum größer als eins ist. Die absolute Höhe ist dabei nicht interessant.

AVL Baum Rotation

"Rebalancierungs-Operationen" sind spezielle Rotationen, welche die Balance eines AVL Baumes gewährleisten.

Insgesamt gibt es vier Rotationen, Du Dir merken musst:

1. Rechts Rotation um vO (R-Rotation)
2. Links Rotation um vO (L-Rotation)
3. Links-Rechts-Rotation; Links Rotation um vU, dann R-Rot um vO (L-R-Rotation)
4. Rechts-links-Rotation; R-Rot um vU; dann L-Rot um vO (R-L-Rotation)

Außerdem kannst Du Dir noch merken, dass Rotationen, bei denen nur einmal rotiert wird, Einfachrotationen heißen. Wenn zweimal rotiert wird, heißt dies dementsprechend auch Doppelrotation.

Bei den Rotationen ist es wichtig den Balance-Faktor (BF) zu beachten, damit Du weißt, welche Rotation Du anwenden musst.

Folgende Tabelle kann Dir dabei einen Überblick verschaffen:

AVL Baum Einfügen

Das Einfügen in einem AVL-Baum geschieht wie in einem normalen binären Suchbaum. Die Zahl 13 ist der Startknoten und daraufhin werden die Zahlen 6 und 5 eingefügt. Da die Zahl 6 kleiner als 13 ist, wird sie links von 13 eingefügt. Dasselbe passiert auch mit der Zahl 5. Zudem werden auch die Balance-Faktoren mit notiert.

Wenn Du jetzt jeden Knoten einzeln betrachtest, dann kannst Du Dir Folgendes notieren:

• Knoten 15 hat einen Balance-Faktor von 0.
• Knoten 6 hat einen Balance-Faktor von -1; Knoten 6 ist also linkslastig. Das AVL-Kriterium (-1 ≤ BF ≤ 1) ist allerdings erfüllt.
• Der Balance-Faktor an Knoten 13 beträgt -2; das AVL-Kriterium ist nicht erfüllt und es muss rotiert werden.

Mithilfe der oberen Tabelle siehst Du, dass eine Rechts-Rotation angewendet werden muss. Der Knoten 6 (vU) muss um 13 (vO) rotiert werden.

Knoten 6 ist aktuell die neue Wurzel und wenn Du jetzt die einzelnen Balance-Faktoren notierst, merkst Du, dass der Baum sowohl balanciert als auch ausgeglichen ist.

Also eigentlich ganz einfach, nicht wahr?

Bei den anderen Rotationen geschieht es ähnlich.

AVL Baum Löschen

Sicherlich möchtest Du auch wissen, wie ein Knoten aus einem AVL-Baum gelöscht werden kann. Auch dies läuft nach dem gleichen Prinzip wie das Einfügen ab.

Zuerst löschst Du Deinen Knoten und danach musst Du rebalancieren. Außerdem musst Du darauf achten, dass Du eventuell Knoten evtl. neu einordnen musst, wenn Du rotierst.

AVL Baum erstellen

Du hast eben gelernt, wie ein AVL-Baum erstellt wird. Du folgst den Prinzipen eines Suchbaumes und balancierst je nach Bedarf. Wie diese Datenstruktur aber implementiert wird, siehst Du im folgenden Abschnitt.

AVL Baum Java

Die Basis Implementierung von einem AVL Baum in Java unterscheidet sich kaum von dem eines normalen binären Suchbaumes. Allerdings müssen die Operationen später modifiziert werden.

Zu Beginn wird der Startknoten (Wurzel), hier auch „Node“ genannt, implementiert:

class Node {
    int data;
    Node left;
    Node right;
    int height;

  public Node(int data) {
    this.data = data;
  }
}

Der AVL-Baum wird durch die Klasse AvlTree implementiert:

class Node {

    int data;
    int height; //speichern der Höhe
    Node left;
    Node right;

    public Node (int data) {

        this.data = data

    }

}

// 3 Methoden für das Balancieren der AVL-Bäume

class AVLTree {

    private Node root;

    int height(Node node) {
    return node != null ? node.height : -1;
    }

    
    void updateHeight(Node node) {

        int leftChild = height(node.left);
        int rightChild = height(node.right);
        node.height = max(leftChild, rightChild) +1;
    }

    int balanceFactor(Node node) {
        return height(node.right) - height(node.left);        
    }    

    // RechtsRotation

    Node rotateRight (Node node) { 
        Node leftChild = node.left; // Merken des Linken Knotens/Kind LeftChild von node 
        node.left = leftChild.right;
        leftChild.right = node;

        // ersetzen des linken Kindes von node durch das rechte Kind des linken Kindes leftChild.right
        // node wird danach als das neue rechte Kind von dem linken Kind gesetzt

        updateHeight(node);
        updateHeight(leftChild);   
        return leftChild;
    }

    // LinksRotation

    Node rotateLeft (Node node) {
        Node rightChild = node.left;
        node.right = rightChild.left;
        rightChild.left = node;
    
        updateHeight(node);
        updateHeight(rightChild);       
        return rightChild;
    }
   
    // Implementierung der Rebalance Operationen durch das Betrachten der einzelnen Fälle:

    Node rebalance(Noded node) {
        updateHeight(node);    
        int balance = BalanceFactor(node);    
        if (balance < -1) {
            if (balanceFactor(node.left) <= 0) {

                // RechtsRotation:

                node.rotateRight(node);

            } else {

                // Links-Rechts-Rotation:

                node.left = rotateLeft(node.left);
                node = rotateRight(node);
            }
        }

         // Überprüfen, ob der Teilbaum rechtslastig ist       

        if (balance > 1) {
            if (balanceFactor(node.right) >= 0) {

                //LinksRotation

                node = rotateLeft(node);

            } else {

                // Rechts-Links-Rotation:

                node.right = rotateRight(node.right);
                node = rotateLeft(node);
            }
        }
        return node;
    }
   
    // Einfügen funktioniert so ähnlich wie bei einem B-Baum

    Node insert(Node node, int key) {
        if (node == null) {
            return new Node(key);    

        } else if (node.key > key) {
            node.left = insert(node.left, key);

        } else if (node.key < key){
            node.right = insert(node.right, key);    

        } else {
            throw new Runtime Exception("duplicate Key!");
        }
        return rebalance(node);
    }

    Noide delete(Node node, int key) {
        if (node == null) {
            return node;

        } else if (node.key > key) {
            node.left = delete(node.left, key);

        } else if (node.key < key) {
            node.right = delete(node.right, key);

        } else {
            if (node.left == null || node.right == null) {
                node = (node.left == null) ? node.right : node.left;

            } else {
               Node mostLeftChild = mostLeftChild(node.right);
                node.key = mostLeftChild.key;
                node.right = delete(node.right, node.key);               
            }
        }   

        if (node != null) {
            node = rebalance(node);            
        }

        return node;        
        
        Node find(int key) {
            Node current = root;
            while (current != null) {
            if (current.key == key) {
                break;
            }
            cuurent = current.key < key ? current.right : current.left;
        }
        return current;
    }
 }    
}

AVL Baum – Vergleich zu anderen Suchbäumen

In der Informatik ist der Suchbaum eine abstrakte Datenstruktur, dessen Elemente in der Form von geordneten Bäumen gespeichert sind. Dabei heißt ein (Binär) Baum ausgeglichen oder balanciert, wenn er bei n Knoten eine Höhe in der Größenordnung von O (log n) hat.

Dir sollten die Unterschiede der jeweiligen Suchbäume bewusst sein, weshalb in den folgenden Abschnitten die Differenzen noch einmal dargestellt werden.

AVL-Baum vs. Rot Schwarz Baum

AVL-Baum vs. Binärer Suchbaum

Ein Binärer Suchbaum (BST) ist ein binärer Baum (B-Baum), dessen Elemente im Linken Teilbaum kleiner als seine Wurzel sind und alle Elemente im rechten Teilbaum größer als seine Wurzel sind. Damit ist auch jeder AVL-Baum gleichzeitig ein BST Baum. Umgekehrt ist dies aber nicht der Fall.

Weitere Unterschiede zwischen einem Binären Suchbaum und einem AVL-Baum siehst Du in folgender Tabelle.