So implementieren Sie den AVL-Baumalgorithmus mit Java

So implementieren Sie den AVL-Baumalgorithmus mit Java

Einführung:
Der AVL-Baum ist ein selbstausgleichender binärer Suchbaum, der während Einfüge- und Löschvorgängen automatisch einen Ausgleich durchführen kann, um sicherzustellen, dass die Höhe des Baums immer beibehalten wird . in einem kleineren Rahmen. In diesem Artikel erfahren Sie, wie Sie den AVL-Baumalgorithmus mit Java implementieren und stellen konkrete Codebeispiele bereit.

1. Grundlegende Beschreibung und Eigenschaften des AVL-Baums:
Der AVL-Baum wurde 1962 von G. M. Adelson-Velsky und Evgenii Landis vorgeschlagen. Im AVL-Baum darf der Höhenunterschied zwischen seinem linken und rechten Teilbaum 1 nicht überschreiten. Wenn der Wert 1 überschreitet, ist für den automatischen Ausgleich ein Rotationsvorgang erforderlich. Im Vergleich zu gewöhnlichen binären Suchbäumen weisen AVL-Bäume eine bessere Such-, Einfügungs- und Löschleistung auf.

2. Knotenimplementierung des AVL-Baums:
In Java können wir benutzerdefinierte Knotenklassen verwenden, um AVL-Bäume zu implementieren. Jeder Knoten enthält einen Wert und einen Verweis auf den linken und rechten Teilbaum sowie eine Variable zum Aufzeichnen der Höhe des Knotens.

class AVLNode {
    int val;
    AVLNode left, right;
    int height;

    AVLNode(int val) {
        this.val = val;
        this.height = 1;
    }
}

3. Knotenhöhe berechnen:
Bevor wir den AVL-Baumalgorithmus implementieren, benötigen wir eine Funktion zur Berechnung der Knotenhöhe. Diese Funktion ermittelt die Höhe des aktuellen Knotens, indem sie die Höhe des linken Teilbaums und des rechten Teilbaums rekursiv berechnet und dann den größeren Wert der beiden nimmt und 1 addiert.

int getHeight(AVLNode node) {
    if (node == null) {
        return 0;
    }
    return Math.max(getHeight(node.left), getHeight(node.right)) + 1;
}

4. Implementieren Sie die Rotationsoperation des AVL-Baums:
Beim Einfügen und Löschen von Operationen muss der AVL-Baum gedreht werden, um das Gleichgewicht des Baums aufrechtzuerhalten. Wir werden sowohl Links- als auch Rechtshandoperationen implementieren.

1. Linksrotationsoperation:
   Linksrotation dient dazu, den rechten Teilbaum des aktuellen Knotens zum neuen Wurzelknoten zu befördern. Der ursprüngliche Wurzelknoten wird zum linken Teilbaum des neuen Wurzelknotens und der linke Teilbaum des ursprünglichen neuen Wurzelknotens wird zum rechten Teilbaum des ursprünglichen Wurzelknotens.

AVLNode leftRotate(AVLNode node) {
    AVLNode newRoot = node.right;
    AVLNode temp = newRoot.left;

    newRoot.left = node;
    node.right = temp;

    node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
    newRoot.height = Math.max(getHeight(newRoot.left), getHeight(newRoot.right)) + 1;

    return newRoot;
}

2. Rechtsrotationsoperation:
   Rechtsrotation besteht darin, den linken Teilbaum des aktuellen Knotens zum neuen Wurzelknoten zu befördern, der ursprüngliche Wurzelknoten wird zum rechten Teilbaum des neuen Wurzelknotens und der rechte Teilbaum des ursprünglichen neuen Der Wurzelknoten wird zum Original. Der linke Teilbaum des Wurzelknotens.

AVLNode rightRotate(AVLNode node) {
    AVLNode newRoot = node.left;
    AVLNode temp = newRoot.right;

    newRoot.right = node;
    node.left = temp;

    node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
    newRoot.height = Math.max(getHeight(newRoot.left), getHeight(newRoot.right)) + 1;

    return newRoot;
}

