In diesem Tutorial lernen Sie die Struktur von Baumdaten kennen. Außerdem lernen Sie verschiedene Baumarten und die im Baum verwendeten Terminologien kennen.
Ein Baum ist eine nichtlineare hierarchische Datenstruktur, die aus Knoten besteht, die durch Kanten verbunden sind.
Ein Baum
Warum Baumdatenstruktur?
Andere Datenstrukturen wie Arrays, verknüpfte Listen, Stapel und Warteschlangen sind lineare Datenstrukturen, in denen Daten nacheinander gespeichert werden. Um eine Operation in einer linearen Datenstruktur auszuführen, nimmt die zeitliche Komplexität mit zunehmender Datengröße zu. In der heutigen Computerwelt ist dies jedoch nicht akzeptabel.
Verschiedene Baumdatenstrukturen ermöglichen einen schnelleren und einfacheren Zugriff auf die Daten, da es sich um eine nichtlineare Datenstruktur handelt.
Baumterminologien
Knoten
Ein Knoten ist eine Entität, die einen Schlüssel oder Wert enthält und auf seine untergeordneten Knoten verweist.
Die letzten Knoten jedes Pfads werden Blattknoten oder externe Knoten genannt , die keinen Link / Zeiger auf untergeordnete Knoten enthalten.
Der Knoten mit mindestens einem untergeordneten Knoten wird als interner Knoten bezeichnet .
Kante
Es ist die Verbindung zwischen zwei beliebigen Knoten.
Knoten und Kanten eines Baumes
Wurzel
Es ist der oberste Knoten eines Baumes.
Höhe eines Knotens
Die Höhe eines Knotens ist die Anzahl der Kanten vom Knoten zum tiefsten Blatt (dh der längste Pfad vom Knoten zu einem Blattknoten).
Tiefe eines Knotens
Die Tiefe eines Knotens ist die Anzahl der Kanten von der Wurzel zum Knoten.
Höhe eines Baumes
Die Höhe eines Baums ist die Höhe des Wurzelknotens oder die Tiefe des tiefsten Knotens.
Höhe und Tiefe jedes Knotens in einem Baum
Grad eines Knotens
Der Grad eines Knotens ist die Gesamtzahl der Zweige dieses Knotens.
Wald
Eine Ansammlung nicht zusammenhängender Bäume wird Wald genannt.
Wald aus einem Baum erstellen
Sie können einen Wald erstellen, indem Sie die Wurzel eines Baumes abschneiden.
Baumarten
- Binärer Baum
- Binärer Suchbaum
- AVL-Baum
- B-Baum
Baumdurchquerung
Um eine Operation an einem Baum auszuführen, müssen Sie den spezifischen Knoten erreichen. Der Tree Traversal-Algorithmus hilft beim Aufrufen eines erforderlichen Knotens im Baum.
Um mehr zu erfahren, besuchen Sie bitte Tree Traversal.
Baumanwendungen
- Mit binären Suchbäumen (BSTs) kann schnell überprüft werden, ob ein Element in einer Menge vorhanden ist oder nicht.
- Heap ist eine Art Baum, der für die Heap-Sortierung verwendet wird.
- Eine modifizierte Version eines Baums namens Tries wird in modernen Routern zum Speichern von Routing-Informationen verwendet.
- Die meisten gängigen Datenbanken verwenden B-Trees und T-Trees, Varianten der oben erlernten Baumstruktur, um ihre Daten zu speichern
- Compiler verwenden einen Syntaxbaum, um die Syntax jedes von Ihnen geschriebenen Programms zu überprüfen.
