Binärer Baum in der Datenstruktur: Eigenschaften, Typen, Darstellung und Vorteile

Zu den verschiedenen Arten von Datenstrukturen gehören Binärbäume, die mehr Verwendung finden als die meisten anderen Typen. Zu ihren bemerkenswertesten Anwendungen gehören Peer-to-Peer-Programmierung, Suche, Kryptografie, Netzwerkrouter mit höherer Bandbreite als andere und 3D-Videospiele. Wir werden nun im Detail besprechen, was binäre Bäume in der Datenwissenschaft sind, welche Typen sie haben und wie sie dargestellt werden.

Was sind binäre Bäume?

Wenn Sie schon einmal an normalen Bäumen gearbeitet haben oder sogar ihre Grundlagen kennen, wissen Sie, dass es keine Einschränkungen gibt, wenn es um die Anzahl der Kinder geht, die verschiedene Knoten in diesen Bäumen haben dürfen. Binäre Bäume sind in diesem Sinne etwas anders. Jeder Elternteil oder Knoten in Binärbäumen kann maximal nur zwei Kinder haben.

Alle Knoten in einem Binärbaum haben drei Hauptkomponenten –

• ein Datenelement
• ein richtiger Hinweis
• eine linke Referenz

Der Knoten, der an der Spitze des Baums liegt, wird als Wurzelknoten bezeichnet. Elternknoten sind diejenigen, die Kinder haben. Kindknoten und Elternknoten sind durch Referenzen miteinander verbunden. Knoten, die keine Kinder haben, werden als Blattknoten bezeichnet.

Es ist klar ersichtlich, dass Knoten in Binärbäumen ein Kind, zwei Kinder oder überhaupt keine Kinder haben können. Binäre Bäume sind keine linearen Datenstrukturen wie Warteschlangen, Arrays, Stacks und verknüpfte Listen. Sie sind stattdessen hierarchische Datenstrukturen.

Schauen Sie sich an: Ideen für Data Science-Projekte für Anfänger

Wichtige Eigenschaften von Knoten in Binärbäumen

Ein besseres Verständnis dieser Eigenschaften wird Ihnen helfen, das Beste aus dieser Diskussion über binäre Bäume zu machen. Die Tiefe verschiedener Knoten ist definiert als die Anzahl der Knoten, die auf dem Weg vorhanden sind, der die Wurzel mit einem bestimmten Knoten verbindet. Deshalb ist die Tiefe des Wurzelknotens 0. Andererseits ist die Höhe verschiedener Knoten in einem Binärbaum die Anzahl der Knoten, die in dem Pfad liegen, der einen bestimmten Knoten mit dem Wurzelknoten verbindet. Deshalb ist die Höhe der Blattknoten 0.

Wie Sie deutlich sehen können, wird die Tiefe eines Knotens gemessen, indem Sie vom Wurzelknoten ausgehen und dann nach unten gehen, um diesen Knoten zu erreichen. Bei der Berechnung der Höhe hingegen beginnen wir am betreffenden Knoten und fahren dann zum Wurzelknoten. Beide Male beginnen wir bei 0. Es gibt Leute, die auch Höhe und Tiefe von 1 messen und nicht von 0, was nicht falsch ist und genau das ist, was verschiedene Leute bevorzugen.

Jetzt wird die maximale Tiefe eines Knotens als die Tiefe eines Binärbaums definiert. In ähnlicher Weise wird die maximale Höhe eines Knotens als die Höhe eines Binärbaums definiert. Höhe und Tiefe eines Binärbaums sind also immer gleich.

Erfahren Sie mehr: Datenstrukturen und Algorithmen in Python

Was ist ein binärer Suchbaum?

Ein binärer Suchbaum ist der häufigste aller anderen Arten von binären Bäumen. Es ist ein spezialisierter Binärbaum mit Eigenschaften, die anders und nützlicher sind als jede andere Form eines Binärbaums. Was genau ist ein binärer Suchbaum oder BST? Wie der Name schon sagt, wird ein binärer Suchbaum verwendet, um Daten im Baum zu durchsuchen.

Ein BST verfügt über Eigenschaften, die es ermöglichen, effiziente Suchen zu ermöglichen. Ein BST ist ein binärer Baum, der den Schlüssel des Knotens hat, der kleiner und größer ist als die Knoten im rechten Unterbaum bzw. die Knoten im linken Unterbaum.

Darstellung von Binärbäumen

1. Verknüpfte Darstellung

