Junior
Wat is een binaire boom?
sobes.tech AI
Antwoord van AI
Een binaire boom is een datastructuur in de vorm van een boom waarin elke knoop maximaal twee nakomelingen heeft: links en rechts.
Belangrijkste eigenschappen:
- Wortel (Root): De bovenste knoop van de boom.
- Knoop (Node): Element van de boom dat gegevens bevat en links naar zijn nakomelingen.
- Kind (Child): Knoop die direct onder een andere knoop (ouder) ligt.
- Ouder (Parent): Knoop die direct onder zich een of meer nakomelingen heeft.
- Blad (Leaf): Knoop zonder nakomelingen.
- Tak (Branch): Pad van de wortel naar een blad.
- Subboom (Subtree): Boom die bestaat uit een knoop en al zijn nakomelingen.
Verschillende soorten binaire bomen:
- Volledige binaire boom (Full Binary Tree): Elke knoop heeft of 0 of 2 nakomelingen.
- Perfecte binaire boom (Perfect Binary Tree): Alle niveaus, behalve de laatste, zijn volledig gevuld, en op het laatste niveau zijn alle knopen zo ver mogelijk links geplaatst.
- Gebalanceerde binaire boom (Balanced Binary Tree): De hoogte van de linker- en rechteronderbomen van elke knoop verschilt niet meer dan 1. Voorbeeld: AVL-boom, rode-zwart boom.
- Degeneratieve binaire boom (Degenerate Binary Tree): Elke knoop heeft maximaal één nakomeling. In wezen is dit een gekoppelde lijst.
Gebruikt in verschillende algoritmen en datastructuren, zoals binaire zoekbomen, heaps, syntactische bomen.