Boomstructuur

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 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.

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.

Hiërarchische indeling van een verzameling

Een hiërarchische indeling van een verzameling is een boomstructuur met de hele verzameling als wortel, waarbij de kinderen van een verzameling steeds een partitie van die verzameling vormen.

Een voorbeeld is de hiërarchische indeling van een verzameling tijdstippen in jaren, maanden, dagen, uren, minuten en seconden. Ook van deze tijdvaksoorten zelf kan gezegd worden dat ze een hiërarchie vormen.

Een ander voorbeeld is een hiërarchie van soorten elementen (taxonomie).

Nog een voorbeeld zou de verzameling onderwerpen in een encyclopedie kunnen zijn. In de illustratie is de gehele verzameling de wortel, aangeduid als 'encyclopedia', die de ouder is 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. Als raakvlakken tussen twee gebieden bij beide zouden worden ingedeeld is er echter geen strikte hiërarchie meer.

Tegenvoorbeeld

Als het tweede kwartaal van 2021 eerst wordt ingedeeld in maanden, en de maanden vervolgens in weken, dan resulteert dat in 10 volledige weken, twee delen van weken waarvan de rest in een ander kwartaal ligt, en vier weekdelen die twee hele weken vormen. Dit is in zoverre geen hiërarchische indeling van het kwartaal in maanden en weken dat, anders dan bij rechtstreeks indelen van het kwartaal in weken, deze twee hele weken niet als knoop voorkomen. Het eerste kwartaal van 2021 kan wel hiërarchisch worden ingedeeld in maanden en weken. Dit neemt niet weg dat in het algemeen een verzameling tijdstippen niet hiërarchisch kan worden ingedeeld in maanden en weken. Maanden en weken vormen dus geen hiërarchie.

Stamboom

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

Vrouwelijke of mannelijke relatienamen

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.

Oneindige boomstructuur

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 ook

• Dendrogram
• XML - een manier om boomstructuren weer te geven.
• Beslissingsboom - een specifiek soort boomstructuur

Mediabestanden

Zie de categorie Tree structures van Wikimedia Commons voor mediabestanden over dit onderwerp.