Implementierung eines binären Suchbaums

2024 Autor: Angel Austin | [email protected]. Zuletzt bearbeitet: 2023-12-17 05:21

Binärer Suchbaum - eine strukturierte Datenbank mit Knoten, zwei Links zu anderen Knoten, rechts und links. Knoten sind ein Objekt der Klasse, das Daten enthält, und NULL ist das Zeichen, das das Ende des Baums markiert.

Es wird oft als BST bezeichnet, das eine besondere Eigenschaft hat: Knoten, die größer als die Wurzel sind, befinden sich rechts davon und kleinere links davon.

Allgemeine Theorie und Terminologie

In einem binären Suchbaum ist jeder Knoten, mit Ausnahme der Wurzel, durch eine gerichtete Kante von einem Knoten zum anderen verbunden, der Elternknoten genannt wird. Jeder von ihnen kann mit einer beliebigen Anzahl von Knoten verbunden werden, die Kinder genannt werden. Knoten ohne "Kinder" werden als Blätter (äußere Knoten) bezeichnet. Elemente, die keine Blätter sind, werden als intern bezeichnet. Knoten mit demselben Elternteil sind Geschwister. Der oberste Knoten wird Wurzel genannt. Ordnen Sie in BST jedem Knoten ein Element zu und stellen Sie sicher, dass für ihn ein spezieller Eigenschaftssatz vorhanden ist.

Baumterminologie:

1. Die Tiefe eines Knotens ist die Anzahl der Kanten, die von der Wurzel zu ihm definiert sind.
2. Die Höhe eines Knotens ist die Anzahl der Kanten, die von ihm bis zum tiefsten Blatt definiert sind.
3. Die Höhe des Baumes wird durch die Höhe der Wurzel bestimmt.
4. Der binäre Suchbaum ist ein spezielles Design, er bietet das beste Verhältnis von Höhe und Anzahl der Knoten.
5. Höhe h mit N Knoten höchstens O (log N).

Sie können dies leicht beweisen, indem Sie die Knoten auf jeder Ebene zählen, beginnend bei der Wurzel, in der Annahme, dass sie die meisten davon enthält: n=1 + 2 + 4 + … + 2 h-1 + 2 h=2 h + 1 - 1 Auflösen nach h ergibt h=O (log n).

Vorteile von Holz:

1. Spiegeln die strukturellen Beziehungen der Daten wider.
2. Dient zur Darstellung von Hierarchien.
3. Effiziente Installation und Suche sicherstellen.
4. Bäume sind sehr flexible Daten, die es Ihnen ermöglichen, Unterbäume mit minimalem Aufwand zu verschieben.

Suchmethode

Um festzustellen, ob sich ein Wert in der BST befindet, starten Sie im Allgemeinen einen binären Suchbaum an seiner Wurzel und bestimmen Sie, ob er die Anforderungen erfüllt:

• an der Wurzel sein;
• be im linken Teilbaum von root;
• im rechten Teilbaum von root.

Wenn kein Basisregister erfüllt ist, wird eine rekursive Suche im entsprechenden Teilbaum durchgeführt. Es gibt eigentlich zwei grundlegende Optionen:

1. Der Baum ist leer - gebe false zurück.
2. Der Wert befindet sich im Wurzelknoten - gebe true zurück.

Zu beachten ist, dass ein binärer Suchbaum mit einem entwickelten Schema immer entlang des Pfades von der Wurzel bis zum Blatt zu suchen beginnt. Im schlimmsten Fall geht es bis zum Blatt. Daher ist die schlechteste Zeit proportional zur Länge des längsten Pfads von der Wurzel zum Blatt, was der Höhe des Baums entspricht. Im Allgemeinen ist dies der Fall, wenn Sie wissen müssen, wie lange das Nachschlagen in Abhängigkeit von der Anzahl der im Baum gespeicherten Werte dauert.

Mit anderen Worten, es gibt eine Beziehung zwischen der Anzahl der Knoten in einem BST und der Höhe eines Baums, abhängig von seiner "Form". Im schlimmsten Fall haben Knoten nur ein Kind, und ein balancierter binärer Suchbaum ist im Wesentlichen eine verkettete Liste. Zum Beispiel:

50

/

10

15

30

/

20

