Was ist ein binärer Suchbaum?

Ein binärer Suchbaum ist eine der verschiedenen Datenstrukturen, die uns helfen, Daten zu organisieren und zu sortieren. Es ist eine effiziente Möglichkeit, Daten in einer Hierarchie zu speichern und ist sehr flexibel.

In diesem Artikel werfen wir einen genaueren Blick auf seine Funktionsweise – zusammen mit seinen Eigenschaften und Anwendungen.

Was ist ein binärer Suchbaum?

Ein binärer Suchbaum ist eine Datenstruktur, die aus Knoten besteht – ähnlich wie bei verknüpften Listen. Es kann zwei Arten von Knoten geben: einen übergeordneten und einen untergeordneten Knoten. Der Wurzelknoten ist der Anfangspunkt der Struktur, die sich in zwei untergeordnete Knoten verzweigt, die als linker Knoten und rechter Knoten bezeichnet werden.

Jeder Knoten kann nur von seinem Elternteil referenziert werden, und wir können die Knoten des Baums je nach Richtung durchlaufen. Der binäre Suchbaum hat drei Haupteigenschaften:

1. Der linke Knoten ist kleiner als sein Elternknoten.
instagram viewer
2. Der rechte Knoten ist größer als sein Elternknoten.
3. Der linke und der rechte Teilbaum müssen binäre Suchbäume sein.

Ein perfekter binärer Suchbaum wird erreicht, wenn alle Ebenen gefüllt sind und jeder Knoten einen linken und einen rechten untergeordneten Knoten hat.

Verwandt: Data Science-Bibliotheken für Python, die jeder Data Scientist verwenden sollte

Grundlegende Operationen eines binären Suchbaums

Nachdem Sie nun eine bessere Vorstellung davon haben, was ein binärer Suchbaum ist, können wir uns unten seine grundlegenden Operationen ansehen.

1. Suchvorgang

Die Suche ermöglicht es uns, einen bestimmten Wert im Baum zu finden. Wir können zwei Arten von Suchen verwenden: Breitensuche (BFS) und Tiefensuche (DFS). Die Breitensuche ist ein Suchalgorithmus, der am Wurzelknoten beginnt und horizontal von Seite zu Seite durchläuft, bis das Ziel gefunden ist. Jeder Knoten wird während dieser Suche einmal besucht.

Die Tiefensuche hingegen durchquert den Baum vertikal – beginnend mit dem Wurzelknoten und durcharbeiten einen einzelnen Zweig. Wenn das Ziel gefunden wird, endet die Operation. Aber wenn nicht, durchsucht es die anderen Knoten.

2. Einfügevorgang

Die Einfügeoperation verwendet die Suchoperation, um die Stelle zu bestimmen, an der der neue Knoten eingefügt werden soll. Der Prozess beginnt beim Root-Knoten und die Suche beginnt, bis das Ziel erreicht ist. Beim Einfügen sind drei Fälle zu berücksichtigen.

• Fall 1: Wenn kein Knoten vorhanden ist. Der einzufügende Knoten wird zum Wurzelknoten.

• Fall 2: Es gibt keine Kinder. In diesem Fall wird der Knoten mit dem Wurzelknoten verglichen. Wenn es größer ist, wird es das richtige Kind; andernfalls wird es das linke Kind.

• Fall 3: Wenn die Wurzel und ihre Kinder vorhanden sind. Der neue Knoten wird mit jedem Knoten auf seinem Pfad verglichen, um zu bestimmen, welchen Knoten er als nächstes besucht. Wenn der Knoten größer als der Wurzelknoten ist, durchquert er den rechten Unterbaum oder sonst den linken. In ähnlicher Weise werden auf jeder Ebene Vergleiche durchgeführt, um zu bestimmen, ob sie nach rechts oder links fahren wird, bis sie ihr Ziel erreicht.

3. Vorgang löschen

Die Löschoperation wird verwendet, um einen bestimmten Knoten innerhalb des Baums zu entfernen. Das Löschen gilt als schwierig, da nach dem Entfernen eines Knotens der Baum entsprechend neu organisiert werden muss. Es sind drei Hauptfälle zu berücksichtigen:

• Fall 1: Löschen eines Blattknotens. Ein Blattknoten ist ein Knoten ohne Kinder. Dies ist am einfachsten zu entfernen, da es keinen anderen Knoten betrifft; wir durchqueren einfach den Baum, bis wir ihn erreichen und löschen ihn.

