Eine nichtlineare Datenstruktur besteht aus einer Sammlung der Elemente, die auf einer Ebene verteilt sind. Dies bedeutet, dass zwischen den Elementen keine solche Reihenfolge besteht, wie sie in einer linearen Datenstruktur vorhanden ist.
Vergleichstabelle
| Basis zum Vergleich | Baum | Graph |
|---|---|---|
| Pfad | Nur einer zwischen zwei Ecken. | Es ist mehr als ein Pfad erlaubt. |
| Wurzelknoten | Es hat genau einen Wurzelknoten. | Graph hat keinen Wurzelknoten. |
| Schleifen | Es sind keine Schleifen erlaubt. | Graph kann Schleifen haben. |
| Komplexität | Weniger komplex | Vergleichsweise komplexer |
| Traversaltechniken | Vorbestellung, Bestellung und Nachbestellung. | Breitensuche und Tiefensuche. |
| Anzahl der Kanten | n-1 (wobei n die Anzahl der Knoten ist) | Nicht definiert |
| Modelltyp | Hierarchisch | Netzwerk |
Definition von Baum
Ein Baum ist eine endliche Sammlung von Datenelementen, die normalerweise als Knoten bezeichnet werden. Wie oben erwähnt, ist ein Baum eine nichtlineare Datenstruktur, die Datenelemente in sortierter Reihenfolge anordnet. Es wird verwendet, um eine hierarchische Struktur zwischen den verschiedenen Datenelementen darzustellen und die Daten in Zweige zu organisieren, die die Informationen in Beziehung setzen. Das Hinzufügen einer neuen Kante in einem Baum führt zu einer Bildung der Schleife oder des Kreises.
Es gibt verschiedene Baumarten, wie z. B. einen binären Baum, einen binären Suchbaum, einen AVL-Baum, einen binären Thread-Baum, einen B-Baum usw. Datenkomprimierung, Dateispeicherung, Manipulation des arithmetischen Ausdrucks und Spielbäume sind einige der Baumanwendungen Datenstruktur.
Eigenschaften des Baumes:
- Oben im Baum befindet sich ein Knoten, der als Wurzel des Baums bezeichnet wird.
- Die verbleibenden Datenelemente sind in getrennte Untermengen unterteilt, die als Unterbaum bezeichnet werden.
- Der Baum ist in der Höhe nach unten erweitert.
- Ein Baum muss verbunden sein, dh es muss ein Pfad von einer Wurzel zu allen anderen Knoten vorhanden sein.
- Es enthält keine Schleifen.
- Ein Baum hat n-1 Kanten.
Es gibt verschiedene Begriffe, die mit Bäumen verbunden sind, wie Endknoten, Kante, Ebene, Grad, Tiefe, Wald usw. Unter diesen Begriffen werden einige nachstehend beschrieben.
- Edge - Eine Linie, die zwei Knoten verbindet.
- Ebene - Ein Baum ist in Ebenen so unterteilt, dass sich der Wurzelknoten auf Ebene 0 befindet. Dann befinden sich die unmittelbaren untergeordneten Elemente auf Ebene 1, und die unmittelbaren untergeordneten Elemente befinden sich auf Ebene 2 usw. bis zum Terminal- oder Blattknoten.
- Grad - Dies ist die Anzahl der Unterbäume eines Knotens in einem bestimmten Baum.
- Tiefe - Dies ist die maximale Höhe eines Knotens in einem bestimmten Baum und wird auch als Höhe bezeichnet .
- Terminalknoten - Der Knoten auf der höchsten Ebene ist ein Terminalknoten, während andere Knoten außer Terminal und Wurzelknoten als Nichtterminalknoten bekannt sind.
Definition von Graph
Ein Graph ist auch eine mathematische nichtlineare Datenstruktur, die verschiedene Arten physikalischer Strukturen darstellen kann. Es besteht aus einer Gruppe von Scheitelpunkten (oder Knoten) und einem Satz von Kanten, die die beiden Scheitelpunkte verbinden. Scheitelpunkte im Diagramm werden als Punkt oder Kreise dargestellt, und Kanten werden als Bögen oder Liniensegmente dargestellt. Eine Kante wird durch E (v, w) dargestellt, wobei v und w die Knotenpunkte sind. Beim Entfernen einer Kante aus einem Kreis oder einem verbundenen Diagramm wird ein Untergraph erstellt, der eine Baumstruktur darstellt.
Die Graphen werden in verschiedene Kategorien eingeteilt, wie z. B. gerichtet, nicht gerichtet, verbunden, nicht verbunden, einfach und mehrere Graphen. Computernetzwerke, Transportsysteme, Diagramme sozialer Netzwerke, Stromkreise und Projektplanung sind einige der Anwendungen der Graphdatenstruktur. Es wird auch in Managementtechniken eingesetzt, die als PERT (Programmbeurteilungs- und Review-Technik) und CPM (Critical Path-Methode) bezeichnet werden, in denen die Diagrammstruktur analysiert wird.
Eigenschaften eines Diagramms:
- Ein Scheitelpunkt in einem Diagramm kann über Kanten mit einer beliebigen Anzahl anderer Scheitelpunkte verbunden werden.
- Eine Kante kann bidirektional oder gerichtet sein.
- Eine Kante kann gewichtet werden.
In Graphen verwenden wir auch verschiedene Ausdrücke wie benachbarte Scheitelpunkte, Pfad, Zyklus, Grad, zusammenhängender Graph, vollständiger Graph, gewichteter Graph usw. Wir wollen einige dieser Begriffe verstehen.
- Benachbarte Scheitelpunkte - Ein Scheitelpunkt a liegt neben dem Scheitelpunkt b, wenn eine Kante (a, b) oder (b, a) vorhanden ist.
- Pfad - Ein Pfad von einem zufälligen Knoten w ist eine benachbarte Folge von Knoten.
- Zyklus - Dies ist ein Pfad, bei dem der erste und der letzte Scheitelpunkt gleich sind.
- Grad - Es ist eine Anzahl von Kanten, die auf einen Scheitelpunkt einfallen.
- Verbundener Graph - Wenn ein Pfad von einem zufälligen Vertex zu einem anderen Vertex vorhanden ist, wird dieser Graph als verbundener Graph bezeichnet.
Hauptunterschiede zwischen Baum und Diagramm
- In einer Baumstruktur gibt es nur einen Pfad zwischen zwei Scheitelpunkten, während ein Diagramm unidirektionale und bidirektionale Pfade zwischen den Knoten haben kann.
- In der Baumstruktur gibt es genau einen Stammknoten, und jedes untergeordnete Element kann nur einen übergeordneten Knoten haben. Im Gegensatz dazu gibt es in einem Diagramm kein Konzept des Wurzelknotens.
- Ein Baum kann keine Schleifen und Selbstschleifen haben, während der Graph Schleifen und Selbstschleifen haben kann.
- Diagramme sind komplizierter, da sie Schleifen und Selbstschleifen haben können. Im Gegensatz dazu sind Bäume im Vergleich zur Grafik einfach.
- Der Baum wird unter Verwendung von Vorbestellungs-, In-Reihenfolge- und Nachbestelltechniken durchlaufen. Auf der anderen Seite verwenden wir für die Diagrammdurchquerung BFS (Breadth First Search) und DFS (Depth First Search).
- Ein Baum kann n-1 Kanten haben. Im Gegensatz dazu gibt es in der Grafik keine vordefinierte Anzahl von Kanten. Dies hängt von der Grafik ab.
- Ein Baum hat eine hierarchische Struktur, wohingegen der Graph ein Netzwerkmodell hat.
Fazit
Graph und Baum sind die nichtlineare Datenstruktur, mit der verschiedene komplexe Probleme gelöst werden. Ein Graph ist eine Gruppe von Knoten und Kanten, bei der eine Kante ein Paar von Knoten verbindet, während ein Baum als minimal verbundener Graph betrachtet wird, der verbunden und frei von Schleifen sein muss.
