Die Beziehung zwischen ausgeglichenen Binärbäumen und binär sortierten Bäumen

Es gibt keine direkte Beziehung zwischen ausgeglichenen Binärbäumen und binären Sortierbäumen, aber die Sucheffizienz binärer Sortierbäume hängt von der Form des Binärbaums ab, also davon, wann wir die Form des binären Sortierbaums haben wollen Seien Sie einheitlich, so werden Binärbäume als ausgeglichene Binärbäume bezeichnet.

1. Binärer Sortierbaum

Binärer Sortierbaum, auch bekannt als Binärer Suchbaum (Binärer Suchbaum), auch bekannt als Binärer Suchbaum.

• Definition des binären Sortierbaums:

Ein binärer Sortierbaum ist entweder ein leerer Baum oder hat die folgenden Eigenschaften: Binärer Baum:

1. Wenn der linke Teilbaum nicht leer ist, sind die Werte aller Knoten im linken Teilbaum kleiner als der Wert seines Wurzelknotens.
2. Wenn der rechte Teilbaum leer ist nicht leer, dann sind die Werte aller Knoten im rechten Teilbaum größer als der Wert seines Wurzelknotens
3. Der linke und rechte Teilbaum sind ebenfalls binär sortierte Bäume.

Wie in der Abbildung unten gezeigt, handelt es sich um einen binären Sortierbaum:

Führen Sie eine Durchquerung des binären Sortierbaums in der richtigen Reihenfolge durch, um eine nach Schlüsselwörtern sortierte Sequenz zu erhalten. Beispielsweise kann eine geordnete Durchquerung der obigen Abbildung eine geordnete Sequenz erhalten: 10, 42, 45, 55, 58, 63, 67, 70, 83, 90, 98

• Suchanalyse des binären Sortierbaums

In Bezug auf die durchschnittliche Zeitleistung der Suche ähnelt die Suche im binären Sortierbaum der binären Suche, jedoch hinsichtlich der Aufrechterhaltung der Ordnungsmäßigkeit der Tabelle In Bezug auf die Effizienz ist der binär sortierte Baum effizienter, da keine Knoten verschoben werden müssen, sondern nur der Zeiger geändert werden muss, um die Einfüge- und Löschvorgänge des binär sortierten Baums abzuschließen.

Binär sortierte Baumsuche Im schlimmsten Fall hängt die benötigte Suchzeit von der Tiefe des Baums ab:

