Website-Suche

Was ist ein binärer Suchbaum?


Binäre Suchbäume eignen sich zum Organisieren von Daten. Hier finden Sie eine vollständige Beschreibung ihrer Funktionsweise.

Ein binärer Suchbaum ist eine der verschiedenen Datenstrukturen, die uns beim Organisieren und Sortieren von Daten helfen. Es ist eine effiziente und sehr flexible Möglichkeit, Daten in einer Hierarchie zu speichern.

In diesem Artikel werfen wir einen genaueren Blick auf seine Funktionsweise sowie seine Eigenschaften und Anwendungen.

Was ist ein binärer Suchbaum?

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

Auf jeden Knoten kann nur von seinem übergeordneten Knoten verwiesen 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 übergeordneter Knoten.
  2. Der rechte Knoten ist größer als sein übergeordneter Knoten.
  3. Die linken und rechten Teilbäume 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.

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

Durch die Suche können wir einen bestimmten im Baum vorhandenen Wert 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 einer Seite zur anderen verläuft, bis das Ziel gefunden ist. Jeder Knoten wird bei dieser Suche einmal besucht.

Die Tiefensuche hingegen durchläuft den Baum vertikal – beginnend beim Wurzelknoten und dann einen einzelnen Zweig nach unten. Wenn das Ziel gefunden wird, endet die Operation. Wenn nicht, durchsucht es die anderen Knoten.

2. Operation einfügen

Die Einfügeoperation verwendet die Suchoperation, um die Position zu bestimmen, an der der neue Knoten eingefügt werden soll. Der Prozess beginnt am Wurzelknoten 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 Stammknoten.

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

  • Fall 3: Wenn die Wurzel und ihre untergeordneten Elemente 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 den linken. Ebenso werden auf jeder Ebene Vergleiche angestellt, um zu bestimmen, ob die Strecke nach rechts oder links verläuft, bis sie ihr Ziel erreicht.

3. Vorgang löschen

Der Löschvorgang 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 untergeordnete Elemente. Dies lässt sich am einfachsten entfernen, da es keine Auswirkungen auf andere Knoten hat. Wir durchlaufen einfach den Baum, bis wir ihn erreichen und löschen ihn.

  • Fall 2: Löschen eines Knotens mit einem untergeordneten Knoten. 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 nach oben 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 Inorder-Nachfolger oder den Vorgänger. 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 Inorder-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 auszudrucken. Wir beginnen immer am 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.

  • Durchlauf in der richtigen Reihenfolge: Durch den Durchlauf in der richtigen Reihenfolge wird eine Karte in aufsteigender Reihenfolge erstellt. Bei dieser Methode beginnen wir mit dem linken Teilbaum und fahren mit der Wurzel und dem rechten Teilbaum fort.

  • Pre-Order Traversal: Bei dieser Methode wird zuerst der Wurzelknoten besucht, gefolgt vom linken Teilbaum und dem rechten Teilbaum.

  • Post-Order-Traversal: Bei diesem Traversal wird zuletzt der Wurzelknoten besucht. Wir beginnen mit dem linken Teilbaum, dann mit dem rechten Teilbaum und dann mit dem Wurzelknoten.

Anwendungen aus der Praxis

Wie nutzen wir also binäre Suchbaumalgorithmen? Es lässt sich vermuten, dass sie beim Suchen und Sortieren äußerst effizient sind. Die größte Stärke binärer Bäume ist ihre organisierte Struktur. Dadurch kann die Suche mit bemerkenswerter Geschwindigkeit durchgeführt werden, da die zu analysierende Datenmenge pro Durchgang halbiert wird.

Mit binären Suchbäumen können wir einen sich dynamisch ändernden Datensatz effizient und organisiert verwalten. Für Anwendungen, bei denen häufig Daten eingefügt und entfernt werden, sind sie sehr hilfreich. Videospiel-Engines verwenden einen auf Bäumen basierenden Algorithmus, der als binäre Raumpartition bekannt ist, um bei der Ordnungsdarstellung von Objekten zu helfen. Microsoft Excel und die meisten Tabellenkalkulationsprogramme verwenden Binärbäume als grundlegende Datenstruktur.

Sie werden vielleicht überrascht sein zu erfahren, dass Morsecode einen binären Suchbaum zum Codieren von Daten verwendet. 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 zur Lösung verschiedenster Probleme entstanden sind. Bei richtiger Anwendung sind binäre Suchbäume eine große Bereicherung.

Binäre Suchbäume: Der perfekte Ausgangspunkt

Eine der wichtigsten Möglichkeiten, die Fachkompetenz eines Ingenieurs zu beurteilen, ist seine Kenntnis und Anwendung von Datenstrukturen. Datenstrukturen sind hilfreich und können dabei helfen, ein effizienteres System zu schaffen. Binäre Suchbäume sind eine großartige Einführung in Datenstrukturen für jeden Entwickler, der gerade anfängt.

Verwandte Artikel: