Een Binaire Zoek Boom (BST) is een boom waar alle knooppunten volg de hieronder genoemde eigenschappen
-
De waarde van de sleutel van de linker deelboom kleiner zijn dan de waarde van zijn ouder (root) knoop van de toets.
-
de waarde van de sleutel van de rechter subboom is groter dan of gelijk aan de waarde van de sleutel van de ouder (root) node.,
dus verdeelt BST alle subbomen in twee segmenten; de linker subboom en de rechter subboom en kan worden gedefinieerd als-
left_subtree (keys) < node (key) ≤ right_subtree (keys)
representatie
BST is een verzameling knooppunten die zo zijn gerangschikt dat ze BST −eigenschappen behouden. Elk knooppunt heeft een sleutel en een bijbehorende waarde. Tijdens het zoeken wordt de gewenste sleutel vergeleken met de sleutels in BST en indien gevonden, wordt de bijbehorende waarde opgehaald.,
Hieronder volgt een picturale representatie van BST –
we zien dat de sleutel van de root node (27) Alle minder gewaardeerde sleutels in de linker subboom heeft en de hoger gewaardeerde sleutels in de rechter subboom.
basisbewerkingen
Hieronder volgen de basisbewerkingen van een boom –
-
zoeken − doorzoekt een element in een boom.
-
Insert-voegt een element in een boomstructuur in.
-
pre-order Traversal-doorkruist een boom op een pre-order manier.
-
In-order Traversal-doorkruist een boom op een in-order manier.,
-
post-order Traversal-doorkruist een boom op een post-order manier.
knooppunt
Definieer een knooppunt met enkele gegevens, verwijzingen naar de linker en rechter onderliggende knooppunten.
struct node { int data; struct node *leftChild; struct node *rightChild;};
zoekopdracht
wanneer een element moet worden doorzocht, start het zoeken vanaf het root-knooppunt. Als de gegevens dan kleiner zijn dan de sleutelwaarde, zoekt u naar het element in de linker subboom. Zoek anders naar het element in de rechter subboom. Volg hetzelfde algoritme voor elk knooppunt.,
algoritme
Insert operatie
wanneer een element moet worden ingevoegd, zoek eerst de juiste locatie. Begin met zoeken vanuit het root-knooppunt, en als de gegevens kleiner zijn dan de sleutelwaarde, zoek dan naar de lege locatie in de linker subboom en voeg de gegevens in. Zoek anders naar de lege locatie in de rechter subboom en voeg de gegevens in.