Kurs:Algorithmen und Datenstrukturen/Vorlesung/AVL Bäume
AVL Bäume
BearbeitenAuf dieser Seite werden AVL Bäume behandelt. Ein Suchbaum erfordert nach Einfügen oder Löschen von Knoten einen Ausgleich, da sie sonst entarten. AVL steht für die russischen Mathematiker Adelson-Velskii und Landis. Liegt ein binärer Suchbaum mit AVL Kriterium vor, bedeutet das, dass für jeden inneren Knoten gilt: Die Höhe des linken und rechten Teilbaums differieren maximal um 1. Es reicht nicht diese Bedingung nur für die Wurzel zu fordern, da beide Teilbäume der Wurzel entartet sein könnten.
Als Lösungsidee gibt es zwei Ansätze. Zum einen ein abgeschwächtes Kriterium für die ausgeglichene Höhe, beispielsweise AVL Bäume und zum anderen eine ausgeglichene Höhe, aber ein unausgeglichener Verzweigungsgrad. Dabei können wir eine direkte Realisierung als Mehrwegbäume, beispielsweise B-Bäume, nutzen, oder eine Kodierung als binären Baum, beispielsweise Rot-Schwarz-Bäume.
AVL Eigenschaften
Bearbeiten
Höhe von AVL Bäumen
BearbeitenWie viele Knoten hat ein AVL Baum der Höhe h mindestens? Bei einer rekursiven Beziehung ist , d.h der Baum hat nur eine Wurzel. Bei , das heißt der Baum hat nur einen Zweig und bei , das heißt der Baum hat mehr Zweige. Daraus lässt sich allgemein sagen, dass . Damit wächst der Baum vergleichbar mit der Fibonacci Reihe.
Einfügen in AVL Baum
BearbeitenDas Einfügen eines Schlüssels erfolgt mit den üblichen Algorithmen. Es kann aber passieren, dass danach die AVL Eigenschaft verletzt ist. Die Balance ist definiert als left.height-right.height. Als AVL Eigenschaft muss die Balance sein. Nach Einfügen ist die Balance aber Reparieren kann man das Ganze mittels Rotation und Doppelrotation.
Fallunterscheidung
BearbeitenBeim Einfügen kann man in verschiedene Fälle unterteilen. Eine Verletzung der AVL Eigenschaft tritt ein bei
- Einfügen in linken Teilbaum des linken Kindes
- Einfügen in rechten Teilbaum des linken Kindes
- Einfügen in linken Teilbaum des rechten Kindes
- Einfügen in rechten Teilbaum des rechten Kindes
1 und 4 sowie 2 und 3 sind symmetrische Problemfälle.
Einfache Rotation
BearbeitenWir haben eine Rotation mit linkem Kind nach rechts oder rechtem Kind nach links.
Doppelrotation
BearbeitenWir haben eine Doppelrotation mit linkem Kind nach rechts oder rechtem Kind nach links.
Beispiel
BearbeitenIm Folgenden werden wir die Rotation an einem Beispiel veranschaulichen.
insert 3, 2, 1
→ einfache Rotation nach rechts (2,3)
insert 4, 5
→ einfache Rotation nach links (4,3)
insert 6
→ einfache Rotation (Wurzel) nach links (4,2)
insert 7
→ einfache Rotation nach links (6,5)
insert 16, 15
→ Doppelrotation nach links (7,15,15)
insert 13+12+11+10
→ jeweils einfache Rotation
insert 8, 9
→ Doppelrotation nach rechts
Eine Verletzung der AVL-Eigenschaft tritt ein
- Beim Einfügen in linken Teilbaum des linken Kindes, dann muss eine Rotation mit dem linkem Kind erfolgen
- Beim Einfügen in rechten Teilbaum des linken Kindes, dann muss eine Doppelrotation mit dem linken Kind erfolgen
- Beim Einfügen in linken Teilbaum des rechten Kindes, dann muss eine Doppelrotation mit dem rechten Kind erfolgen
- Beim Einfügen in rechten Teilbaum des rechten Kindes, dann muss eine Rotation mit dem rechten Kind erfolgen
Implementation
BearbeitenDie Implementierung ist ähnlich des binären Suchbaums. Der Aufruf um einen neuen Knoten hinzuzufügen geschieht dabei mit AvlTree.insert(K k).
public class AvlTree<K extends Comparable<K>> {
private AvlTreeNode<K> head;
private AvlTreeNode<K> nullNode; //Neuer Knotentyp
public AvlTree(){
head = new AvlTreeNode<K>(null);
nullNode = new AvlTreeNode<K>(null);
nullNode.setLeft(nullNode);
nullNode.setRight(nullNode);
head.setRight(nullNode);
}
public boolean insert(K k){
AvlTreeNode<K> parent = head;
AvlTreeNode<K> child = head.getRight();
while(child != nullNode){
parent = child;
int cmp = child.getKey().compareTo(k);
if(cmp == 0)
return false;
else if (cmp > 0)
child = child.getLeft();
else
child = child.getRight();
}
AvlTreeNode<K> node = new AvlTreeNode<K>(k);
node.setLeft(nullNode);
node.setRight(nullNode);
node.setParent(parent);
if(parent.compareTo(node) > 0)
parent.setLeft(node);
else
parent.setRight(node);
//Nach der Einfügung die Balance ggfs. reparieren
parent.repair(node, nullNode);
return true;
}
}
Die Knotenimplementierung ist zu Beginn genauso wie beim binären Suchbaum. Die Methoden balance() und height() dienen als Hilfe für die Balance. Weiterhin wird die Methode repair() zur Reparatur der Balance benötigt. Sie testet, ob die Balance für den aktuellen Knoten (this) verletzt ist und repariert diese gegebenenfalls.
class AvlTreeNode<K extends Comparable<K>>{
K key;
private AvlTreeNode<K> left;
private AvlTreeNode<K> right;
private AvlTreeNode<K> parent; //für jeden Knoten merken wir uns nun den Elternknoten
public AvlTreeNode(K key){
this.left = null;
this.right = null;
this.parents = null;
this.key = key;
}
public AvlTreeNode<K> getLeft() { return left; }
public AvlTreeNode<K> getRight() { return right; }
public K getKey() { return key; }
public void setLeft(AvlTreeNode<K> n) { left = n; }
public void setRight(AvlTreeNode<K> n) { right = n; }
public void setParent(AvlTreeNode<K> n) { parent = n; }
public int compareTo(AvlTreeNode<K> other){
return (this.key == null) ? -1 : this.key.compareTo(other.key);
}
//Positive Balance, falls linker Teilbaum größer als der rechte Teilbaum
//Negative Balance, falls rechter Teilbaum größer als der linke Teilbaum
//Balance = 0, falls ausgeglichen
public int balance(){
if(this.key == null) //Nullknoten sind stets ausgeglichen
return 0;
return this.left.height() - this.right.height();
}
//Gibt die Länge des längsten Pfades zu einem Blatt wieder
public int height(){
if(this.key == null) //Nullknoten haben die Höhe 0
return 0;
return Math.max(this.left.height(), this.right.height()) + 1;
}
//Es werden die zwei nachfolgenden Knoten auf dem Pfad der Einfügung übergeben
//man startet vom Punkt der Einfügung, einem Blatt und arbeitet sich von unten nach oben
public void repair(AvlTreeNode<K> child, AvlTreeNode<K> grandchild){
//Falls wie am head angekommen sind, terminieren wir
if(this.key == null)
return;
//Fall 1: Einfügen im linken Teilbaum des linken Kindes
if(this.balance() > 1 && child.balance() > 0){
child.parent = this.parent;
this.parent = child;
this.left = child.right;
child.right = this;
if(child.parent.left == this)
child.parent.left = child;
else child.parent.right = child;
}
//Fall 2: Einfügung im rechten Teilbaum des linken Kindes
if(this.balance() > 1 && child.balance() < 0){
grandchild.parent = this.parent;
this.parent = grandchild;
this.left = grandchild.right;
this.left.parent = this;
grandchild.right = this;
child.right = grandchild.left;
child.right.parent = child;
grandchild.left = child;
child.parent = grandchild;
if(grandchild.parent.left == this)
grandchild.parent.left = grandchild;
else grandchild.parent.right = grandchild;
}
//Fall 3 und 4 wären analog
//Fahre rekursiv mit Elternknoten fort
this.parent.repair(this, child);
}
}
Literatur
BearbeitenDa die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 14.4.2 zu finden.