1. Wenn ein binärer Sortierbaum nahe an einem vollständigen Binärbaum liegt, beträgt seine Tiefe $log_2n$ , also ist die Suchzeit im ungünstigsten Fall O( $log_2n$ ), was in der gleichen Größenordnung wie die binäre Suche liegt.
2. Wenn ein Binärbaum einen Einzelzweigbaum bildet, wie in der folgenden Abbildung gezeigt, beträgt seine Tiefe n und die Suchzeit beträgt im schlimmsten Fall O (n). in der gleichen Größenordnung wie die sequentielle Suche.
   
   AlsoUm eine hohe Suchgeschwindigkeit für die Suche nach binären Sortierbäumen sicherzustellen, hoffen wir, dass der Binärbaum einem vollständigen Binärbaum nahe kommt oder dass die Tiefen des linken und rechten Teilbaums Jeder Knoten des Binärbaums ist so gleich wie möglich Der Sortierbaum hängt mit der Form des Binärbaums zusammen. Wir hoffen, dass die Form des Binärsortierbaums einheitlich ist. Ein solcher Binärbaum wird als ausgeglichener Binärbaum bezeichnet.
   • Definition eines ausgeglichenen Binärbaums
     Ausgeglichener Binärbaum (Balanced Binary Tree), es ist ein leerer Baum oder hat die folgenden Eigenschaften:
   1. Der absolute Wert der Tiefendifferenz zwischen seinem linken und rechten Teilbaum überschreitet nicht 1;
   2. Sein linker und rechter Teilbaum sind ebenfalls ausgeglichene Binärbäume.

   Die Tiefe des linken Teilbaums eines Binärbaumknotens abzüglich der Tiefe seines rechten Teilbaums wird als Balance-Faktor BF bezeichnet, dann ist es nur möglich, die Balance-Faktoren auszubalancieren aller Knoten im Binärbaum sind -1, 0 und 1. Der linke in der Abbildung unten ist ein ausgeglichener Binärbaum und der rechte ist ein unausgeglichener Binärbaum.
   
   Da der Unterschied zwischen den Tiefen des linken und rechten Teilbaums eines beliebigen Knotens in einem ausgeglichenen Binärbaum 1 nicht überschreitet, kann bewiesen werden, dass seine Tiefe mit der Tiefe eines vollständigen Knotens übereinstimmt Binärbaum mit n Knoten $lfloor log_2n rfloor$+1 sind gleich Größenordnung. Daher beträgt die durchschnittliche Anzahl der Suchanfragen auch >g2$o$g

   • Es gibt im Allgemeinen vier Situationen zum Anpassen des minimalen unausgeglichenen Teilbaums:
   1. Einseitige Rechtsdrehung (LL-Typ): Fügen Sie den linken Teilbaum ein, dessen Position der linke Teilbaum ist, und führen Sie eine einzelne Rechtsdrehung mit dem linken Teilbaum als Achse durch, wie in der Abbildung unten gezeigt. Die Zahl neben dem Knoten ist der Gleichgewichtsfaktor des Knotens, und der I-Knoten ist der aktuell eingefügte Knoten (wenn sich der I-Knoten in der Mitte befindet, bedeutet dies, dass der I-Knoten entweder ein linkes oder ein rechtes Kind sein kann.

   Hinweis: LL-Typ, drehen Sie mit dem mittleren Knoten als Achse. Warum hier I das linke Kind von BL ist und B-BL-I nicht als LL-Typ verwendet werden kann, weil der A-Knoten dem I-Knoten am nächsten kommt. Bei Teilbäumen mit einem Faktor-Absolutwert von > 1 überschreiten die Absolutwerte der Gleichgewichtsfaktoren anderer Knoten ebenfalls nicht 1; rechtes Kind von BL, B-BL-I kann nicht als LR-Typ angesehen werden 2. Einseitige Linksrotation (RR-Typ):
   Die Einfügeposition ist der rechte Teilbaum des rechten Teilbaums und der rechte Teilbaum ist die Achse, und eine einzelne Operation wird ausgeführt.
   Beachten Sie den RR-Typ Die Achse hat keinen Einfluss auf den tatsächlichen RR-Typ.

   3.

   Bidirektionale Drehung zuerst nach links und dann nach rechts (LR-Typ): Fügen Sie den rechten Teilbaum des linken Teilbaums ein und führen Sie zuerst zwei Drehungen durch nach links und dann nach rechts. 🎜>Fügen Sie den Knoten als linkes Kind ein: Beachten Sie, warum
   B-C-I nicht als Teilbaum verwenden kann, um ihn als RL-Typ zu definieren. Das Prinzip ist das gleiche wie in RR Beim LR-Typ liegt das R-Ende oder L in der Nähe des eingefügten Knotenendes als Rotationsachse (wie in der Abbildung unten gezeigt, entspricht dies dem Drehen des Teilbaums zuerst mit B als Wurzel und dem anschließenden Drehen des Teilbaums mit A als Wurzel und dann den Teilbaum mit A als Wurzel drehen. Untergeordnetes Element:
   4 Teilbaum, dessen Position der rechte Teilbaum ist, und zwei Anpassungen vornehmen, zuerst Rechtsrotation und dann Linksrotation; Die Verarbeitungssituation ist ähnlich wie bei LR:

   Knoten als rechtes untergeordnetes Element einfügen:
   
   Durch das oben Gesagte können wir feststellen, dass der Gleichgewichtsfaktor eine gute Beziehung zu dem Typ hat, der dem Knoten am nächsten ist der eingefügte Knoten und der Absolutwert des Ausgleichsfaktors > 1 als Teilbaum des Wurzelknotens, um zu bestimmen, um welchen Typ es sich handelt
   
   Übung

   
   Wie in der Abbildung unten gezeigt, fügen Sie zuerst Knoten 2 ein, um ein LL-Typ zu werden, und gleichen Sie ihn dann nach der gesamten rechten Verarbeitung aus. >
   Nachdem Sie 8 und 6 nacheinander eingefügt haben Der absolute Wert des Ausgleichsfaktors von Knoten 5 ist > 1 und wird zum RL-Typ. Nehmen Sie also zuerst 5 als Wurzelknoten und drehen Sie seinen Unterbaum um 8-6 nach rechts (wird zum RR-Typ) und drehen Sie dann den gesamten Baum um 5 as Nachdem Sie Knoten 9 weiter eingefügt haben, ist der Ausgleichsfaktor von Knoten 4 zum RR-Typ geworden, sodass 4 der Wurzelknoten ist. Drehen Sie das Ganze nach links.

Das obige ist der detaillierte Inhalt vonDie Beziehung zwischen ausgeglichenen Binärbäumen und binär sortierten Bäumen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!