Innenknoten

Innenknoten (internal nodes) bezeichnet in der Graphentheorie und Informatik einen Knoten, der kein Blatt ist. In einem gerooteten Baum hat ein Innenknoten mindestens ein Kind; der Wurzelknoten zählt als Innenknoten, wenn er Kinder besitzt. Falls der Baum nur aus einem Knoten besteht, gilt dieser Knoten als Wurzel und Blatt zugleich und ist kein Innenknoten.

Eigenschaften: In einem Baum mit n Knoten und l Blättern gilt i = n − l, wobei i die Anzahl der Innenknoten ist. Bei vollständigen Binärbäumen gilt zusätzlich die Beziehung l = i + 1. Innenknoten dienen in der Praxis als Verzweigungspunkte oder Sammelstellen für Verweise auf Nachfolgeknoten; Blätter liefern oft Endergebnisse oder Verweise auf Daten.

Rolle und Beispiele: In einem binären Suchbaum oder Entscheidungsbaum sind Innenknoten Knoten, an denen Verzweigungen erfolgen (links/rechts bzw. verschiedene Entscheidungswege). Blätter enthalten typischerweise die endgültigen Werte oder Referenzen. In Dateisystemen, Netzwerkstrukturen und vielen Algorithmen spielen Innenknoten eine zentrale Rolle, da sie Struktur und Hierarchie organisieren.

Varianten: In gerichteten Bäumen oder allgemeineren Baumnetzen kann der Out-Degree (Anzahl der Nachfolger) von Innenknoten variieren. In speziellen Baumarten wie mehrstufigen Bäumen oder B-Bäumen gelten unterschiedliche Verzweigungsregeln, wodurch sich typische Innenknotenmengen und deren Eigenschaften unterscheiden.

Anwendungen: Innenknoten sind grundlegende Bausteine von Traversierungs-, Such- und Entscheidungsalgorithmen. Sie helfen bei der Berechnung von Tiefen, Pfaden und Kosten sowie bei der Strukturierung von Daten, einschließlich Suchbäumen, Entscheidungsbäumen und Dateisystemen. Siehe auch: Blatt, Knoten, Baum, Wurzel.