Binärer Baum vs. binärer Suchbaum: Unterschied zwischen binärem Baum und binärem Suchbaum

Einführung

Beim Sortieren werden die Daten in einer systematischen Reihenfolge angeordnet, damit sie effektiver analysiert werden können. Der Vorgang des Identifizierens eines bestimmten Datensatzes wird als Suchen bezeichnet. Wenn die Daten richtig in einer bestimmten Reihenfolge sortiert sind, wird die Suche zu einer einfachen und effizienten Aufgabe. Dieser Artikel behandelt eine der wichtigsten nichtlinearen Datenstrukturen, nämlich Bäume.

Bäume werden hauptsächlich verwendet, um Daten darzustellen, indem eine hierarchische Beziehung zwischen den Elementen demonstriert wird. Zum Beispiel Inhaltsverzeichnis, Stammbaum. Technisch gesehen kann ein Baum als eine endliche Menge „T“ aus einem oder mehreren Knoten definiert werden, sodass ein Knoten als Wurzel des Baums zugewiesen wird und die anderen Knoten in n>=0 disjunkte Mengen T1, T2, T3 unterteilt werden. T4 …. Tn und werden als Unterbäume oder Kinder dieses Wurzelknotens bezeichnet.

Was ist ein Binärbaum?

Ein binärer Baum ist eine nichtlineare Datenstruktur, bei der ein Knoten entweder 0, 1 oder 2 Knoten haben kann. Jeder Knoten im Binärbaum wird entweder als Elternknoten oder als Kindknoten bezeichnet. Der oberste Knoten des Binärbaums wird als Wurzelknoten bezeichnet. Jeder übergeordnete Knoten kann höchstens 2 untergeordnete Knoten haben, nämlich den linken untergeordneten Knoten und den rechten untergeordneten Knoten.

Ein Knoten in einem Binärbaum hat drei Felder:

1. Datenelement – ​​Es speichert den Datenwert, der vom Knoten gespeichert werden soll.
2. Zeiger auf das linke untergeordnete Element – ​​Es speichert die Referenz (oder Adresse) auf den linken untergeordneten Knoten.
3. Zeiger auf das rechte untergeordnete Element – ​​Es speichert den Verweis auf den rechten untergeordneten Knoten.

Auf diese Weise werden mehrere Knoten zu einem Binärbaum zusammengefasst.

Ein Binärbaum kann dargestellt werden als:

Quelle

In der obigen Abbildung hat der Wurzelknoten 2 zwei Kinder (oder untergeordnete Knoten), 7 und 5. 7 wird als linker untergeordneter Knoten und 5 als rechter untergeordneter Knoten bezeichnet. Auf diese Weise fungiert jeder der untergeordneten Knoten als übergeordneter Knoten für mehrere andere Knoten und repräsentiert zusammen den Binärbaum.

Check out: Arten von Binärbäumen

Im Binärbaum verwendete Terminologien

Knoten : Die grundlegende Darstellung eines Endpunkts in einem Baum.

Wurzelknoten : Der oberste Knoten eines Binärbaums.

Elternknoten : Wenn ein Knoten durch Kanten mit einem anderen Knoten verbunden ist, wird er als Elternknoten bezeichnet. In einem Binärbaum kann ein übergeordneter Knoten maximal 2 untergeordnete Knoten haben.

Kindknoten : Wenn ein Knoten einen Vorgänger hat, wird er als Kindknoten bezeichnet.

Blattknoten : Ein Knoten, der keinen untergeordneten Knoten hat, wird als Blattknoten bezeichnet.

Tiefe eines Knotens : Dies ist der Abstand vom Wurzelknoten zu diesem bestimmten Knoten, dessen Tiefe gemessen werden soll.

Höhe des Baums : Es ist die längste Entfernung vom Wurzelknoten zum Blattknoten.

Dies sind einige grundlegende Terminologien eines binären Baums. Lassen Sie uns mit diesem grundlegenden Verständnis eines binären Baums zu einer Weiterentwicklung des binären Baums übergehen, die als binärer Suchbaum bekannt ist.

Lesen Sie auch: Binärer Suchalgorithmus: Funktion, Vorteile, Zeit- und Raumkomplexität

Was ist ein binärer Suchbaum

Wie der Name schon sagt, ist ein binärer Suchbaum oder BST ein Baum, der zum Sortieren, Abrufen und Suchen von Daten verwendet wird. Es ist auch eine Art nichtlineare Datenstruktur, in der die Knoten in einer bestimmten Reihenfolge angeordnet sind. Daher wird er auch als „ Ordered Binary Tree “ bezeichnet. Es hat die folgenden Eigenschaften:

