Anleitung zu AVL-Bäumen in Java

1. Einleitung

In diesem Tutorial stellen wir den AVL-Baum vor und untersuchen Algorithmen zum Einfügen, Löschen und Suchen nach Werten.

2. Was ist AVL Tree?

Der AVL-Baum, benannt nach seinen Erfindern Adelson-Velsky und Landis, ist ein selbstausgleichender binärer Suchbaum (BST).

Ein selbstausgleichender Baum ist ein binärer Suchbaum, der die Höhe nach dem Einfügen und Löschen gemäß einigen Ausgleichsregeln ausgleicht.

Die Zeitkomplexität eines BST im ungünstigsten Fall ist eine Funktion der Höhe des Baums. Insbesondere der längste Pfad von der Wurzel des Baums zu einem Knoten. Nehmen wir für eine BST mit N Knoten an, dass jeder Knoten nur null oder ein Kind hat. Daher ist seine Höhe gleich N und die Suchzeit im schlimmsten Fall ist O (N). Unser Hauptziel bei einer BST ist es daher, die maximale Höhe nahe am log (N) zu halten.

Der Ausgleichsfaktor des Knotens N ist Höhe (rechts (N)) - Höhe (links (N)) . In einem AVL-Baum kann der Ausgleichsfaktor eines Knotens nur einer von 1, 0 oder -1 Werten sein.

Definieren wir ein Knotenobjekt für unseren Baum:

public class Node { int key; int height; Node left; Node right; ... }

Als nächstes definieren wir den AVLTree :

public class AVLTree { private Node root; void updateHeight(Node n) { n.height = 1 + Math.max(height(n.left), height(n.right)); } int height(Node n) { return n == null ? -1 : n.height; } int getBalance(Node n) { return (n == null) ? 0 : height(n.right) - height(n.left); } ... }

3. Wie balanciere ich einen AVL-Baum?

Der AVL-Baum überprüft den Ausgleichsfaktor seiner Knoten nach dem Einfügen oder Löschen eines Knotens. Wenn der Ausgleichsfaktor eines Knotens größer als eins oder kleiner als -1 ist, gleicht sich der Baum neu aus.

Es gibt zwei Operationen, um einen Baum neu auszugleichen:

  • Rechtsdrehung und
  • Linksdrehung.

3.1. Rechtsdrehung

Beginnen wir mit der richtigen Drehung.

Angenommen, wir haben eine BST namens T1 mit Y als Wurzelknoten, X als linkem Kind von Y und Z als rechtem Kind von X. Angesichts der Eigenschaften einer BST wissen wir, dass X <Z <Y.

Nach einer Rechtsdrehung von Y haben wir einen Baum namens T2 mit X als Wurzel und Y als rechtem Kind von X und Z als linkem Kind von Y. T2 ist immer noch eine BST, da es die Reihenfolge X <Z <Y beibehält .

Werfen wir einen Blick auf die richtige Rotationsoperation für unseren AVLTree :

Node rotateRight(Node y) { Node x = y.left; Node z = x.right; x.right = y; y.left = z; updateHeight(y); updateHeight(x); return x; }

3.2. Linksdrehung

Wir haben auch eine Linksdrehung.

Angenommen, eine BST namens T1 mit Y als Wurzelknoten, X als rechtem Kind von Y und Z als linkem Kind von X. Vor diesem Hintergrund wissen wir, dass Y <Z <X.

Nach einer Linksdrehung von Y haben wir einen Baum namens T2 mit X als Wurzel und Y als linkem Kind von X und Z als rechtem Kind von Y. T2 ist immer noch eine BST, da es die Reihenfolge Y <Z <X beibehält .

Werfen wir einen Blick auf die Linksdrehung für unseren AVLTree :

Node rotateLeft(Node y) { Node x = y.right; Node z = x.left; x.left = y; y.right = z; updateHeight(y); updateHeight(x); return x; }

3.3. Rebalancing-Techniken

Wir können die Operationen zur Rechts- und Linksrotation in komplexeren Kombinationen verwenden, um den AVL-Baum nach jeder Änderung seiner Knoten im Gleichgewicht zu halten . In einer unsymmetrischen Struktur hat mindestens ein Knoten einen Ausgleichsfaktor von 2 oder -2. Mal sehen, wie wir den Baum in diesen Situationen ausbalancieren können.

Wenn der Ausgleichsfaktor des Knotens Z 2 ist, befindet sich der Teilbaum mit Z als Wurzel in einem dieser beiden Zustände, wobei Y als das richtige Kind von Z betrachtet wird.

Im ersten Fall ist die Größe des rechten Kindes von Y (X) größer als die Höhe des linken Kindes (T2). Wir können den Baum leicht durch eine Linksdrehung von Z wieder ausbalancieren.

