Balanced Binary Tree

Q: Wie hoch ist die Zeitkomplexität eines balancierten binären Baums?

Ein Postorder-Durchlauf besucht jeden Knoten einmal: O(n) Zeit und O(h) Stapelspeicher für einen Baum der Höhe h . Die Höhen an jedem Knoten erneut zu berechnen, kostet O(n·h) , was bei einer Kette zu O(n²) wird.

LeichtBaumdurchlauf Rekursion

+10

Das Array root enthält einen binären Baum. Die Wurzel befindet sich am Index 0, die Kinder des Index i befinden sich an den Indizes 2*i+1 (links) und 2*i+2 (rechts), -1 kennzeichnet eine leere Stelle, und am Ende können zusätzliche Einträge -1 folgen.

Gib true zurück, wenn der Baum höhenbalanciert ist, das heißt, wenn sich an jedem Knoten die Höhen des linken und rechten Teilbaums um höchstens 1 unterscheiden, und andernfalls false. Die Höhe eines Teilbaums ist die Anzahl der Knoten auf seinem längsten Abwärtspfad; ein leerer Teilbaum hat die Höhe 0.

Funktion

isBalanced(root: integer-array) → boolean

rootinteger-array: den Binärbaum in Ebenenreihenfolge, mit -1 für eine leere Stelle
Gibt zurückboolean: wahr, wenn sich die Höhen der beiden Teilbäume jedes Knotens um höchstens 1 unterscheiden, andernfalls falsch

Einschränkungen

1 ≤ root.length ≤ 32767
Jedes root[i] ist -1 oder ein Wert mit 0 ≤ root[i] ≤ 10⁵.
root[0] ist niemals -1, daher hat der Baum mindestens einen Knoten.
Das Array kann nach dem letzten Knoten zusätzliche -1-Einträge enthalten.
Auch die beiden Kinder einer leeren Stelle sind leer, und die Tiefe beträgt höchstens 14.
Knotenwerte sind unterschiedlich.

Beispiele

Eingabe: root = [5, 2, 9, -1, -1, 7, 11]
Ausgabe: true
Erklärung: Der linke Teilbaum der Wurzel ist der einzelne Knoten 2 mit Höhe 1. Ihr rechter Teilbaum mit den Knoten 9, 7, 11 hat Höhe 2. Sie unterscheiden sich um 1, und jeder andere Knoten hat zwei Teilbäume gleicher Höhe.

Eingabe: root = [6, 3, 8, 1, -1, -1, 9, 0, -1, -1, -1, -1, -1, -1, 10]
Ausgabe: false
Erklärung: Beide Seiten der Wurzel haben die Höhe 3, aber der Knoten 3 verletzt die Bedingung: Sein linker Teilbaum 1, 0 hat die Höhe 2, und der rechte ist leer.

Eingabe: root = [4, 2, -1, 1]
Ausgabe: false
Erklärung: Die Wurzel hat die Kette 2, 1 auf ihrer linken Seite, die Höhe 2, und nichts auf ihrer rechten Seite, die Höhe 0. Eine Differenz von 2 ist zu groß.

Weiterführende Frage

Kannst du den Baum ohne Rekursion mithilfe eines expliziten Stapels überprüfen?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Die Regel gilt an jedem Knoten, daher kann ein Baum, dessen Wurzel ausgeglichen wirkt, weiter unten trotzdem scheitern, wie es beim zweiten Beispiel bei 3 der Fall ist. Ein Durchlauf in Postorder berechnet die Höhe jedes Teilbaums genau einmal und gibt einen Fehler nach oben weiter, sobald er auftritt, in O(n).

Berechne die Höhen an jedem Knoten neu

Idee

Setze die Definition in Code um. height(i) ist an einer leeren Stelle 0 und andernorts um 1 größer als die Höhe des höheren Kindes. Vergleiche an jedem tatsächlichen Knoten die Höhen der beiden Kinder; der erste Knoten, an dem sie sich um mehr als 1 unterscheiden, macht die Antwort false.

Jede Prüfung durchläuft den gesamten Teilbaum unterhalb ihres Knotens, daher wird ein Knoten für jeden Knoten oberhalb von ihm einmal durchlaufen: O(n·h). Bei höchstens 14 Ebenen kostet ein vollständiger Baum mit 16,383 Knoten etwa 2 × 10^5 Schritte. Eine Kette aus n Knoten würde O(n²) kosten.

Algorithmus

Definiere height(i) für einen Index hinter dem Ende oder einen -1 als 0 und für einen tatsächlichen Knoten als 1 + max(height(2*i+1), height(2*i+2)).
Besuche jeden Index i, der einen tatsächlichen Knoten enthält.
Wenn sich height(2*i+1) und height(2*i+2) um mehr als 1 unterscheiden, gib false zurück.
Wenn die Schleife ohne Fehler endet, gib true zurück.

