Tutorial zum binären Suchbaumalgorithmus für JavaScript-Anfänger

In diesem Artikel werde ich mein Bestes geben, einige der wichtigsten Algorithmen zu erklären, die Sie vor einem Coding-Interview lernen sollten.

Was ist ein binärer Suchbaum (BST)?

Ein BST, das häufig bei Kodierungsinterviews anzutreffen ist, ist eine baumartige Datenstruktur mit einer Wurzel an der Spitze. Sie eignen sich hervorragend zum Speichern numerischer Werte, da ihre geordnete Natur ein schnelles Suchen und Nachschlagen ermöglicht.

Im Vergleich zu gewöhnlichen Bäumen weist BST die folgenden Eigenschaften auf:

• Jedes linke Kind hat einen geringeren Wert als sein Elternteil
• Jedes richtige Kind hat einen höheren Wert als sein Elternteil
• Jeder Knoten kann 0 bis 2 untergeordnete Knoten enthalten.

Das folgende Diagramm soll die Dinge klarer machen.

Definition eines binären Baumknotens

Normalerweise definieren wir einen binären Baumknoten in Javascript mit der folgenden Funktion:

 Funktion TreeNode(Wert, links, rechts) {
     dies.val = val
     dies.links = links
     dies.rechts = rechts
 }

Grundlegende Durchquerung eines binären Baums (In-Order, Post-Order, Pre-Order)

Zuerst müssen wir wissen, wie jeder Knoten des BST durchlaufen wird. Dadurch können wir eine Funktion auf allen Knoten des BST ausführen. Wenn wir beispielsweise einen Wert x in einem BST finden möchten, benötigen wir Knoten.

Hierfür gibt es im Wesentlichen drei Möglichkeiten. Glücklicherweise haben sie ein gemeinsames Thema.

In-Order-Traversierung

Ein rekursiver Algorithmus ist der einfachste Weg, mit der In-Order-Traversierung eines Binärbaums zu beginnen. Die Idee ist folgende:

• Wenn der Knoten leer ist, tun Sie nichts. Andernfalls rufen Sie die Funktion rekursiv für das linke untergeordnete Element des Knotens auf.
• Führen Sie dann, nachdem Sie alle linken untergeordneten Knoten durchlaufen haben, einige Vorgänge an den Knoten aus. Unser aktueller Knoten ist garantiert der äußerste linke Knoten.
• Schließlich wird die Funktion auf node.right aufgerufen.

Der Inorder-Algorithmus durchläuft die Baumknoten von links, von der Mitte und von rechts.

const inorder = (Wurzel) => {
    const Knoten = []
    wenn (Wurzel) {
        inorder(Wurzel.links)
        Knoten.push(root.val)
        inorder(root.rechts)
    }
    Rückgabeknoten
}
// Für unseren Beispielbaum ergibt dies [1,2,3,4,5,6]

Post-Order-Traversierung

Ein rekursiver Algorithmus ist die einfachste Möglichkeit, eine Post-Order-Traversierung zu starten.

• Wenn der Knoten leer ist, tun Sie nichts. Andernfalls rufen Sie die Funktion rekursiv für das linke untergeordnete Element des Knotens auf.
• Wenn keine linken Kinder mehr vorhanden sind, rufen Sie die Funktion auf node.right auf.
• Führen Sie abschließend einige Vorgänge am Knoten durch.

Bei der Post-Order-Traversierung werden die Baumknoten von links, rechts und der Mitte besucht.

const postorder = (Wurzel) => {
    const Knoten = []
    wenn (Wurzel) {
        Postorder(Wurzel.links)
        Postorder(root.rechts)
        Knoten.push(root.val)
    }
    Rückgabeknoten
}
// Für unseren Beispielbaum ergibt dies [1,3,2,6,5,4]

Durchquerung vorbestellen

Der einfachste Weg, eine Pre-Order-Traversierung zu starten, ist mit einem rekursiven Algorithmus.

• Wenn der Knoten leer ist, tun Sie nichts. Andernfalls tun Sie etwas auf dem Knoten.
• Durchlaufen Sie die linken untergeordneten Knoten und wiederholen Sie den Vorgang.
• Gehen Sie zum rechten untergeordneten Knoten und wiederholen Sie den Vorgang.

Bei der Post-Order-Traversierung werden die Baumknoten von der Mitte, von links und von rechts aus besucht.

const preorder = (Wurzel) => {
    const Knoten = []
    wenn (Wurzel) {
        Knoten.push(root.val)
        Vorbestellung (root.left)
        Vorbestellung (Root.right)
    }
    Rückgabeknoten
}
// Für unseren Beispielbaum ergibt dies [4,2,1,3,5,6]

Was ist ein gültiger binärer Suchbaum?