Dieser Baum hat 5 Knoten und Höhe=5. Um Werte im Bereich 16-19 und 21-29 zu finden, ist der folgende Pfad von der Wurzel zum Blatt (dem Knoten mit dem Wert 20) erforderlich, d.h., dauert es proportional zur Anzahl der Knoten. Bestenfalls haben sie alle 2 Kinder, und die Blätter befinden sich in der gleichen Tiefe.

Dieser binäre Suchbaum hat 7 Knoten und eine Höhe=3. Im Allgemeinen hat ein Baum wie dieser (vollständiger Baum) eine Höhe von ungefähr log 2 (N), wobei N die Anzahl der Knoten im Baum ist. Der Wert von log 2 (N) ist die Anzahl (2), die N geteilt werden kann, bevor Null erreicht wird.

Zusammenfassend: Die schlechteste Zeit, die zum Suchen in BST benötigt wird, ist O (Baumhöhe). Der ungünstigste "lineare" Baum ist O(N), wobei N die Anzahl der Knoten im Baum ist. Ein "vollständiger" Baum ist bestenfalls O(log N).

BST-Binäreinsatz

Ich frage mich, wo das sein sollteDer neue Knoten befindet sich im BST, Sie müssen die Logik verstehen, er muss dort platziert werden, wo der Benutzer ihn findet. Außerdem müssen Sie sich an die Regeln erinnern:

1. Duplikate sind nicht erlaubt, der Versuch, einen doppelten Wert einzufügen, löst eine Ausnahme aus.
2. Die öffentliche Einfügemethode verwendet eine rekursive "Helfer"-Hilfsmethode, um tatsächlich einzufügen.
3. Ein Knoten, der einen neuen Wert enthält, wird immer als Blatt in BST eingefügt.
4. Die öffentliche Einfügemethode gibt void zurück, aber die Hilfsmethode gibt einen BSTnode zurück. Dies geschieht, um den Fall zu behandeln, in dem der an ihn übergebene Knoten null ist.

Im Allgemeinen gibt die Hilfsmethode an, dass das Ergebnis ein Baum mit einem Knoten ist, wenn der ursprüngliche binäre Suchbaum leer ist. Andernfalls ist das Ergebnis ein Zeiger auf denselben Knoten, der als Argument übergeben wurde.

Löschung im binären Algorithmus

Wie zu erwarten ist, muss beim Löschen eines Elements ein Knoten gefunden werden, der den zu entfernenden Wert enthält. In diesem Code gibt es mehrere Dinge:

1. BST verwendet eine überladene Hilfslöschmethode. Wenn das gesuchte Element nicht im Baum vorhanden ist, wird die Hilfsmethode schließlich mit n==null aufgerufen. Dies wird nicht als Fehler gewertet, der Baum ändert sich in diesem Fall einfach nicht. Die Delete-Hilfsmethode gibt einen Wert zurück – einen Zeiger auf den aktualisierten Baum.
2. Wenn ein Blatt entfernt wird, setzt das Entfernen aus dem binären Suchbaum den entsprechenden untergeordneten Zeiger seines übergeordneten Elements auf null, oder die Wurzel auf null, wenn es das zu entfernende istder Knoten ist eine Wurzel und hat keine Kinder.
3. Beachten Sie, dass der Löschaufruf einer der folgenden sein muss: root=delete (root, key), n.setLeft (delete (n.getLeft (), key)), n.setRight (delete(n. getRight(), Taste)). Daher ist es in allen drei Fällen richtig, dass die delete-Methode einfach null zurückgibt.
4. Wenn die Suche nach dem Knoten, der den zu löschenden Wert enthält, erfolgreich ist, gibt es drei Möglichkeiten: Der zu löschende Knoten ist ein Blatt (hat keine Kinder), der zu löschende Knoten hat ein Kind, er hat zwei Kinder.
5. Wenn der zu entfernende Knoten ein Kind hat, können Sie es einfach durch ein Kind ersetzen und einen Zeiger auf das Kind zurückgeben.
6. Wenn der zu löschende Knoten null oder 1 Kind hat, dann wird die delete-Methode "dem Pfad folgen" von der Wurzel zu diesem Knoten. Die schlechteste Zeit ist also proportional zur Höhe des Baums, sowohl für die Suche als auch für das Einfügen.