def isBalanced(root):
    n = len(root)

    def height(i):
        # The number of nodes on the longest downward path from index i.
        if i >= n or root[i] == -1:
            return 0
        return 1 + max(height(2 * i + 1), height(2 * i + 2))

    # Check every real node, measuring both subtrees from scratch.
    for i in range(n):
        if root[i] != -1 and abs(height(2 * i + 1) - height(2 * i + 2)) > 1:
            return False
    return True

Ein Durchlauf in Postorder, der die Höhe oder einen Fehler meldet

Idee

Die Prüfung an einem Knoten benötigt die Höhen seiner beiden Teilbäume, und diese benötigt der Knoten auch, um seine eigene Höhe zurückzugeben. Ermittle also beide bei einem Durchlauf in Postorder: Jeder Aufruf gibt die Höhe seines Teilbaums zurück, nachdem beide Kindknoten zurückgekehrt sind.

Ein Fehler weiter unten muss ebenfalls nach oben weitergegeben werden. Eine tatsächliche Höhe ist niemals negativ, verwende daher -1 dafür: Ein Aufruf gibt -1 zurück, wenn ein Kindknoten -1 zurückgegeben hat oder sich die Höhen der Kindknoten um mehr als 1 unterscheiden. Im zweiten Beispiel sieht die 3 die Höhen 2 und 0 und gibt -1 zurück, und die Wurzel gibt diesen Wert weiter, ohne ihre rechte Seite zu besuchen.

Kein Knoten wird zweimal betreten, daher beträgt die Laufzeit O(n), mit O(h) Aufrufen auf dem Stack.

Algorithmus

Schreibe check(i). Für einen Index jenseits des Endes oder -1 gib 0 zurück.
Berechne left = check(2*i+1). Wenn es -1 ist, gib -1 zurück.
Berechne right = check(2*i+2). Wenn es -1 ist oder sich left und right um mehr als 1 unterscheiden, gib -1 zurück.
Gib andernfalls 1 + max(left, right) zurück.
Gib zurück, ob check(0) nicht -1 ist.

def isBalanced(root):
    n = len(root)

    def check(i):
        # The height of the subtree at index i, or -1 if it is not balanced.
        if i >= n or root[i] == -1:
            return 0
        left = check(2 * i + 1)
        if left == -1:
            return -1
        right = check(2 * i + 2)
        if right == -1 or abs(left - right) > 1:
            return -1
        return 1 + max(left, right)

    return check(0) != -1

Stolperfallen und Grenzfälle

Nur die Wurzel überprüfen. Im zweiten Beispiel haben beide Seiten der Wurzel die Höhe 3, dennoch weicht der Knoten 3 um 2 ab.
Das flachste und das tiefste Blatt vergleichen. Der kleinste balancierte Baum der Höhe 6 hat Blätter in den Tiefen 4 und 6, und jeder Knoten darin besteht die Prüfung.
Einen Fehler auf dem Weg nach oben verlieren. Wenn ein Kind -1 zurückgibt und der Elternknoten 1 + max(-1, 2) berechnet, wird aus dem Fehler wieder eine Höhe.
Die Länge des Arrays als Höhe verwenden. Nachgestellte -1-Einträge machen das Array länger, als der Baum tief ist.
In Lua und R beginnen Arrays bei 1. Behalte für 2*i+1 die 0-basierte Indizierung der Knoten bei und lies root[i + 1].

Häufige Fragen3

Wie hoch ist die Zeitkomplexität eines balancierten binären Baums?

Ein Postorder-Durchlauf besucht jeden Knoten einmal: O(n) Zeit und O(h) Stapelspeicher für einen Baum der Höhe h. Die Höhen an jedem Knoten erneut zu berechnen, kostet O(n·h), was bei einer Kette zu O(n²) wird.

Was bedeutet höhenbalanciert bei einem Binärbaum?

An jedem Knoten unterscheiden sich die Höhen des linken und rechten Teilbaums um höchstens 1. AVL-Bäume stellen diese Eigenschaft nach jedem Einfügen und Löschen wieder her, wodurch ihre Höhe bei O(log n) bleibt.

Ist ein vollständiger Binärbaum immer ausgeglichen?

Ja. Jede Ebene eines vollständigen Baums ist voll, mit Ausnahme möglicherweise der letzten, die sich von links füllt. Daher unterscheiden sich an jedem Knoten die Höhen der beiden Teilbäume um höchstens 1. Die Umkehrung gilt nicht: Ein balancierter Baum kann Lücken auf der linken Seite seiner letzten Ebene haben.

def isBalanced(root):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argument

root = [5, 2, 9, -1, -1, 7, 11]

Erwartete Ausgabe

true