Ein gültiger binärer Suchbaum (BST) hat alle linken Kinder, deren Werte kleiner als der Elternknoten sind, und alle rechten Kinder, deren Werte größer als der Elternknoten sind.
So überprüfen Sie, ob ein Baum ein gültiger binärer Suchbaum ist:

• Definiert den minimalen und maximalen Wert, den der aktuelle Knoten haben kann
• Wenn der Wert des Knotens nicht innerhalb dieser Bereiche liegt, gibt er false zurück.
• Überprüfen Sie rekursiv das linke Kind des Knotens, wobei die maximale Grenze auf den Wert des Knotens gesetzt wird
• Überprüfen Sie rekursiv das rechte Kind des Knotens, wobei die Mindestgrenze auf den Wert des Knotens gesetzt wird.

const isValidBST = (root) => {
    const-Helfer = (Knoten, min, max) => {
        wenn (!node) true zurückgibt
        wenn (node.val <= min || node.val >= max) false zurückgibt
        gibt Helfer zurück (Knoten.links, min, Knoten.val) und Helfer (Knoten.rechts, Knoten.val, max)
    }
    Rückgabe-Helfer (Root, Zahl.MIN_SAFE_INTEGER, Zahl.MAX_SAFE_INTEGER)
}

So finden Sie die maximale Tiefe eines Binärbaums

Hier versucht der Algorithmus, die Höhe/Tiefe unseres BST zu finden. Mit anderen Worten, wir untersuchen, wie viele „Ebenen“ der BST enthält.

• Wenn der Knoten leer ist, geben wir 0 zurück, da er keine Tiefe hinzufügt
• Andernfalls addieren wir +1 zu unserer aktuellen Tiefe (wir haben eine Ebene durchlaufen)
• Berechnen Sie rekursiv die Tiefe der untergeordneten Knoten eines Knotens und geben Sie die maximale Summe zwischen node.left und node.right zurück.

const maxDepth = Funktion(Wurzel) {
    const calc = (Knoten) => {
        wenn (!node) return 0
        returniere Math.max(1 + calc(Knoten.links), 1 + calc(Knoten.rechts))
    }
    gibt calc(Wurzel) zurück
};

So finden Sie den kleinsten gemeinsamen Vorfahren zwischen zwei Baumknoten

Erhöhen wir den Schwierigkeitsgrad. Wie finden wir den gemeinsamen Vorfahren zwischen zwei Baumknoten in unserem Binärbaum? Schauen wir uns einige Beispiele an.

In diesem Baum ist der kleinste gemeinsame Vorfahr von 3 und 1 2. Der LCA von 3 und 2 ist 2. Der LCA von 6 und 1 und 6 ist 4.

Sehen Sie hier das Muster? Der LCA zwischen zwei Baumknoten ist entweder einer der Knoten selbst (Fälle 3 und 2) oder ein übergeordneter Knoten, bei dem sich das erste untergeordnete Element irgendwo in seinem linken Teilbaum und das zweite untergeordnete Element irgendwo in seinem rechten Teilbaum befindet.

Der Algorithmus zum Finden des kleinsten gemeinsamen Vorfahrens (LCA) zwischen zwei Baumknoten p und q lautet wie folgt:

• Überprüfen Sie, ob p oder q im linken oder rechten Teilbaum gefunden wird
• Überprüfen Sie dann, ob der aktuelle Knoten p oder q ist.
• Wenn wir eines von p oder q im linken oder rechten Teilbaum finden und eines von p oder q der Knoten selbst ist, haben wir den LCA gefunden
• Wenn wir sowohl p als auch q im linken oder rechten Teilbaum finden, haben wir LCA gefunden

const niedrigsterGemeinsamerVorfahre = Funktion(Wurzel, p, q) {
    lass lca = null
    const isCommonPath = (Knoten) => {
        wenn (!node) false zurückgibt
        var isLeft = isCommonPath(node.left)
        var isRight = isCommonPath(node.right)
        var isMid = Knoten == p || Knoten == q
        wenn (istMitte && istLinks || istMitte && istRechts || istLinks && istRechts) {
            lca = Knoten
        }
        Rückgabe ist links || ist rechts || ist Mitte
    }
    isCommonPath(Wurzel)
    Ökobilanz zurückgeben
};

😊 Ende

Bisher haben wir gelernt, wie man einen BST durchläuft, überprüft und seine Tiefe berechnet.

Damit ist dieser Artikel zum Tutorial zum binären Suchbaumalgorithmus für JavaScript-Anfänger abgeschlossen. Weitere relevante Inhalte zum binären Suchbaumalgorithmus in JavaScript finden Sie in den vorherigen Artikeln von 123WORDPRESS.COM oder in den folgenden verwandten Artikeln. Ich hoffe, dass jeder 123WORDPRESS.COM in Zukunft unterstützen wird!