Binäre Bäume in verknüpfter Darstellung werden im Speicher als verknüpfte Listen gespeichert. Diese Listen haben Knoten, die nicht an benachbarten oder benachbarten Speicherorten gespeichert sind, und sind durch die den Bäumen zugeordnete Eltern-Kind-Beziehung miteinander verknüpft.

In dieser Darstellung hat jeder Knoten drei verschiedene Teile –

• Zeiger, der auf den rechten Knoten zeigt,
• Zeiger, der auf den linken Knoten zeigt,
• Datenelement.

Dies ist die häufigere Darstellung. Alle Binärbäume bestehen aus einem Wurzelzeiger, der in Richtung des Wurzelknotens zeigt. Wenn Sie einen Wurzelknoten sehen, der auf Null oder 0 zeigt, sollten Sie wissen, dass Sie es mit einem leeren Binärbaum zu tun haben. Die rechten und linken Zeiger speichern die Adresse der rechten und linken Kinder des Baums.

2. Sequentielle Darstellung

Obwohl es einfacher als die verknüpfte Darstellung ist, macht es seine Ineffizienz zu einer weniger bevorzugten binären Baumdarstellung der beiden. Die Ineffizienz liegt in der Menge an Platz, die für die Lagerung verschiedener Baumelemente benötigt wird. Die sequentielle Darstellung verwendet ein Array zur Speicherung von Baumelementen.

Die Anzahl der Knoten, die ein Binärbaum hat, definiert die Größe des verwendeten Arrays. Der Wurzelknoten des Binärbaums liegt am ersten Index des Arrays. Der Index, an dem ein bestimmter Knoten gespeichert ist, definiert die Indizes, an denen die rechten und linken Kinder des Knotens gespeichert werden. Ein leerer Baum hat null oder 0 als ersten Index.

Arten von Binärbäumen

1. Vollständige Binärbäume: Vollständige Binärbäume sind solche Binärbäume, deren Knoten entweder zwei oder keine Kinder haben. Mit anderen Worten, ein Binärbaum wird zu einem vollständigen Binärbaum, wenn abgesehen von den Blättern alle anderen Knoten zwei Kinder haben.
2. Vollständige Binärbäume: Vollständige Binärbäume sind solche, bei denen alle ihre verschiedenen Ebenen vollständig gefüllt sind. Die einzige Ausnahme könnte ihre letzte Ebene sein, deren Tasten überwiegend auf der linken Seite liegen. Ein binärer Heap wird oft als Beispiel für einen vollständigen binären Baum genommen.
3. Perfekte Binärbäume: Perfekte Binärbäume sind Binärbäume, deren Blätter auf der gleichen Ebene vorhanden sind und deren interne Knoten zwei Kinder tragen. Ein gängiges Beispiel für einen perfekten binären Baum ist ein Ahnenstammbaum.
4. Pathologisch degenerierte Binärbäume: Degenerierte Bäume sind solche Binärbäume, deren interne Knoten ein Kind haben. Ihre Leistungsniveaus ähneln verknüpften Listen. Erfahren Sie mehr über die Arten von Binärbäumen.

Lesen Sie: Die sechs am häufigsten verwendeten Datenstrukturen in R

Vorteile von Binärbäumen

1. Ein idealer Weg, um mit der hierarchischen Art der Datenspeicherung zu gehen
2. Reflektieren strukturelle Beziehungen, die in dem gegebenen Datensatz vorhanden sind
3. Machen Sie das Einfügen und Löschen schneller als verknüpfte Listen und Arrays
4. Eine flexible Möglichkeit, Daten zu speichern und zu verschieben
5. Werden verwendet, um so viele Knoten wie möglich zu speichern
6. Sind beim Zugriff auf Elemente schneller als verknüpfte Listen und langsamer als Arrays

Fazit

In diesem Blog haben wir diskutiert, was binäre Bäume in Datenstrukturen sind, sowie über ihre Typen, ihre Darstellungen und ihre Vorteile gesprochen. Die beiden Hauptverwendungen der Bäume sind das Suchen und Speichern von Daten, und daher sind sie ein wesentlicher Bestandteil des Studiums der Datenwissenschaft und verwandter Bereiche.

Wenn Sie neugierig sind, mehr über binäre Bäume in Datenstrukturen und Datenwissenschaft zu erfahren, schauen Sie sich das Executive PG Program 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, Mentoring mit Branchenexperten, 1-on-1 mit Branchenmentoren, mehr als 400 Stunden Lern- und Jobunterstützung bei Top-Unternehmen.