• Der linke Teilbaum eines Knotens hat Knoten, die nur kleiner als der Schlüssel dieses Knotens sind.
• Der rechte Teilbaum eines Knotens hat Knoten, die nur größer als der Schlüssel dieses Knotens sind.
• Jeder Knoten hat unterschiedliche Schlüssel und Duplikate sind im binären Suchbaum nicht erlaubt.
• Der linke und der rechte Teilbaum müssen ebenfalls ein binärer Suchbaum sein.

Lassen Sie uns dieses Konzept visualisieren, um ein klares Verständnis von binären Suchbäumen zu erhalten.

Quelle

In der obigen Abbildung sehen wir, dass der Wert des Wurzelknotens 8 ist. Bei weiterer Prüfung wird beobachtet, dass alle Werte im linken Teilbaum kleiner sind als der Wert des Wurzelknotens und alle Werte im rechten Teilbaum haben Werte, die größer als der Wurzelknoten sind. Darüber hinaus wird darauf hingewiesen, dass jeder Wert im binären Suchbaum einzigartig ist und es keine Duplikate gibt. Somit werden die oben angegebenen Eigenschaften des binären Suchbaums verifiziert.

In einem weiteren Beispiel sehen wir, dass die linken und rechten Unterbäume binäre Suchbäume mit eindeutigen Werten im gesamten Baum sind. Der Wert am Blattknoten im linken Teilbaum ist 12, was größer ist als der Wert des Wurzelknotens, der 12 ist. Somit erfüllt dies nicht die Eigenschaft des BST und ist daher kein binärer Suchbaum.

Suchvorgang in einem BST –

Betrachten Sie einen binären Suchbaum mit den unten angegebenen Werten. Lassen Sie uns verstehen, wie die Suchoperation durchgeführt wird, um 9 aus dem binären Suchbaum zu erhalten.

Quelle

Um die binäre Suche durchzuführen, ordnen wir zunächst alle ganzen Zahlen in einem sortierten Array an. Dies wird als Suchraum bezeichnet. Dieser Suchraum soll aus zwei Zeigern bestehen, die als Start- und Endzeiger bezeichnet werden. Das Array des oben angegebenen binären Suchbaums wird dargestellt als:

Der erste Schritt besteht darin, den mittleren Wert des Arrays zu berechnen und ihn mit dem zu suchenden Wert zu vergleichen, in unserem Fall 9. Dies erfolgt durch Berechnung von n/2, wobei n die Gesamtzahl der Elemente im Array (BST) und 6 ist. Somit ist das 3. Element das mittlere Element, das 5 ist.

Da nun das mittlere Element mit 9 verglichen wird und ungleich (größer) ist, wird die Suchoperation im rechten Array durchgeführt. Auf diese Weise wird der Suchvorgang auf die Hälfte reduziert, wie unten gezeigt:

Im nächsten Schritt wird das mittlere Element berechnet und mit 9 ermittelt, was unserem zu suchenden Element entspricht.

Binärer Baum vs. binärer Suchbaum –

Nachdem wir nun ein grundlegendes Verständnis sowohl des binären Baums als auch des binären Suchbaums haben, wollen wir kurz einige der Unterschiede zwischen beiden zusammenfassen.

Fazit

Daher folgern wir, dass, obwohl sowohl der binäre Baum als auch der binäre Suchbaum eine gemeinsame hierarchische Struktur mit einer Sammlung von Knoten haben, sie mehrere Unterschiede in ihrer Anwendung aufweisen. Ein binärer Baum ist eine Grundstruktur mit einer einfachen Regel, dass kein Elternteil mehr als 2 Kinder haben darf, während der binäre Suchbaum eine Variante des binären Baums ist, die einer bestimmten Reihenfolge folgt, in der die Knoten organisiert werden sollten.

Wenn Sie neugierig sind, mehr über binäre Bäume und binäre Suchbäume zu erfahren, sehen Sie sich das PG Diploma in Data Science von IIIT-B & upGrad an, das für Berufstätige entwickelt wurde und mehr als 10 Fallstudien und Projekte, praktische praktische Workshops und Mentoring in der Industrie bietet Experten, 1-on-1 mit Mentoren aus der Branche, mehr als 400 Stunden Lern- und Jobunterstützung bei Top-Unternehmen.

Lernen Sie Data Science-Kurse online von den besten Universitäten der Welt. Verdienen Sie Executive PG-Programme, Advanced Certificate-Programme oder Master-Programme, um Ihre Karriere zu beschleunigen.