Ausgewogene Binärbäume

Im Falle von Binärbäumen, wenn die Bäume einseitig sind, werden sie rechnerisch ineffizient, um Operationen auszuführen. Das ist die Motivation dahinter, sicherzustellen, dass die Bäume nicht einseitig sind. Daher die Notwendigkeit für ausgeglichene Binärbäume.

Was ist ein ausgeglichener Binärbaum?

Ausgeglichene Binärbäume sind rechnerisch effizient, um Operationen darauf auszuführen. Ein ausgeglichener Binärbaum wird den folgenden Bedingungen folgen:

• Die absolute Differenz der Höhen von linken und rechten Teilbäumen an jedem Knoten ist weniger als 1.
• Für jeden Knoten ist sein linker Teilbaum ein ausgeglichener Binärbaum.
• Für jeden Knoten ist sein rechter Teilbaum ein ausgeglichener Binärbaum.

Höhen-ausgeglichene Binärbäume

Ausgeglichene Binärbäume sind auch als höhen-ausgeglichene Binärbäume bekannt. Höhen-ausgeglichene Binärbäume können mit HB(k) bezeichnet werden, wobei k der Unterschied zwischen den Höhen von linken und rechten Teilbäumen ist. ‚k‘ ist als der Balancefaktor bekannt.

Wenn für einen Baum der Balancefaktor (k) gleich Null ist, dann ist dieser Baum als ein vollständig ausgeglichener Binärbaum bekannt. Er kann als HB(0) bezeichnet werden.

Automatisch balancierende Binärsuchbäume

Wenn ein Binärsuchbaum einen Balancefaktor von eins hat, dann ist es ein AVL (Adelso-Velskii und Landis) Baum. Das bedeutet, dass in einem AVL-Baum der Unterschied zwischen linker und rechter Teilbaumhöhe höchstens eins ist. Ein AVL-Baum ist ein automatisch balancierender Binärsuchbaum. Wenn in einem AVL-Baum der Unterschied zwischen linken und rechten Teilbäumen größer als 1 ist, führt er eine der folgenden 4 Rotationen aus, um sich selbst auszugleichen:

• Linksrotation
• Rechtsrotation
• Links-Rechts-Rotation
• Rechts-Links-Rotation

Wie prüft man, ob ein Binärbaum ausbalanciert ist?

Um zu prüfen, ob ein Binärbaum ausbalanciert ist, müssen wir drei Bedingungen überprüfen:

• Die absolute Differenz zwischen Höhen von linken und rechten Teilbäumen an jedem Knoten sollte weniger als 1 sein.
• Für jeden Knoten sollte sein linker Teilbaum ein ausgeglichener Binärbaum sein.
• Für jeden Knoten sollte sein rechter Teilbaum ein ausgeglichener Binärbaum sein.

Wir benötigen eine Funktion, die die Höhe des Baums berechnen kann. Eine Möglichkeit dies zu tun, ist eine separate Funktion für die Berechnung der Höhe zu schreiben und sie jedes Mal aufzurufen, wenn die Höhe benötigt wird. Dies wäre rechnerisch ineffizient. Der bessere Weg, dies zu implementieren, wäre, die Höhe in derselben Funktion zurückzugeben.

Für jeden Knoten wird -1 zurückgegeben, wenn er nicht ausgeglichen ist, und die Höhe des Knoten/Teilbaums, wenn er ausgeglichen ist.

Der Algorithmus läuft wie folgt ab:

• Wenn Knoten == null -> return 0
• Linken Teilbaum prüfen. Wenn nicht ausgeglichen -> return -1
• Rechten Teilbaum prüfen. Wenn nicht ausgeglichen -> return -1
• Der absolute Wert zwischen den Höhen des linken und rechten Teilbaums. Wenn er größer als 1 ist -> return -1.
• Wenn der Baum ausgeglichen ist -> return Höhe

private int balanceHeight (TreeNode currentNode)
    {
        if (currentNode == null)
        {
            return 0;
        }

        // checking left subtree
        int leftSubtreeHeight = balanceHeight (currentNode.left);
        if (leftSubtreeHeight == -1) return -1;
        // if left subtree is not balanced then the entire tree is also not balanced

        //checking right subtree
        int rightSubtreeHeight = balanceHeight (currentNode.right);
        if (rightSubtreeHeight == -1) return -1;
        // if right subtree is not balanced then the entire          tree is also not balanced

        //checking the difference of left and right subtree for current node
        if (Math.abs(leftSubtreeHeight - rightSubtreeHeight) > 1)
        {
            return -1;
        }
        //if it is balanced then return the height
        return (Math.max(leftSubtreeHeight, rightSubtreeHeight) + 1);
    }

Sie können diese Funktion auf die Wurzel des Baumes aufrufen und wenn sie etwas anderes als -1 zurückgibt, dann ist es ein ausgeglichener Binärbaum. Wenn sie -1 zurückgibt, dann ist es kein ausgeglichener Binärbaum.

Schlussfolgerung

In diesem Tutorial haben wir die Eigenschaften ausgeglichener und ausgewogener Binärbäume behandelt und wie man prüfen kann, ob ein Baum ein ausgeglichener Binärbaum ist. Wir hoffen, Sie haben verstanden und das Lernen mit uns genossen.