5. Implementierung des Einfügevorgangs:
Beim Einfügen eines neuen Knotens wird dieser zunächst gemäß den Regeln des binären Suchbaums eingefügt und dann entsprechend dem Ausgleichsfaktor des Knotens auf dem Einfügepfad angepasst umfasst Rotationsoperationen und die Aktualisierung von Knoten.

AVLNode insert(AVLNode node, int val) {
    if (node == null) {
        return new AVLNode(val);
    }

    if (val < node.val) {
        node.left = insert(node.left, val);
    } else if (val > node.val) {
        node.right = insert(node.right, val);
    } else {
        // 如果节点已经存在，不进行插入
        return node;
    }

    node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;

    int balanceFactor = getBalanceFactor(node);

    // 左左情况，需要进行右旋
    if (balanceFactor > 1 && val < node.left.val) {
        return rightRotate(node);
    }

    // 左右情况，需要进行左旋后再进行右旋
    if (balanceFactor > 1 && val > node.left.val) {
        node.left = leftRotate(node.left);
        return rightRotate(node);
    }

    // 右右情况，需要进行左旋
    if (balanceFactor < -1 && val > node.right.val) {
        return leftRotate(node);
    }

    // 右左情况，需要进行右旋后再进行左旋
    if (balanceFactor < -1 && val < node.right.val) {
        node.right = rightRotate(node.right);
        return leftRotate(node);
    }

    return node;
}

6. Implementierung des Löschvorgangs:
Beim Löschen eines Knotens wird dieser zunächst gemäß den Regeln des binären Suchbaums gelöscht und dann entsprechend dem Ausgleichsfaktor des Knotens auf dem Löschpfad angepasst. Die Anpassung umfasst die Rotation Operationen und Aktualisierung der Knotenhöhe.

AVLNode delete(AVLNode node, int val) {
    if (node == null) {
        return node;
    }

    if (val < node.val) {
        node.left = delete(node.left, val);
    } else if (val > node.val) {
        node.right = delete(node.right, val);
    } else {
        if (node.left == null || node.right == null) {
            node = (node.left != null) ? node.left : node.right;
        } else {
            AVLNode successor = findMin(node.right);
            node.val = successor.val;
            node.right = delete(node.right, node.val);
        }
    }

    if (node == null) {
        return node;
    }

    node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;

    int balanceFactor = getBalanceFactor(node);

    // 左左情况，需要进行右旋
    if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0) {
        return rightRotate(node);
    }

    // 左右情况，需要进行左旋后再进行右旋
    if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) {
        node.left = leftRotate(node.left);
        return rightRotate(node);
    }

    // 右右情况，需要进行左旋
    if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0) {
        return leftRotate(node);
    }

    // 右左情况，需要进行右旋后再进行左旋
    if (balanceFactor < -1 && getBalanceFactor(node.right) > 0) {
        node.right = rightRotate(node.right);
        return leftRotate(node);
    }

    return node;
}

AVLNode findMin(AVLNode node) {
    while (node.left != null) {
        node = node.left;
    }
    return node;
}

7. Testbeispiel:
Um die Richtigkeit des von uns implementierten AVL-Baum-Algorithmus zu überprüfen, können wir das folgende Beispiel zum Testen verwenden:

public static void main(String[] args) {
    AVLTree tree = new AVLTree();

    tree.root = tree.insert(tree.root, 10);
    tree.root = tree.insert(tree.root, 20);
    tree.root = tree.insert(tree.root, 30);
    tree.root = tree.insert(tree.root, 40);
    tree.root = tree.insert(tree.root, 50);
    tree.root = tree.insert(tree.root, 25);

    tree.inOrderTraversal(tree.root);
}

Ausgabeergebnisse:
10 20 25 30 40 50

Zusammenfassung:
In diesem Artikel wird die Verwendung von Java zum Implementieren des AVL-Baumalgorithmus vorgestellt und es werden spezifische Codebeispiele bereitgestellt. Durch die Implementierung von Einfüge- und Löschvorgängen können wir sicherstellen, dass der AVL-Baum immer ausgeglichen ist, was zu einer besseren Such-, Einfüge- und Löschleistung führt. Ich glaube, dass die Leser durch das Studium dieses Artikels den AVL-Baumalgorithmus besser verstehen und anwenden können.

Das obige ist der detaillierte Inhalt vonSo implementieren Sie den AVL-Baumalgorithmus mit Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!