AVL Baum

Hast Du bei sehr starkem Wind einen Baum schon mal biegen sehen? Oder hast Du Dich schon einmal gewundert, wie ein Baum mit vielen Früchten nicht aus der Balance kommt? In der Informatik gibt es eine besondere Baumdatenstruktur, die dafür sorgt, dass ein Baum niemals aus der Balance kommt!

AVL Baum AVL Baum

Erstelle Lernmaterialien über AVL Baum mit unserer kostenlosen Lern-App!

  • Sofortiger Zugriff auf Millionen von Lernmaterialien
  • Karteikarten, Notizen, Übungsprüfungen und mehr
  • Alles, was du brauchst, um bei deinen Prüfungen zu glänzen
Kostenlos anmelden
Inhaltsverzeichnis
Inhaltsangabe

    Hier erfährst Du wie das ganze eigentlich möglich ist und warum dieser Baum beim Suchen von Daten so effizient ist.

    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.

    Den AVL Baum kannst Du auch als AVL-Baum schreiben!

    Ein AVL Baum ist ein ausgeglichener binärer Suchbaum, wobei sich für jeden Knoten die Höhen seines linken und rechten Teilbaumes um maximal eins unterscheiden.

    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.

    Mehr über Suchbäume und seine Variationen findest Du in eigenständigen Erklärungen auf StudySmarter!

    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

    Ein Teilbaum, der nur aus einem Wurzelknoten besteht, hat auch eine Höhe von 1! Hierbei handelt es sich um einen ausgeglichenen Knoten.

    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.

    Es ist wichtig zu erwähnen, dass Eigenschaften wie Suchen, Vorgänger, Nachfolger oder Maximum/Minimum nicht von den modifizierten Einfügen und Entfernen Operationen betroffen sind, wenn die allgemeine Suchbaumeigenschaft weiterhin erhalten bleiben soll.

    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.

    vO beschreibt den oberen Knoten und vU steht für den unteren Knoten. Es wird also stets um den nicht balancierten Knoten rotiert.

    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:

    BF von vO oberer KnotenBF von vU unterer KnotenRotation
    -2-1R-Rotation
    21L-Rotation
    2-1R-L-Rotation
    -21L-R-Rotation

    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.

    Links Rotation

    In diesem Baum siehst Du anhand der Balance-Faktoren, dass sowohl Knoten 5 als auch 6 rechtslastig sind. Bei Knoten 5 ist allerdings das AVL-Kriterium nicht erfüllt. Hier muss eine Links-Rotation angewendet werden:

    Nach der Rotation ist der Baum wieder balanciert und das AVL-Kriterium ist an jedem Knoten erfüllt.

    Rechts-Links-Rotation

    Knoten 5 ist hier rechtslastig und Knoten 13 dafür linkslastig. Anhand der Balance-Faktoren weißt Du, dass Du hier die Rechts-Links-Rotation (R-L-Rotation) anwenden musst.

    Zuerst wird um Knoten 13 (vU) rechts rotiert. Daraufhin entsteht erneut ein unbalancierter Baum, weshalb wieder rotiert werden muss. Diesmal aber links um Knoten 5 (vO)

    Es entsteht wieder ein balancierter, ausgeglichener Baum.

    Links-Rechts-Rotation

    Zuerst wird um Knoten 5 (vU) nach links rotiert. Daraufhin wird um Knoten 13 (vO) nach rechts rotiert.

    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.

    Gegeben ist ein AVL-Baum

    Wenn hier der Knoten 16 gelöscht wird, ist der Baum unbalanciert und es muss rotiert werden. Nach dem Löschen beträgt der Balance-Faktor von Knoten 8 (vO) -2 und der von Knoten 4 (vU) 1. Daher muss eine Links-Rechts-Rotation durchgeführt werden.

    Bei der Links-Rotation rutscht der Knoten 4 links von Knoten 6 und tauscht mit Knoten 5 die Plätze. Da aber 5 größer als 4 ist und wieder einen Platz braucht, wird er rechts von Knoten 4 eingefügt. Dementsprechend erfolgt die Rechts-Rotation um Knoten 8.

    Wieder rutscht Knoten 8 rechts von Knoten 6 und tauscht mit Knoten 7 die Plätze. Da 7 aber kleiner als 8 ist und einen Platz benötigt, wird er an die linke Stelle von Knoten 8 eingefügt.

    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.

    Du findest zu den verschiedenen Bäumen, wie B-Baum oder dem Rot Schwarz Baum jeweils eine eigenständige Erklärung auf StudySmarter!

    AVL-Baum vs. Rot Schwarz Baum

    Ein Rot Schwarz Baum ist ein selbst balancierender binärer Suchbaum, dem jedem Knoten anhand von bestimmten Regeln eine Farbe zugeordnet ist.

    AVL-BaumRot Schwarz Baum
    Sehr strenge Balancierungregeln, die eine schnellere Suche ermöglichenWeniger strenge Balancierungsregeln
    Komplex zu implementieren in der PraxisEinfach zu implementieren
    Jeder Knoten hat ein Balance-FaktorJedem Knoten ist eine Farbe (rot oder schwarz) zugeordnet
    Einfügen und Entfernen erfolgen relativ langsamEinfügen und Entfernen erfolgen zügig
    Die Tiefe zweier Teilbäume unterscheidet sich nie um mehr als 1Längster Pfad ist maximal doppelt so lang wie der kürzeste, nie länger

    Das Suchen liegt in beiden Bäumen im Bereich von O (log n), allerdings ist die Suche in der Praxis bei AVL-Bäumen schneller. Das Einfügen liegt ebenfalls im Bereich von O (log n), da aber der Rot Schwarz Baum seltener balanciert wird, erfolgt das Einfügen und Entfernen schneller.

    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.

    Binärer Suchbaum (BST)AVL-Baum
    Höhe und Tiefe liegen im Bereich von O (n), mit n KnotenHöhe und Tiefe liegen im Bereich von O (log n)
    Suche in einem BST ist ineffizient, da der Baum nicht balanciert istSuche erfolgt aufgrund der Balance effizient
    Beim Einfügen und Entfernen wird das Element nur mit der Wurzel verglichen – es gibt keine Rebalancierungs-OperationenNach jedem Einfügen und Löschen muss die Balance überprüft und eine AVL Rotation durchgeführt werden
    Kein hoher Speicherverbrauch bei den einzelnen OperationenHöherer Speicherverbrauch als bei einem BST, da für jeden Knoten der Balance-Faktor mitgespeichert werden muss

    Das Einfügen in einem BST ist weniger effizient, da ein BST zu einer linearen Liste degenerieren kann.

    AVL Baum – Das Wichtigste

    • Ein AVL-Baum ist ein ausgeglichener binärer Suchbaum, wobei sich für jeden Knoten die Höhen seines linken und rechten Teilbaumes um maximal eins unterscheiden.
    • AVL Baum erstellen: Die Erstellung eines AVL-Baums erfolgt genauso wie bei anderen Suchbäume, allerdings muss die Balance mit beachtet werden.
    • Der Balance-Faktor errechnet sich durch die Höhe (rechten Teilbaumes) - Höhe (linken Teilbaumes) und wird an jedem Knoten vermerkt.
    • AVL Baum Rotation: Es gibt vier Rotationen, die für die Balancierung eines AVL-Baums zuständig sind: Rechts-Rotation, Links-Rotation, Rechts-Links-Rotation, Links-Rechts-Rotation
    • Eine AVL Rotation erfolgt nach dem Einfügen und Löschen.
    • Die Suche innerhalb eines AVL Baum, erfolgt schnell und liegt im Bereich von O (log n).
    • AVL Baum Java: Einen AVL Baum in Java zu implementieren, erfolgt so ähnlich wie bei einem B-Baum, allerdings müssen die Rotationen mit einbezogenen werden, die wiederum etwas komplexer sind.
    • Der Aufwand für das Ausgleichen in einem AVL-Baum ist aufgrund der geringeren Umsortierung deutlich weniger als bei anderen Suchbäumen.

    Nachweise

    1. Ralf Hartmut Güting; Stefan Dieker (2018). Datenstrukturen und Algorithmen. Springer
    2. Prof. Dr.-Ing. Matthias Teschner (2012). Algorithmen und Datenstrukturen Balancierte Suchbäume. cg.informatik.uni-freiburg.de (25.10.2022)
    3. happycoders.eu: AVL-Baum (mit Java-Code). (28.10.2022)
    Häufig gestellte Fragen zum Thema AVL Baum

    Was ist ein AVL Baum?

    Ein AVL Baum ist ein ausgeglichener binärer Suchbaum, wobei sich für jeden Knoten die Höhen seines linken und rechten Teilbaumes um maximal eins unterscheiden.

    Wie ist der Balance-Faktor in einem AVL Baum definiert?

    Der Balance-Faktor ergibt sich aus der Höhe vom rechten Teilbaum - der Höhe vom linken Teilbaum.

    Welchen Zweck erfüllt das Rotieren von Knoten bis hin zu ganzen Teilbäumen?

    Das Rotrieren sorgt dafür, dass ein AVL-Baum stets balanciert ist. Dadurch erfolgt das Suchen innerhalb von AVL Bäumen deutlich schneller als bei anderen Suchbäumen.

    Teste dein Wissen mit Multiple-Choice-Karteikarten

    Die Höhe eines AVL Baumes beträgt O (log n)

    Bei welchem Balancefaktor hat man einen ausgeglichenen Baum?

    Welche Rotation wendest Du an wenn vO gleich -2 und vU gleich 1 ist?

    Weiter
    1
    Über StudySmarter

    StudySmarter ist ein weltweit anerkanntes Bildungstechnologie-Unternehmen, das eine ganzheitliche Lernplattform für Schüler und Studenten aller Altersstufen und Bildungsniveaus bietet. Unsere Plattform unterstützt das Lernen in einer breiten Palette von Fächern, einschließlich MINT, Sozialwissenschaften und Sprachen, und hilft den Schülern auch, weltweit verschiedene Tests und Prüfungen wie GCSE, A Level, SAT, ACT, Abitur und mehr erfolgreich zu meistern. Wir bieten eine umfangreiche Bibliothek von Lernmaterialien, einschließlich interaktiver Karteikarten, umfassender Lehrbuchlösungen und detaillierter Erklärungen. Die fortschrittliche Technologie und Werkzeuge, die wir zur Verfügung stellen, helfen Schülern, ihre eigenen Lernmaterialien zu erstellen. Die Inhalte von StudySmarter sind nicht nur von Experten geprüft, sondern werden auch regelmäßig aktualisiert, um Genauigkeit und Relevanz zu gewährleisten.

    Erfahre mehr
    StudySmarter Redaktionsteam

    Team AVL Baum Lehrer

    • 12 Minuten Lesezeit
    • Geprüft vom StudySmarter Redaktionsteam
    Erklärung speichern

    Lerne jederzeit. Lerne überall. Auf allen Geräten.

    Kostenfrei loslegen

    Melde dich an für Notizen & Bearbeitung. 100% for free.

    Schließ dich über 22 Millionen Schülern und Studierenden an und lerne mit unserer StudySmarter App!

    Die erste Lern-App, die wirklich alles bietet, was du brauchst, um deine Prüfungen an einem Ort zu meistern.

    • Karteikarten & Quizze
    • KI-Lernassistent
    • Lernplaner
    • Probeklausuren
    • Intelligente Notizen
    Schließ dich über 22 Millionen Schülern und Studierenden an und lerne mit unserer StudySmarter App!