Wortelknooppunt

Wortelknooppunt is het knooppunt dat als oorsprong is aangewezen in een gewortelde boom of een gewortelde grafiek. In het Nederlands wordt hiermee doorgaans het knooppunt bedoeld waar de vertakkingen van een hiërarchie beginnen en van waaruit alle andere knopen via unieke paden bereikbaar zijn.

In een gewortelde boom bestaat er precies één wortelknooppunt; alle andere knopen hebben een unieke ouder en een pad naar de wortel. De wortel heeft geen ouder en bevindt zich op diepte nul. Elke andere knoop heeft een ouder en kan een subboom vormen.

In informatica en algoritmen dienen wortelknooppunten als uitgangspunt voor traversals zoals breadth-first of depth-first search. Ze bepalen ook de hiërarchie van gegevens, bijvoorbeeld bij bestanden, organisatiemodellen of parse-boomstructuren. In heap-structuren bepaalt het wortelknooppunt vaak de grootste of kleinste waarde, afhankelijk van het type heap.

In niet-gewortelde grafieken of in grafieken die niet als boom zijn opgebouwd, kan een in-degree-zero set bestaan uit meerdere wortelknooppunten. Het concept is dan afhankelijk van de gekozen richting of semantische betekenis van de verbindingen. Het kiezen van een wortelknooppunt kan noodzakelijk zijn voor efficiëntie, uitvoerbaarheid of semantische betekenis van de gegevens.

Termen die verwant zijn aan wortelknooppunt zijn wortel, wortellijn en de hiërarchie van een boom. In gebruik kan de exacte betekenis per vakgebied verschillen; in computerwetenschappen verwijst wortelknooppunt meestal naar de oorsprong van de structuur.