Contents
Was ist ein Binärbaum?
In der Informatik ist ein Binärbaum eine hierarchische Datenstruktur, in der jeder Knoten höchstens zwei Kinder hat, die im Allgemeinen als linkes Kind und rechtes Kind bezeichnet werden. Jeder Knoten in einem Binärbaum enthält drei Knoten , die umfassen Zeiger auf den linken Unterbaum , und Zeiger auf der rechten Unterbaum und Datenelement . Der oberste Knoten im Baum wird als Wurzel bezeichnet. Normalerweise wird ein leerer Baum durch einen NULL- Zeiger dargestellt.
Arten von Binärbäumen basierend auf der Struktur
- Verwurzelter Binärbaum (er hat einen Wurzelknoten und jeder Knoten hat nicht mehr als zwei Kinder).
- Vollständiger Binärbaum (jeder Knoten im Baum hat entweder keine oder höchstens 2 Kinder).
- Degenerierter Baum (jeder übergeordnete Knoten hat nur einen untergeordneten Knoten. Er verhält sich wie eine verkettete Liste).
- Perfekter Binärbaum (alle inneren Knoten haben 2 Kinder und Blätter haben dieselbe Tiefe oder dieselbe Ebene.
- Vollständiger Binärbaum (jede Ebene mit Ausnahme der letzten Ebene ist vollständig gefüllt und alle Knoten befinden sich am linken Rand.
Was Sie über Binärbaum wissen müssen
- Binärbaum ist eine hierarchische Datenstruktur, in der ein Kind null, einen oder maximal zwei Kindknoten haben kann, jeder Knoten enthält einen linken Zeiger, einen rechten Zeiger und ein Datenelement. Es gibt keine spezifische Organisationsstruktur der Knoten im Baum.
- Es gibt verschiedene Arten von Binärbäumen, die beliebtesten sind: Vollständiger Binärbaum, Vollständiger Binärbaum, Erweiterter Binärbaum und Perfekter Binärbaum.
- Übliche Operationen, die an einem binären Baum ausgeführt werden können, sind Löschen, Einfügen und Transversal.
- Binärer Baum kann auch als spezialisierte Baumform beschrieben werden, die Daten in einer Baumstruktur darstellt. In einem binären Baum repräsentiert der oberste Knoten den Wurzelzeiger, während der rechte und der linke Wurzelzeiger Daten in einer Baumstruktur darstellen.
Was ist ein binärer Suchbaum?
In der Informatik, binäre Suche Bäume sind eine nützliche Datenstruktur für schnelle Hinzufügen und Entfernen von Daten. Der binäre Suchbaum ist ein organisierter binärer Baum, in dem es eine relative Reihenfolge gibt, in der Knoten angeordnet werden sollten. Es besteht aus Knoten, die Daten speichern und auch mit bis zu zwei anderen untergeordneten Knoten verknüpft sind. Damit ein binärer Baum ein binärer Suchbaum ist, sollten die Daten aller Knoten im linken Unterbaum des Wurzelknotens kleiner sein als die Daten der Wurzel. Die Daten aller Knoten im rechten Teilbaum des Wurzelknotens sollten größer als gleich den Daten der Wurzel sein. Dabei haben die Blätter ganz links vom Baum die niedrigsten Werte, während die Blätter rechts vom Baum die größten Werte haben.
Arten von binären Suchbäumen
- T-Bäume
- AVL-Bäume
- Spreizbäume
- Tangobäume
- Rot-schwarze Bäume
Was Sie über den binären Suchbaum wissen müssen
- Der binäre Suchbaum ist ein organisierter binärer Baum, in dem es eine relative Reihenfolge gibt, in der Knoten angeordnet werden sollten.
- Die beliebtesten Arten von binären Suchbäumen sind: T-Bäume, AVL-Bäume, Splay-Bäume, Tango-Bäume, Rot-Schwarz-Bäume usw.
- Binäre Suchbäume halten ihre Schlüssel sortiert, daher implementiert Lookup normalerweise eine binäre Suche nach Operationen. Binäre Suchbäume sind besser sortierte binäre Bäume, die ein schnelles und effizientes Suchen, Einfügen und Löschen von Elementen ermöglichen.
- Der binäre Suchbaum kann auch als eine Art von binärem Baum beschrieben werden, bei dem alle Knoten im linken Teilbaum kleiner oder gleich dem Wert des Wurzelknotens sind und der des rechten Teilbaums größer oder gleich der Wert des Wurzelknotens.
Lesen Sie auch : Unterschied zwischen Baum und Graph
Binärer Baum vs. binärer Suchbaum in Tabellenform
| GRUNDLAGENVERGLEICH | BINÄRBAUM | BINÄRER SUCHBAUM |
| Beschreibung | Binärbaum ist eine hierarchische Datenstruktur, in der ein Kind null, einen oder maximal zwei Kindknoten haben kann, jeder Knoten enthält einen linken Zeiger, einen rechten Zeiger und ein Datenelement. Es gibt keine spezifische Organisationsstruktur der Knoten im Baum. | Der binäre Suchbaum ist ein organisierter binärer Baum, in dem es eine relative Reihenfolge gibt, in der Knoten angeordnet werden sollten. |
| Typen | Es gibt verschiedene Arten von Binärbäumen, die beliebtesten sind: Vollständiger Binärbaum, Vollständiger Binärbaum, Erweiterter Binärbaum und Perfekter Binärbaum. | Die beliebtesten Arten von binären Suchbäumen sind: T-Bäume, AVL-Bäume, Splay-Bäume, Tango-Bäume, Rot-Schwarz-Bäume usw. |
| Allgemeine Operationen | Übliche Operationen, die an einem binären Baum ausgeführt werden können, sind Löschen, Einfügen und Transversal. | Binäre Suchbäume halten ihre Schlüssel sortiert, daher implementiert Lookup normalerweise eine binäre Suche nach Operationen. Binäre Suchbäume sind besser sortierte binäre Bäume, die ein schnelles und effizientes Suchen, Einfügen und Löschen von Elementen ermöglichen. |
| Alternative Beschreibung | Binärer Baum kann auch als spezialisierte Baumform beschrieben werden, die Daten in einer Baumstruktur darstellt. In einem binären Baum repräsentiert der oberste Knoten den Wurzelzeiger, während der rechte und der linke Wurzelzeiger Daten in einer Baumstruktur darstellen. | Der binäre Suchbaum kann auch als eine Art von binärem Baum beschrieben werden, bei dem alle Knoten im linken Teilbaum kleiner oder gleich dem Wert des Wurzelknotens sind und der des rechten Teilbaums größer oder gleich der Wert des Wurzelknotens. |
Vorteile von Bäumen (binärer und binärer Suchbaum)
- Bäume spiegeln strukturelle Beziehungen in den Daten wider.
- Bäume ermöglichen ein effizientes Einfügen und Suchen.
- Bäume werden verwendet, um Hierarchien darzustellen.
- Bäume sind sehr flexible Daten, die es ermöglichen, Teilbäume mit minimalem Aufwand zu verschieben.