Inleiding tot bomen in gegevensstructuur
Voordat we de boomtypen in datastructuur begrijpen, zullen we eerst de bomen in datastructuur bestuderen. Tree in het computerveld wordt ook wel de echte boom genoemd, maar het verschil tussen de echte wereld en de computerveldboom is dat deze wordt gevisualiseerd als ondersteboven en root bovenop en vertakking van root naar boombladeren. Onder verschillende real-world toepassingen wordt de boomgegevensstructuur gebruikt omdat deze relaties tussen verschillende knooppunten met de ouder-kindhiërarchie kan aantonen. Daarom wordt het ook een hiërarchische gegevensstructuur genoemd. Het is het populairst voor het vereenvoudigen en versnellen van zoeken en sorteren. Het wordt beschouwd als een van de sterkste en meest geavanceerde gegevensstructuren. Een boom is een weergave van de niet-lineaire gegevensstructuur. Een boomstructuur kan worden weergegeven met verschillende door de gebruiker gedefinieerde of primitieve gegevenstypen. We kunnen arrays, met klassen verbonden lijsten of andere soorten gegevensstructuren gebruiken om de boom te implementeren. Het is een groep knooppunten die met elkaar verbonden zijn. Aan de randen zijn knooppunten bevestigd om de relatie aan te tonen.
Relaties in een boom: In het bovenstaande diagram is P de wortel van de boom en is P ook ouder van Q, R en S. Q is het kind van P. Vandaar dat Q, R en S broers en zussen zijn. Terwijl P grootouder is van A, B, C, D en E.
Wat zijn bomen?
Een boom is een hiërarchische gegevensstructuur die de informatie op een hiërarchische manier opslaat. De Tree-datastructuur is een van de meest efficiënte en volwassen. De knooppunten verbonden door de randen worden weergegeven.
Eigenschappen van Tree: Elke boom heeft een specifieke root node. Elke boomknoop kan worden gekruist door een wortelknoop. Het wordt root genoemd, omdat de boom de enige root was. Elk kind heeft maar één ouder, maar de ouder kan veel kinderen hebben.
Soorten bomen in gegevensstructuur
Hieronder staan de typen bomen in een gegevensstructuur:
1. Algemene boom
Als er geen beperking wordt geplaatst op de hiërarchie van de boom, wordt een boom een algemene boom genoemd. Elk knooppunt kan een oneindig aantal kinderen hebben in General Tree. De boom is de superset van alle andere bomen.
2. Binaire boom
De binaire boom is het soort boom waarin de meeste twee kinderen voor elke ouder kunnen worden gevonden. De kinderen staan bekend als de linker en rechter jongen. Dit is populairder dan de meeste andere bomen. Wanneer bepaalde beperkingen en kenmerken worden toegepast in een binaire boom, worden ook een aantal andere, zoals AVL-boom, BST (binaire zoekboom), RBT-boom, enz. Gebruikt. Wanneer we verder gaan, zullen we al deze stijlen in detail uitleggen.
3. Binaire zoekboom
Binaire zoekboom (BST) is een binaire boomextensie met verschillende optionele beperkingen. De linker onderliggende waarde van een knooppunt moet in BST kleiner zijn dan of gelijk zijn aan de bovenliggende waarde en de rechter onderliggende waarde moet altijd groter zijn dan of gelijk aan de bovenliggende waarde. Deze eigenschap van de binaire zoekboom maakt het ideaal voor zoekbewerkingen omdat we bij elk knooppunt nauwkeurig kunnen bepalen of de waarde zich in de linker of rechter subboom bevindt. Dit is de reden waarom de zoekboom een naam heeft.
4. AVL-structuur
AVL-structuur is een binaire zelfbalancerende zoekboom. Namens de uitvinders Adelson-Velshi en Landis wordt de naam AVL gegeven. Dit was de eerste boom die dynamisch in balans was. Een balanceringsfactor wordt toegewezen voor elk knooppunt in de AVL-structuur, op basis van het feit of de structuur al dan niet gebalanceerd is. De hoogte van de knooppuntkinderen is maximaal 1. AVL vine. In de AVL-structuur is de juiste balansfactor 1, 0 en -1. Als de boom een nieuw knooppunt heeft, wordt deze gedraaid om ervoor te zorgen dat de boom in balans is. Het zal dan worden gedraaid. Algemene bewerkingen zoals weergeven, invoegen en verwijderen nemen O (log n) tijd in de AVL-structuur in beslag. Het wordt meestal toegepast bij het werken met opzoekbewerkingen.
5. Rood-zwarte boom
Een ander soort auto-balancerende boom is rood-zwart. De rood-zwarte naam wordt gegeven omdat de rood-zwarte boom rood of zwart op elke knoop heeft geschilderd volgens de eigenschappen van de rood-zwarte boom. Het handhaaft het evenwicht van het bos. Hoewel deze boom geen volledig gebalanceerde boom is, kost de zoekbewerking alleen O (log n) tijd. Wanneer de nieuwe knooppunten worden toegevoegd in de rood-zwarte boom, worden de knopen opnieuw geroteerd om de eigenschappen van de rood-zwarte boom te behouden.
6. N-ary boom
Het maximale aantal kinderen in dit type boom dat een knoop kan hebben, is N. Een binaire boom is een tweejarige boom, zoals maximaal 2 kinderen in elke binaire boomknoop. Een complete N-ary boom is een boom waar kinderen van een knoop 0 of N zijn.
Voordelen van Tree
Nu zullen we de voordelen van Tree begrijpen:
- Boom weerspiegelt in de structurele gegevensverbindingen.
- De boom wordt gebruikt voor hiërarchie.
- Het biedt een efficiënte zoek- en invoegprocedure.
- De bomen zijn flexibel. Hierdoor kunnen subtrees met minimale inspanning worden verplaatst.
Conclusie - Soorten bomen in de gegevensstructuur
Dus hier in dit artikel hebben we gezien wat boomstructuur is, wat verschillende soorten bomen zijn in datastructuur en de voordelen ervan. Ik hoop dat je een idee hebt gekregen van enkele veelvoorkomende bomen in de structuur van de gegevens.
Aanbevolen artikelen
Dit is een gids voor boomtypen in datastructuur. Hier bespreken we wat bomen zijn, 6 soorten bomen in de datastructuur, met voordelen. U kunt ook onze andere gerelateerde artikelen doornemen voor meer informatie -
- AWS-gegevenspijplijn
- Oracle Data Warehousing
- Multidimensionale database
- Data Structure: sollicitatievragen voor Java