• Fall 2: Löschen eines Knotens mit einem Kind. Das Löschen eines übergeordneten Knotens mit einem Knoten führt dazu, dass der untergeordnete Knoten seine Position einnimmt und alle nachfolgenden Knoten eine Ebene höher rücken. An der Struktur der Unterbäume ändert sich nichts.

• Fall 3: Löschen eines Knotens mit zwei Kindern. Wenn wir einen Knoten mit zwei Kindern entfernen müssen, müssen wir zuerst einen nachfolgenden Knoten finden, der seine Position einnehmen kann. Zwei Knoten können den entfernten Knoten ersetzen, den Nachfolger oder Vorgänger in der Reihenfolge. Der inorder-Nachfolger ist das am weitesten links stehende Kind des rechten Teilbaums, und der inorder-Vorgänger ist das am weitesten rechts stehende Kind des linken Teilbaums. Wir kopieren den Inhalt des Nachfolgers/Vorgängers auf den Knoten und löschen den ingeordneten Nachfolger/Vorgänger.

Verwandt: So erstellen Sie Datenstrukturen mit JavaScript ES6-Klassen

So durchqueren Sie einen binären Suchbaum

Traversal ist der Prozess, durch den wir durch einen binären Suchbaum navigieren. Dies geschieht, um ein bestimmtes Element zu lokalisieren oder einen Umriss des Baums zu drucken. Wir starten immer beim Wurzelknoten und müssen den Kanten folgen, um zu den anderen Knoten zu gelangen. Jeder Knoten sollte als Unterbaum betrachtet werden, und der Vorgang wird wiederholt, bis alle Knoten besucht sind.

• Durchqueren der Reihenfolge: Wenn Sie der Reihe nach durchqueren, wird eine Karte in aufsteigender Reihenfolge erstellt. Bei dieser Methode beginnen wir mit dem linken Teilbaum und fahren bis zur Wurzel und dem rechten Teilbaum fort.

• Vorbestellungsdurchquerung: Bei dieser Methode wird zuerst der Wurzelknoten besucht, gefolgt vom linken Teilbaum und dem rechten Teilbaum.

• Post-Order-Durchquerung: Bei dieser Durchquerung wird der Wurzelknoten zuletzt besucht. Wir beginnen beim linken Teilbaum, dann beim rechten Teilbaum und dann beim Wurzelknoten.

Reale Anwendungen

Wie verwenden wir also binäre Suchbaumalgorithmen? Wie zu vermuten ist, sind sie beim Suchen und Sortieren äußerst effizient. Die größte Stärke von Binärbäumen ist ihre organisierte Struktur. Es ermöglicht die Suche mit bemerkenswerter Geschwindigkeit, indem die zu analysierende Datenmenge pro Durchgang um die Hälfte reduziert wird.

Binäre Suchbäume ermöglichen es uns, einen sich dynamisch ändernden Datensatz effizient in einer organisierten Form zu verwalten. Für Anwendungen, bei denen häufig Daten eingefügt und entfernt werden, sind sie sehr hilfreich. Videospiel-Engines verwenden einen Algorithmus, der auf Bäumen basiert, die als Binärraumpartition bekannt sind, um beim geordneten Rendern von Objekten zu helfen. Microsoft Excel und die meisten Tabellenkalkulationsprogramme verwenden binäre Bäume als grundlegende Datenstruktur.

Sie werden vielleicht überrascht sein zu wissen, dass Morsecode einen binären Suchbaum verwendet, um Daten zu codieren. Ein weiterer wichtiger Grund, warum binäre Suchbäume so nützlich sind, sind ihre vielfältigen Variationen. Ihre Flexibilität hat dazu geführt, dass zahlreiche Varianten geschaffen wurden, um alle möglichen Probleme zu lösen. Bei richtiger Verwendung sind binäre Suchbäume ein großer Vorteil.

Binäre Suchbäume: Der perfekte Ausgangspunkt

Eine der wichtigsten Methoden, um das Fachwissen eines Ingenieurs zu messen, besteht in der Kenntnis und Anwendung von Datenstrukturen. Datenstrukturen sind hilfreich und können zu einem effizienteren System beitragen. Binäre Suchbäume sind eine großartige Einführung in Datenstrukturen für jeden beginnenden Entwickler.

15 JavaScript-Array-Methoden, die Sie heute beherrschen sollten

Sie möchten JavaScript-Arrays verstehen, kommen aber nicht damit zurecht? Sehen Sie sich unsere JavaScript-Array-Beispiele an, um eine Anleitung zu erhalten.

Weiter lesen

Über den Autor