Für den zweiten Fall ist die Größe des rechten Kindes von Y (T4) geringer als die Größe des linken Kindes (X). Diese Situation erfordert eine Kombination von Rotationsoperationen.

In diesem Fall drehen wir zuerst Y nach rechts, damit der Baum die gleiche Form wie im vorherigen Fall erhält. Dann können wir den Baum durch eine Linksdrehung von Z neu ausbalancieren.

Wenn der Ausgleichsfaktor des Knotens Z -2 ist, befindet sich sein Teilbaum in einem dieser beiden Zustände, sodass wir Z als Wurzel und Y als linkes Kind betrachten.

Die Höhe im linken Kind von Y ist größer als die des rechten Kindes, daher gleichen wir den Baum mit der rechten Drehung von Z aus.

Oder im zweiten Fall hat das rechte Kind von Y eine größere Größe als sein linkes Kind.

Zuerst transformieren wir es mit einer Linksdrehung von Y in die frühere Form, dann balancieren wir den Baum mit der Rechtsdrehung von Z.

Werfen wir einen Blick auf die Neuausgleichsoperation für unseren AVLTree :

Node rebalance(Node z) { updateHeight(z); int balance = getBalance(z); if (balance > 1) { if (height(z.right.right) > height(z.right.left)) { z = rotateLeft(z); } else { z.right = rotateRight(z.right); z = rotateLeft(z); } } else if (balance  height(z.left.right)) z = rotateRight(z); else { z.left = rotateLeft(z.left); z = rotateRight(z); } } return z; }

Wir verwenden die Neuverteilung nach dem Einfügen oder Löschen eines Knotens für alle Knoten im Pfad vom geänderten Knoten zum Stamm.

4. Fügen Sie einen Knoten ein

Wenn wir einen Schlüssel in den Baum einfügen, müssen wir seine richtige Position finden, um die BST-Regeln zu übergeben. Wir beginnen also mit der Wurzel und vergleichen ihren Wert mit dem neuen Schlüssel. Wenn der Schlüssel größer ist, gehen wir weiter nach rechts - andernfalls gehen wir zum linken Kind.

Sobald wir den richtigen übergeordneten Knoten gefunden haben, fügen wir den neuen Schlüssel je nach Wert links oder rechts als Knoten hinzu.

Nach dem Einfügen des Knotens haben wir eine BST, aber möglicherweise ist es kein AVL-Baum. Daher überprüfen wir die Ausgleichsfaktoren und gleichen die BST für alle Knoten im Pfad vom neuen Knoten zur Wurzel neu aus.

Werfen wir einen Blick auf die Einfügeoperation:

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 RuntimeException("duplicate Key!"); } return rebalance(node); }

Es ist wichtig zu beachten, dass ein Schlüssel im Baum eindeutig ist - keine zwei Knoten teilen sich denselben Schlüssel.

Die zeitliche Komplexität des Einfügealgorithmus ist eine Funktion der Höhe. Da unser Baum ausgeglichen ist, können wir davon ausgehen, dass die Zeitkomplexität im schlimmsten Fall O (log (N)) ist.

5. Löschen Sie einen Knoten

Um einen Schlüssel aus dem Baum zu löschen, müssen wir ihn zuerst in der BST finden.

Nachdem wir den Knoten (Z genannt) gefunden haben, müssen wir den neuen Kandidaten als Ersatz für den Baum einführen. Wenn Z ein Blatt ist, ist der Kandidat leer. Wenn Z nur ein Kind hat, ist dieses Kind der Kandidat, aber wenn Z zwei Kinder hat, ist der Prozess etwas komplizierter.

Assume the right child of Z called Y. First, we find the leftmost node of the Y and call it X. Then, we set the new value of Z equal to X ‘s value and continue to delete X from Y.

Finally, we call the rebalance method at the end to keep the BST an AVL Tree.

Here is our delete method:

Node 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; }

The time complexity of the delete algorithm is a function of the height of the tree. Similar to the insert method, we can assume that time complexity in the worst case is O(log(N)).

6. Search for a Node

Searching for a node in an AVL Tree is the same as with any BST.

Start from the root of the tree and compare the key with the value of the node. If the key equals the value, return the node. If the key is greater, search from the right child, otherwise continue the search from the left child.

Die zeitliche Komplexität der Suche ist eine Funktion der Höhe. Wir können davon ausgehen, dass die Zeitkomplexität im schlimmsten Fall O (log (N)) ist.

Sehen wir uns den Beispielcode an:

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

7. Fazit

In diesem Tutorial haben wir einen AVL-Baum mit Einfüge-, Lösch- und Suchvorgängen implementiert.

Wie immer finden Sie den Code auf Github.