Elternknoten

Elternknoten, im Deutschen oft auch als parent node bezeichnet, bezeichnet in Baum- oder Graphdatenstrukturen einen Knoten, dem mindestens ein Nachfolgerknoten (ein Kindknoten) zugeordnet ist. In vielen Implementierungen enthält ein Elternknoten Verweise auf seine Kindknoten und gegebenenfalls auf seinen eigenen Elternknoten, wodurch eine bidirektionale Navigierbarkeit ermöglicht wird. Der oberste Knoten eines Baums, die Wurzel, besitzt keinen Elternknoten.

In gerichteten Bäumen verläuft die Kante typischerweise vom Elternknoten zu seinen Kindknoten. Demnach hat jeder Knoten außer der Wurzel genau einen Elternknoten. Die Kindknoten eines Elternknotens werden als dessen Nachbarn in der darunterliegenden Ebene betrachtet. In ungerichteten Bäumen kann man die Richtung ignorieren, doch auch dort lässt sich die Beziehung als Eltern-Kind-Relation interpretieren.

Die Struktur unterscheidet sich je nach Baumtyp. In binären Bäumen kann ein Elternknoten höchstens zwei Kindknoten haben (links und rechts). In allgemeinen Bäumen kann ein Elternknoten hingegen mehrere Kinder besitzen; die Reihenfolge der Kinder kann relevant oder irrelevant sein, je nach konkreter Datenstruktur.

Anwendungen umfassen unter anderem binäre Suchbäume, Heaps, Trie-Strukturen und Parsebäume. Elternknoten ermöglichen effiziente Traversierungen (Vorzugs-, In- und Nachorder), sowie Operationen wie Einfügen, Löschen und Neuordnung bzw. Rebalancierung. In Dateisystemen entsprechen Verzeichnisse Elternknoten zu den enthaltenen Dateien und Unterverzeichnissen. Blätter oder Blattknoten besitzen dagegen keine Kindknoten.