In deze tutorial leert u over de datastructuur in de boom. Ook leert u over verschillende soorten bomen en de terminologieën die in de boom worden gebruikt.
Een boom is een niet-lineaire hiërarchische gegevensstructuur die bestaat uit knooppunten die zijn verbonden door randen.
Een boom
Waarom Tree Data Structure?
Andere datastructuren zoals arrays, gekoppelde lijst, stapel en wachtrij zijn lineaire datastructuren die gegevens opeenvolgend opslaan. Om een bewerking in een lineaire gegevensstructuur uit te voeren, neemt de tijdcomplexiteit toe met de toename van de gegevensomvang. Maar het is niet acceptabel in de computerwereld van vandaag.
Verschillende boomgegevensstructuren zorgen voor een snellere en gemakkelijkere toegang tot de gegevens, aangezien het een niet-lineaire gegevensstructuur is.
Tree Terminologieën
Knooppunt
Een knooppunt is een entiteit die een sleutel of waarde bevat en verwijst naar de onderliggende knooppunten.
De laatste knooppunten van elk pad worden bladknooppunten of externe knooppunten genoemd die geen link / pointer naar onderliggende knooppunten bevatten.
Het knooppunt met ten minste een kindknooppunt wordt een intern knooppunt genoemd .
Rand
Het is de verbinding tussen twee willekeurige knooppunten.
Knopen en randen van een boom
Wortel
Het is het bovenste knooppunt van een boom.
Hoogte van een knooppunt
De hoogte van een knoop is het aantal randen van de knoop tot het diepste blad (dwz het langste pad van de knoop naar een bladknoop).
Diepte van een knooppunt
De diepte van een knooppunt is het aantal randen van de wortel tot het knooppunt.
Hoogte van een boom
De hoogte van een boom is de hoogte van het wortelknooppunt of de diepte van het diepste knooppunt.
Hoogte en diepte van elk knooppunt in een boom
Mate van een knooppunt
De graad van een knooppunt is het totale aantal vertakkingen van dat knooppunt.
Woud
Een verzameling onsamenhangende bomen wordt een bos genoemd.
Bos creëren vanuit een boom
U kunt een bos creëren door de wortel van een boom te kappen.
Soorten boom
- Binaire boom
- Binaire zoekboom
- AVL-boom
- B-Tree
Doorkruisen van bomen
Om een bewerking op een boom uit te voeren, moet u naar het specifieke knooppunt gaan. Het tree traversal-algoritme helpt bij het bezoeken van een vereist knooppunt in de boom.
Ga voor meer informatie naar Tree Traversal.
Boomtoepassingen
- Binaire zoekbomen (BST's) worden gebruikt om snel te controleren of een element in een set aanwezig is of niet.
- Heap is een soort boom die wordt gebruikt voor het sorteren van heap.
- Een aangepaste versie van een boomstructuur genaamd Tries wordt in moderne routers gebruikt om routeringsinformatie op te slaan.
- De meeste populaire databases gebruiken B-Trees en T-Trees, varianten van de boomstructuur die we hierboven hebben geleerd om hun gegevens op te slaan
- Compilers gebruiken een syntaxisboom om de syntaxis van elk programma dat u schrijft te valideren.