Wenn der zu entfernende Knoten zwei Kinder hat, werden die folgenden Schritte ausgeführt:

1. Finde den zu löschenden Knoten, indem du dem Pfad von der Wurzel zu ihm folgst.
2. Finde den kleinsten Wert von v im rechten Unterbaum und folge dem Pfad zum Blatt.
3. Entferne rekursiv den Wert von v, folge dem gleichen Pfad wie in Schritt 2.
4. Damit wird im schlimmsten Fall der Pfad von der Wurzel zum Blatt doppelt ausgeführt.

Reihenfolge der Traversen

Traversal ist ein Prozess, der alle Knoten in einem Baum besucht. Da ein binärer C-Suchbaum eine nichtlineare Datenstruktur ist, gibt es keine eindeutige Traversierung. Zum Beispiel manchmal mehrere Traversalalgorithmengruppiert in die folgenden zwei Typen:

• Kreuzungstiefe;
• erster Durchgang.

Es gibt nur eine Art der Breitenüberquerung - das Umgehen der Ebene. Diese Traversierung besucht die Knotenebene unten und links, oben und rechts.

Es gibt drei verschiedene Arten von Tiefendurchgängen:

1. Passing PreOrder - besuchen Sie zuerst das Elternteil und dann das linke und rechte Kind.
2. Passing InOrder - Besuch des linken Kindes, dann des Elternteils und des rechten Kindes.
3. Vorbei an der PostOrder - Besuch des linken Kindes, dann des rechten Kindes, dann des Elternteils.

Beispiel für vier Durchläufe eines binären Suchbaums:

1. Vorbestellung - 8, 5, 9, 7, 1, 12, 2, 4, 11, 3.
2. InOrder - 9, 5, 1, 7, 2, 12, 8, 4, 3, 11.
3. PostOrder - 9, 1, 2, 12, 7, 5, 3, 11, 4, 8.
4. LevelOrder - 8, 5, 4, 9, 7, 11, 1, 12, 3, 2.

Die Abbildung zeigt die Reihenfolge, in der Knoten besucht werden. Die Nummer 1 ist der erste Knoten in einem bestimmten Durchlauf und 7 ist der letzte Knoten.

Diese allgemeinen Durchläufe können als ein einziger Algorithmus dargestellt werden, vorausgesetzt, dass jeder Knoten dreimal besucht wird. Die Euler-Tour ist ein Spaziergang um einen Binärbaum, bei dem jede Kante als Wand behandelt wird, die der Benutzer nicht überschreiten kann. Bei diesem Spaziergang wird jeder Knoten entweder links, unten oder rechts besucht. Die Euler-Tour, die die Knoten auf der linken Seite besucht, bewirkt, dass die Präposition umgangen wird. Wenn die folgenden Knoten besucht werden, werden sie der Reihe nach durchlaufen. Und wenn die Knoten auf der rechten Seite besucht werden - getschrittweise Umgehung.

Navigation und Debugging

Um das Navigieren im Baum zu vereinfachen, erstellen Sie Funktionen, die zuerst prüfen, ob sie das linke oder rechte Kind sind. Um die Position eines Knotens zu ändern, muss der Zeiger am übergeordneten Knoten leicht zugänglich sein. Die korrekte Implementierung eines Baums ist sehr schwierig, daher müssen Sie Debugging-Prozesse kennen und anwenden. Ein binärer Suchbaum mit einer Implementierung hat oft Zeiger, die nicht wirklich die Fahrtrichtung anzeigen.

Um das alles herauszufinden, wird eine Funktion verwendet, die prüft, ob der Baum korrekt sein kann, und hilft, viele Fehler zu finden. Beispielsweise prüft es, ob der übergeordnete Knoten ein untergeordneter Knoten ist. Mit assert(is_wellformed(root)) können viele Fehler vorzeitig abgefangen werden. Anhand einiger vorgegebener H altepunkte innerhalb dieser Funktion können Sie auch genau bestimmen, welcher Zeiger falsch ist.

Funktion Konsolenausgabe

Diese Funktion löscht den gesamten Baum auf die Konsole und ist daher sehr nützlich. Die Reihenfolge, in der das Baumausgabeziel ausgeführt wird, ist:

1. Dazu müssen Sie zunächst festlegen, welche Informationen über den Knoten ausgegeben werden.
2. Und Sie müssen auch wissen, wie breit und hoch der Baum ist, um zu berücksichtigen, wie viel Platz übrig bleibt.
3. Die folgenden Funktionen berechnen diese Informationen für den Baum und jeden Teilbaum. Da Sie nur zeilenweise in die Konsole schreiben können, müssen Sie den Baum auch zeilenweise ausdrucken.
4. Jetzt brauchen wir eine andere Möglichkeit, uns zurückzuziehenden ganzen Baum, nicht nur Zeile für Zeile.
5. Mit Hilfe der Dump-Funktion können Sie den Baum auslesen und den Ausgabealgorithmus deutlich verbessern, was die Geschwindigkeit betrifft.

Bei großen Bäumen ist diese Funktion jedoch schwierig zu verwenden.

Konstruktor und Destruktor kopieren

Da ein Baum keine triviale Datenstruktur ist, ist es besser, einen Kopierkonstruktor, einen Destruktor und einen Zuweisungsoperator zu implementieren. Der Destruktor ist einfach rekursiv zu implementieren. Bei sehr großen Bäumen kann es mit "Heap Overflow" umgehen. In diesem Fall wird es iterativ formuliert. Die Idee ist, das Blatt zu entfernen, das den kleinsten Wert aller Blätter darstellt, sodass es sich auf der linken Seite des Baums befindet. Durch das Abschneiden der ersten Blätter entstehen neue, und der Baum schrumpft, bis er schließlich aufhört zu existieren.

Der Kopierkonstruktor kann auch rekursiv implementiert werden, aber seien Sie vorsichtig, wenn eine Ausnahme geworfen wird. Sonst wird der Baum schnell unübersichtlich und fehleranfällig. Deshalb wird die iterative Variante bevorzugt. Die Idee ist, durch den alten Baum und den neuen Baum zu gehen, wie Sie es im Destruktor tun würden, und alle Knoten zu klonen, die im alten Baum sind, aber nicht die neuen.

Bei dieser Methode befindet sich die Implementierung des binären Suchbaums immer in einem gesunden Zustand und kann sogar in einem unvollständigen Zustand vom Destruktor entfernt werden. Wenn eine Ausnahme auftritt, müssen Sie lediglich den Destruktor anweisen, den halbfertigen Baum zu löschen. Aufgabenverw alterlässt sich einfach per Copy & Swap implementieren.

Erstellen eines binären Suchbaums

Optimale binäre Suchbäume sind unglaublich effizient, wenn sie richtig verw altet werden. Einige Regeln für binäre Suchbäume:

1. Ein übergeordneter Knoten hat höchstens 2 untergeordnete Knoten.
2. Der linke untergeordnete Knoten ist immer kleiner als der übergeordnete Knoten.
3. Ein gültiger untergeordneter Knoten ist immer größer oder gleich dem übergeordneten Knoten.

Das Array, das verwendet wird, um den binären Suchbaum zu erstellen:

