Wie funktioniert ein AVL Baum?
Definition. Bei einem AVL Baum handelt es sich in der Informatik um eine Datenstruktur. Dabei geht es um einen binären Suchbaum, dessen Höhe sich bei jedem Knoten beider Teilbäume um maximal eins unterscheidet – also ausgeglichen bzw. höhenbalanciert ist.
Wann ist ein AVL Baum ein binärer Suchbaum?
Definition: Ein binärer Suchbaum heißt AVL-Baum oder höhenbalanciert, wenn sich für jeden Knoten die Höhe seines rechten Teilbaums und die Höhe seines linken Teilbaums um maximal eins unterscheiden.
Was ist ein vollständiger Baum?
Man bezeichnet volle Binärbäume als vollständig, wenn alle Blätter die gleiche Tiefe haben, wobei die Tiefe eines Knotens als die Anzahl der Bögen bis zur Wurzel definiert ist. Der Binärbaum wird entartet genannt, wenn jeder Knoten entweder Blatt ist (Anzahl Kinder ist 0) oder Halbblatt (Anzahl Kinder ist 1).
Wann ist ein binärbaum voll?
Man bezeichnet volle Binärbäume als vollständig, wenn alle Blätter die gleiche Tiefe haben, wobei die Tiefe eines Knotens als die Anzahl der Bögen bis zur Wurzel definiert ist.
Wie ist die Höhe in einem AVL-Baum gemittelt?
Dabei ist die Höhe gemittelt über alle zufälligen Einfügungen in einen AVL-Baum vorgegebener Größe näher bei der unteren als bei der oberen Grenze des Intervalls. Werden der Datenstruktur AVL-Baum Operationen zum Zugriff und zur Verwaltung beigegeben, so werden diese nur dann als zugehörig angesehen, wenn sie die AVL-Eigenschaft aufrechterhalten.
Was sind die wichtigsten Operationen beim AVL-Baum?
Die wichtigsten Operationen bei den Suchbäumen – und damit beim AVL-Baum – sind: Suchen einerseits sowie Einfügen und Löschen andererseits. Mit der Eigenschaft, dass alle diese Operationen im schlechtesten Fall ( Worst Case) logarithmische Komplexität haben, gehört der AVL-Baum zu den höhenbalancierten binären Suchbäumen.
Was sind die Angaben zur Komplexität der AVL-Bäume?
Die dortigen Angaben zur Komplexität gelten genauso für AVL-Bäume, mit der Präzisierung, dass die Höhe des AVL-Baums sich logarithmisch zur Anzahl der Knoten verhält. Das Suchen (englisch: find, search, lookup oder locate) eines Elements anhand seines Schlüssels ist die wichtigste unter den Navigationsoperationen.
Was geschieht mit der AVL-Bedingung?
Mit -2 ist die AVL-Bedingung also verletzt und der Baum muss entsprechend umgebaut werden. Das geschieht mit einer sogenannten Rechtsrotation des Knotens, der die Bedingung verletzt und desjenigen darunter. In diesem Fall müssen also die 2 und die 3 nach rechts rotieren: Die 2 wird dadurch zum Elternknoten und die 3 zum rechten Kindknoten.