Hoofdmenu openen

Boomstructuur

niet-gerichte samenhangende cycelvrije graaf
(Doorverwezen vanaf Hiërarchische indeling)
Binary-tree-structure.png

De mogelijke structuur van een encyclopedie
wordt hier als een boom weergegeven.
In dit geval is dat een binaire boom.
  • Encyclopedia
    • Culture
      • Craft
      • Art
    • Science

Dendrogram op zijn kant met dezelfde informatie.

Een boomstructuur of hiërarchische structuur is een samenhangende graaf zonder cykels (boom) met een wortel (root), een rooted tree. De elementen van een boomstructuur worden (net als bij andere grafen) knopen genoemd en zijn logisch verbonden door middel van takken. De boomstructuur definiert een hiërarchie van knopen, met de wortel bovenaan in de hiërarchie. Of deze knoop in een diagram daadwerkelijk bovenaan staat varieert, hij kan ook onderaan staan (zoals de stam van een boom) of links.

De relaties tussen de knopen wordt aangeduid met de namen van familierelaties:

  • Een in de hiërarchie direct boven een knoop gelegen knoop (dichter bij de root), heet een ouder.
  • Een knoop met een ouder heet een kind van die ouder.
  • Knopen die dezelfde ouder hebben zijn broers of zussen.
  • Een knoop zonder kinderen wordt blad genoemd.

Een toepassing is bijvoorbeeld een hiërarchische indeling van een verzameling, of, daarmee corresponderend, een hiërarchie van soorten elementen (taxonomie).

Een voorbeeld van een boomstructuur is een stamboom, mits steeds maar één ouder wordt weergegeven.

In de illustratie is 'encyclopedia' (encyclopedie) de wortel, maar ook de ouder van twee kinderen, 'science' (wetenschap) en 'culture' (cultuur). Deze twee kinderen zijn broers/zussen van elkaar. 'Science', 'art' (kunsten) en 'craft' (ambachten) zijn de bladeren.

Of een wetenschap vrouwelijke of mannelijke relatienamen gebruikt, verschilt per discipline. De informatica gebruikte aanvankelijk mannelijke relatienamen. Het verhaal gaat dat in protest hiertegen vrouwelijke studenten van Noam Chomsky vrouwelijke relatienamen gingen gebruiken voor diens generatieve taalkunde. Hierom worden in de taalkunde vrouwelijke relatienamen gebruikt.

Een variant van een boomstructuur als boven is er een die naar boven oneindig doorloopt, bijvoorbeeld bij een indeling van getallen in intervallen, waarbij die intervallen naarmate die hoger in de hiërarchie zitten, steeds groter worden.

Zie ookBewerken