4 Arten von Bäumen in der Datenstruktur erklärt: Eigenschaften und Anwendungen

Was ist ein Baum in der Datenstruktur?

Ein Baum ist eine Art Datenstruktur, die hierarchische Daten darstellt. Es hat eine nichtlineare Struktur, die aus Knoten besteht, die durch Kanten verbunden sind. Unter den anderen Arten von Datenstrukturen, die Operationen in einer linearen Datenstruktur ausführen, nimmt die Komplexität mit zunehmender Datengröße zu. Die Baumdatenstruktur bietet jedoch einen schnelleren Zugriff auf die nichtlinearen Daten. Durch die Verfügbarkeit der verschiedenen Arten von Datenstrukturen und der damit verbundenen Algorithmen ist die Aufgabenerfüllung zu einem einfachen und effizienten Weg geworden.

Einige Terminologien im Zusammenhang mit Bäumen in Datenstrukturen sind:

• Knoten : Der Knoten ist eine Entität in einer Baumdatenstruktur, die einen Schlüssel oder einen Wert und Zeiger auf seine untergeordneten Knoten enthält.
• Untergeordneter Knoten : Ein untergeordneter Knoten ist der Nachkomme eines beliebigen Knotens.
• Blattknoten: Die Knoten, die keine untergeordneten Knoten haben und die untersten Knoten in einem Baum sind. Sie werden auch als externe Knoten bezeichnet.
• Wurzel : Es ist der oberste Punkt eines Baumes.
• Interner Knoten : Der Knoten mit mindestens einem untergeordneten Knoten.
• Kante: Eine Kante bezieht sich auf die Verbindung zwischen zwei beliebigen Knoten in einem Baum.
• Höhe eines Knotens: Anzahl der Kanten vom Knoten bis zum tiefsten Blatt.
• Tiefe eines Knotens : Anzahl der Kanten von der Wurzel zum Knoten.
• Höhe eines Baums : Höhe des Wurzelknotens.
• Grad eines Knotens : Gesamtzahl der Verzweigungen zu diesem Knoten.
• Wald: Eine Sammlung disjunkter Bäume.

Baumarten

1. Binärer Baum

Der Binärbaum ist eine Art Baumdatenstruktur, bei der jeder übergeordnete Knoten maximal zwei untergeordnete Knoten hat. Wie der Name schon sagt, bedeutet binär zwei, daher kann jeder Knoten 0, 1 oder 2 Knoten haben. Eine binäre Baumdatenstruktur ist in Fig. 1 gezeigt. Knoten 1 im Baum enthält zwei Zeiger, einen für jeden untergeordneten Knoten. Knoten 2 hat wieder jeweils zwei Zeiger für die beiden Kindknoten. Wohingegen Knoten 3, 5 und 6 Blattknoten sind und daher sowohl auf dem linken als auch auf dem rechten Teil Nullzeiger haben.