1. Ein Basis-Integer-Array aus sieben Werten in unsortierter Reihenfolge.
2. Der erste Wert im Array ist 10, also besteht der erste Schritt beim Erstellen des Baums darin, einen 10-Wurzelknoten zu erstellen, wie hier gezeigt.
3. Bei einer Menge von Wurzelknoten sind alle anderen Werte Kinder dieses Knotens. Unter Bezugnahme auf die Regeln besteht der erste Schritt zum Hinzufügen von 7 zum Baum darin, sie mit dem Wurzelknoten zu vergleichen.
4. Wenn der Wert 7 kleiner als 10 ist, wird er zum linken untergeordneten Knoten.
5. Wenn der Wert 7 größer oder gleich 10 ist, wird er nach rechts verschoben. Da bekannt ist, dass 7 kleiner als 10 ist, wird er als linker untergeordneter Knoten bezeichnet.
6. Rekursive Vergleiche für jedes Element durchführen.
7. Führen Sie nach demselben Muster denselben Vergleich mit dem 14. Wert im Array durch.
8. Vergleiche den Wert 14 mit dem Wurzelknoten 10, in dem Wissen, dass 14 das richtige Kind ist.
9. Durch die Anordnung gehen,komm zu 20.
10. Beginnen Sie damit, das Array mit 10 zu vergleichen, je nachdem, welcher Wert größer ist. Gehe also nach rechts und vergleiche es mit 14, er ist über 14 und hat rechts keine Kinder.
11. Jetzt gibt es einen Wert von 1. Folgen Sie dem gleichen Muster wie die anderen Werte, vergleichen Sie 1 mit 10, bewegen Sie sich nach links und vergleichen Sie mit 7 und schließlich mit dem 1 linken Kind des 7. Knotens.
12. Wenn der Wert 5 ist, vergleiche ihn mit 10. Da 5 kleiner als 10 ist, gehe nach links und vergleiche ihn mit 7.
13. Da du weißt, dass 5 kleiner als 7 ist, gehe den Baum weiter nach unten und vergleiche 5 mit 1 Wert.
14. Wenn 1 keine Kinder hat und 5 größer als 1 ist, dann ist 5 ein gültiges Kind von 1 Knoten.
15. Füge zum Schluss den Wert 8 in den Baum ein.
16. Wenn 8 kleiner als 10 ist, bewege es nach links und vergleiche es mit 7, 8 ist größer als 7, also bewege es nach rechts und vervollständige den Baum, wodurch 8 ein richtiges Kind von 7 wird.

Ermittlung und Bewertung der einfachen Eleganz optimaler binärer Suchbäume. Wie bei vielen Themen in der Programmierung liegt die Leistungsfähigkeit binärer Suchbäume in ihrer Fähigkeit, Daten in kleine, verwandte Komponenten aufzulösen. Von nun an können Sie organisiert mit dem gesamten Datensatz arbeiten.

Potenzielle Probleme bei der binären Suche

Binäre Suchbäume sind großartig, aber es gibt ein paar Vorbeh alte, die man beachten sollte. Sie sind in der Regel nur wirksam, wenn sie ausgewogen sind. Ein ausgeglichener Baum ist ein Baum, in demder Unterschied zwischen den Höhen der Teilbäume jedes Knotens im Baum ist höchstens eins. Schauen wir uns ein Beispiel an, das helfen könnte, die Regeln zu verdeutlichen. Stellen wir uns vor, dass das Array sortierbar beginnt.

Wenn Sie versuchen, einen binären Suchbaumalgorithmus auf diesem Baum auszuführen, verhält er sich genau so, als würde er nur durch das Array iterieren, bis der gewünschte Wert gefunden wird. Die Stärke der binären Suche liegt in der Fähigkeit, unerwünschte Werte schnell herauszufiltern. Wenn ein Baum nicht ausgewogen ist, bietet er nicht die gleichen Vorteile wie ein ausbalancierter Baum.

Es ist sehr wichtig, die Daten zu untersuchen, mit denen der Benutzer arbeitet, wenn er einen binären Suchbaum erstellt. Sie können Routinen wie Array-Randomisierung integrieren, bevor Sie einen binären Suchbaum für ganze Zahlen implementieren, um ihn auszugleichen.

Berechnungsbeispiele für binäre Suche

Wir müssen bestimmen, welche Art von Baum sich ergibt, wenn 25 in den folgenden binären Suchbaum eingefügt wird:

10

/

/

5 15

/ /

/ /

2 12 20

Beim Einfügen von x in einen Baum T, der x noch nicht enthält, wird der Schlüssel x immer in ein neues Blatt eingefügt. In Verbindung damit sieht der neue Baum so aus:

10

/

/

5 15

/ /

/ /

2 12 20

25

Welche Art von Baum würden Sie erh alten, wenn Sie 7 in den folgenden binären Suchbaum einfügen würden?

10

/

/

5 15

/ /

/ /

2 12 20

Antwort:

10

/

/

/

5 15

/ / /

/ / /

2 7 12 20

Ein binärer Suchbaum kann verwendet werden, um beliebige Objekte zu speichern. Der Vorteil der Verwendung eines binären Suchbaums anstelle einer verknüpften Liste besteht darin, dass, wenn der Baum einigermaßen ausgeglichen ist und eher einem "vollständigen" als einem "linearen" Baum ähnelt, Einfügungs-, Such- und alle Löschoperationen ausgeführt werden können O(log N) time.