Beispielanalyse eines Java-Binärsuchbaums

Konzept

Der binäre Suchbaum wird auch als binärer Sortierbaum bezeichnet. Er ist entweder ein leerer Baum oder ein binärer Baum mit den folgenden Eigenschaften:
1. Wenn sein linker Teilbaum nicht leer ist, dann Die Werte aller Knoten im linken Teilbaum sind kleiner als der Wert des Wurzelknotens.
2. Wenn sein rechter Teilbaum nicht leer ist, sind die Werte aller Knoten im rechten Teilbaum größer als der Wert des Wurzelknotens.
3. Seine linken und rechten Teilbäume sind jeweils auch binäre Suchbäume

Direkte Übung

Vorbereitungsarbeit: Definieren Sie eine Klasse von Baumknoten und eine Klasse von binären Suchbäumen.

Durchsuchen Sie die Suchfunktion eines Binärbaums.

Angenommen, wir haben einen solchen Binärbaum erstellt, wie unten gezeigt. Die erste Frage, über die wir nachdenken möchten, ist, wie wir herausfinden können, ob ein bestimmter Wert vorhanden ist der Binärbaum?

Basierend auf der obigen Logik verbessern wir die Suchmethode.

Durchsuchen Sie die Einfügeoperation des Binärbaums.

Basierend auf der obigen Logik schreiben wir einen Code zum Einfügen eines Knotens.

Suche nach dem Vorgang zum Löschen von Knoten in einem Binärbaum - Schwierigkeitsgrad

Lassen Sie uns noch einmal analysieren: Wie curDummy und parentDummy den „Sündenbock“ finden. Allgemeines Programm: Simulieren Sie die Implementierung des binären Suchbaums in der Leistung des binären Suchbaums.

  Wenn für einen binären Suchbaum mit n Knoten die Wahrscheinlichkeit, jedes Element zu finden, gleich ist, dann ist die durchschnittliche Suchlänge des binären Suchbaums eine Funktion der Tiefe des Knotens in der binären Suche BaumDas heißt, je tiefer der Knoten, desto größer die Anzahl der Vergleiche.

  Wenn jedoch für denselben Schlüsselcodesatz die Reihenfolge der Einfügung jedes Schlüsselcodes unterschiedlich ist, können binäre Suchbäume mit unterschiedlichen Strukturen erhalten werden:

Wenn wir links und rechts garantieren können Kinder des binären Suchbaums Der Unterschied in der Baumhöhe überschreitet nicht 1. Versuchen Sie, die hohen Gleichgewichtsbedingungen zu erfüllen.

Dies wird zu einem AVL-Baum (höhenbalancierter binärer Suchbaum). Der AVL-Baum hat auch Nachteile: Er erfordert eine häufige Rotation. Viel verschwendete Effizienz.

An diesem Punkt wird der rot-schwarze Baum geboren, um weitere Rotationen zu vermeiden.

Die Beziehung zwischen Java-Klassensätzen

TreeMap und TreeSet sind Map und Set, die in Java mithilfe von Suchbäumen implementiert werden. Tatsächlich werden rot-schwarze Bäume verwendet, und rot-schwarze Bäume sind ein ungefähr ausgeglichener binärer Suchbaum Basierend auf dem binären Suchbaum + der Farbe und der Rot-Schwarz-Baum-Eigenschaftsüberprüfung wird der Blogger einen Blog schreiben, nachdem er ihn gelernt hat.

Das obige ist der detaillierte Inhalt vonBeispielanalyse eines Java-Binärsuchbaums. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!