Abbildung 1: Eine Darstellung eines Binärbaums ( https://www.javatpoint.com/binary-tree ).

Eigenschaften eines Binärbaums

• Die maximale Anzahl von Knoten auf jeder Ebene von I beträgt 2 i .
• Die Höhe des Baums in Abbildung 1 beträgt 3, was bedeutet, dass die maximale Anzahl von Knoten (1 + 2 + 4 + 8) = 15 ist.

• Auf der Höhe h beträgt die maximal mögliche Knotenzahl (20 + 21 + 22+….2h) = 2h+1 -1.

• Auf der Höhe h ist die minimal mögliche Knotenzahl gleich h+1.

• Eine minimale Anzahl von Knoten repräsentiert einen Baum mit maximaler Höhe und umgekehrt.

Auch die Binärbäume lassen sich in folgende Baumarten unterteilen:

• Vollständiger Binärbaum: Dies ist eine spezielle Art von Binärbaum. In dieser Baumdatenstruktur hat jeder Elternknoten oder ein interner Knoten entweder zwei Kinder oder keine Kinderknoten.
• Perfekter Binärbaum: Bei dieser Art von Baumdatenstruktur hat jeder interne Knoten genau zwei untergeordnete Knoten und alle Blattknoten befinden sich auf derselben Ebene.
• Vollständiger Binärbaum: Er ähnelt dem vollständigen Binärbaum mit einigen Unterschieden.
• Jede Ebene ist vollständig gefüllt.
• Die Blattknoten neigen sich nach links vom Baum.
• Es ist nicht erforderlich, dass der letzte Blattknoten das richtige Geschwister hat, dh ein vollständiger Binärbaum muss kein vollständiger Binärbaum sein.
• Degenerierter oder pathologischer Baum: Diese Bäume haben ein einzelnes Kind entweder links oder rechts vom Elternknoten.
• Schiefer binärer Baum: Es ist ein pathologischer oder entarteter Baum, bei dem der Baum entweder von den linken Knoten oder den rechten Knoten dominiert wird. Daher gibt es zwei Arten von schiefen Binärbäumen, nämlich den linksschiefen oder den rechtsschiefen Binärbaum.
• Ausgeglichener Binärbaum: Die Differenz zwischen der Höhe des linken und rechten Teilbaums für jeden Knoten ist entweder 0 oder 1.

2. Binärer Suchbaum

Diese Baumstrukturen sind nichtlinear und ein Knoten ist mit einer Anzahl von Knoten verbunden. Der Knoten kann mit höchstens zwei untergeordneten Knoten verbunden werden. Es wird ein binärer Suchbaum genannt, weil:

• Jeder Knoten hat maximal zwei untergeordnete Knoten.
• Es kann verwendet werden, um ein Element in 0(log(n))-Zeit zu suchen und wird daher als Suchbaum bezeichnet.

Abbildung: Ein Beispiel für einen binären Suchbaum ( https://www.tutorialspoint.com/data_structures_algorithms/binary_search_tree.htm )

Eigenschaften eines binären Suchbaums sind:

• Der Wert in allen Knoten eines linken Teilbaums sollte kleiner sein als der Wert im Wurzelknoten.
• Der Wert in allen Knoten eines rechten Teilbaums sollte größer sein als der Wert im Wurzelknoten.

3. AVL-Baum

Die AVL-Bäume sind die Typen oder Varianten eines Binärbaums. Es besteht aus Eigenschaften sowohl aus dem binären als auch aus einem binären Suchbaum. Diese von Adelson Velsky Lindas erfundenen Bäume sind selbstbalancierend, was bedeutet, dass die Höhe des linken Teilbaums und des rechten Teilbaums ausgeglichen ist. Dieses Gleichgewicht wird in Form eines Ausgleichsfaktors gemessen.

Ausgleichsfaktor:

• Es ist der Unterschied zwischen dem linken Teilbaum und dem rechten Teilbaum.
• Der Wert eines Ausgleichsfaktors muss 0, –1 oder 1 sein. Daher sollte jeder Knoten eines AVL-Baums aus einem Ausgleichsfaktorwert bestehen, dh 0, –1 oder 1.
• Ausgleichsfaktor = (Höhe des linken Teilbaums – Höhe des rechten Teilbaums)
• Ein AVL-Baum wird als ausgeglichener Baum bezeichnet, wenn der Ausgleichsfaktor jedes Knotens zwischen -1 und 1 liegt.

Andere Werte von Knoten als -1 bis 1 in einem AVL-Baum stellen einen unausgeglichenen Baum dar, der ausgeglichen werden muss.

• Wenn ein Knoten einen Ausgleichsfaktor von 1 hat, bedeutet dies, dass der linke Teilbaum eine Ebene höher ist als der rechte Teilbaum.
• Wenn ein Knoten einen Ausgleichsfaktor von 0 hat, bedeutet dies, dass die Höhe des linken Teilbaums und des rechten Teilbaums gleich ist.
• Wenn ein Knoten einen Ausgleichsfaktor von –1 hat, bedeutet dies, dass der rechte Teilbaum eine Ebene höher ist als der linke Teilbaum oder dass der linke Teilbaum eine Ebene niedriger als der rechte Teilbaum ist.

4. B-Baum

B-Baum ist eine allgemeinere Form eines binären Suchbaums. Es ist auch als höhenausgeglichener m-Wege-Baum bekannt, wobei m die Ordnung des Baums ist. Jeder Knoten des Baums kann mehr als einen Schlüssel und mehr als zwei untergeordnete Knoten haben. Im Fall eines binären Baums befinden sich die Blattknoten möglicherweise nicht auf derselben Ebene. Im Fall eines B-Baums sollten sich jedoch alle Blattknoten auf derselben Ebene befinden.

Eigenschaften eines B-Baums:

• Schlüssel werden in aufsteigender Reihenfolge für jeden Knoten x gespeichert.
• In jedem Knoten existiert ein boolescher Wert „x.leaf“, der wahr ist, wenn x ein Blatt ist.
• Die internen Knoten sollten höchstens „n-1“ Schlüssel haben, wobei n die Reihenfolge des Baums ist. Es sollte auch einen Zeiger für jedes Kind haben.
• Alle Knoten mit Ausnahme des Wurzelknotens haben höchstens n Kinder und mindestens n/2 Kinder.
• Die Blattknoten des Baums haben die gleiche Tiefe.
• Der Wurzelknoten hat mindestens 1 Schlüssel und mindestens zwei Kinder.
• Wenn n ≥ 1, dann gilt für jeden B-Baum mit n Schlüsseln der Höhe h und dem Mindestgrad t ≥ 2, h ≥ logt (n+1)/2.

Anwendungen

• Der binäre Suchbaum kann zum Suchen eines Elements in einer Menge von Elementen angewendet werden.
• Heap-Bäume werden für die Heap-Sortierung verwendet.
• Moderne Router verwenden eine Art Baum namens Tries zum Speichern von Routing-Informationen.
• Die B-Bäume und die T-Bäume werden hauptsächlich von populären Datenbanken verwendet, um ihre Daten zu speichern.
• Ein Syntaxbaum wird von Compilern verwendet, um die Syntax jedes geschriebenen Programms zu validieren.

Fazit

Datenstrukturen bieten eine organisierte Möglichkeit zum Speichern der Daten für eine einfache Verwaltung und effektive Handhabung. Es existieren verschiedene Typen von Datenstrukturen für unterschiedliche Datentypen. Basierend auf der Art der zu speichernden Daten wird diese vom Benutzer ausgewählt.

Bäume sind Typen solcher Datenstrukturen, in denen der hierarchische Datentyp gespeichert werden kann. Die Daten werden in den Knoten gespeichert, die manchmal die Referenz für andere Knoten speichern, die als untergeordnete Knoten bezeichnet werden.

Basierend auf der Anzahl der untergeordneten Knoten können Bäume, wie im Artikel erwähnt, in verschiedene Typen eingeteilt werden. Basierend auf der Anordnung der Knoten in den Baumtypen hat jede Baumstruktur zugeordnete Eigenschaften. Mit den unterschiedlichen Arten von Operationen, die von den unterschiedlichen Klassen von Bäumen durchgeführt werden können, hat diese Art von Datenstruktur Anwendungen in Sortieralgorithmen und Datenspeicherung gefunden.

Ein Executive PG Program in Software Development – ​​Specialization in Full Stack Development, kuratiert von upGrad & IIIT-Bangalore, kann Ihnen helfen, Ihr Profil zu verbessern und sich bessere Beschäftigungsmöglichkeiten als Programmierer zu sichern.