Binært søketre (BST) med eksempel

Attributter til binært søketre

En BST er laget av flere noder og består av følgende attributter:

• Noder i treet er representert i et foreldre-barn-forhold
• Hver overordnet node kan ha null undernoder eller maksimalt to undernoder eller undertrær på venstre og høyre side.
• Hvert undertre, også kjent som et binært søketre, har undergrener til høyre og venstre for seg selv.
• Alle nodene er knyttet til nøkkelverdi-par.
• Nøklene til nodene som er tilstede på det venstre undertreet er mindre enn nøklene til deres overordnede node
• På samme måte har nøklene til venstre undertre nodene lavere verdier enn deres overordnede nodes nøkler.

1. Det er hovednoden eller overordnet nivå 11. Under den er det venstre og høyre noder/grener med egne nøkkelverdier
2. Det høyre undertreet har nøkkelverdier som er større enn overordnet node
3. Det venstre undertreet har verdier enn den overordnede noden

Hvorfor trenger vi et binært søketre?

• De to hovedfaktorene som gjør binært søketre til en optimal løsning på alle reelle problemer er hastighet og nøyaktighet.
• På grunn av det faktum at det binære søket er i et grenlignende format med foreldre-barn-relasjoner, vet algoritmen på hvilken plassering av treet elementene skal søkes. Dette reduserer antallet nøkkelverdi-sammenligninger programmet må gjøre for å finne det ønskede elementet.
• I tillegg, i tilfelle elementet som skal søkes større eller mindre enn den overordnede noden, vet noden hvilken treside den skal søke etter. Årsaken er at det venstre undertreet alltid er mindre enn hovednoden, og det høyre undertreet har verdier som alltid er lik eller større enn overordnet node.
• BST brukes ofte til å implementere komplekse søk, robust spilllogikk, autofullføringsaktiviteter og grafikk.
• Algoritmen støtter effektivt operasjoner som søk, sett inn og slett.

Typer binære trær

Tre typer binære trær er:

• Komplett binært tre: Alle nivåene i trærne er fulle av siste nivås mulige unntak. På samme måte er alle nodene fulle, og dirigerer helt til venstre.
• Fullt binært tre: Alle nodene har 2 underordnede noder bortsett fra bladet.
• Balansert eller perfekt binært tre: I treet har alle nodene to barn. Dessuten er det samme nivå for hver subnode.

Lær mer om Binært tre i datastruktur hvis du er interessert.

Hvordan fungerer binært søketre?

Treet har alltid en rotnode og ytterligere barnnoder, enten det er til venstre eller høyre. Algoritmen utfører alle operasjonene ved å sammenligne verdier med roten og dens ytterligere barnnoder i venstre eller høyre undertre tilsvarende.

Avhenger av elementet som skal settes inn, søkes eller slettes, etter sammenligningen kan algoritmen enkelt slippe venstre eller høyre undertre til rotnoden.

BST tilbyr primært følgende tre typer operasjoner for din bruk:

• Søk: søker etter elementet fra det binære treet
• Sett inn: legger til et element til det binære treet
• Slett: slett elementet fra et binært tre

Hver operasjon har sin egen struktur og metode for utførelse/analyse, men den mest komplekse av alt er Slett-operasjonen.

Søk Operasjon

Start alltid analysetreet ved rotnoden og flytt deretter videre til enten høyre eller venstre undertre av rotnoden avhengig av at elementet som skal lokaliseres enten er mindre eller større enn roten.

1. Elementet som skal søkes i er 10
2. Sammenlign elementet med rotnoden 12, 10 < 12, derav flytter du til venstre undertre. Du trenger ikke å analysere det høyre undertreet
3. Sammenlign nå 10 med node 7, 10 > 7, så flytt til høyre undertreet
4. Sammenlign deretter 10 med neste node, som er 9, 10 > 9, se i det høyre undertrebarnet
5. 10 samsvarer med verdien i noden, 10 = 10, returner verdien til brukeren.

Pseudokode for søk i BST

search(element, root)
     if !root
    	return -1
     if root.value == element
    	return 1
     if root.value < element
    	search(element, root.right)
      else
    	search(element, root.left)

innfelt Operasjon

Dette er en veldig rett frem operasjon. Først settes rotnoden inn, deretter sammenlignes neste verdi med rotnoden. Hvis verdien er større enn roten, legges den til høyre undertre, og hvis den er mindre enn roten, legges den til venstre undertre.

1. Det er en liste over 6 elementer som må settes inn i en BST i rekkefølge fra venstre til høyre
2. Sett inn 12 som rotnoden og sammenlign neste verdier 7 og 9 for å sette inn tilsvarende i høyre og venstre undertre
3. Sammenlign de resterende verdiene 19, 5 og 10 med rotnoden 12 og plasser dem deretter. 19 > 12 plasser det som høyre barn av 12, 5 < 12 & 5 < 7, derav plasser det som venstre barn av 7. Sammenlign nå 10, 10 er < 12 & 10 er > 7 & 10 er > 9, plass 10 som høyre undertre av 9.

Pseudokode for å sette inn en node i BST

insert (element, root)
    Node x = root
    Node y = NULL
    while x:
    	y = x
    if x.value < element.value
        x = x.right
    else
        x = x.left
    if y.value < element
    	y.right = element
    else
    	y.left = element

Delete Operasjoner

For å slette en node fra en BST, er det noen tilfeller, dvs. sletting av en rot eller sletting av en bladnode. Etter å ha slettet en rot, må vi også tenke på rotnoden.

Si at vi ønsker å slette en bladnode, vi kan bare slette den, men hvis vi vil slette en rot, må vi erstatte rotens verdi med en annen node. La oss ta følgende eksempel:

• Tilfelle 1- Node med null barn: dette er den enkleste situasjonen, du trenger bare å slette noden som ikke har flere barn til høyre eller venstre.
• Tilfelle 2 – Node med ett barn: Når du har slettet noden, kobler du ganske enkelt dens underordnede node til den overordnede noden til den slettede verdien.
• Tilfelle 3 Node med to barn: dette er den vanskeligste situasjonen, og den fungerer på følgende to regler
• 3a – I rekkefølge forgjenger: du må slette noden med to barn og erstatte den med den største verdien på venstre undertreet til den slettede noden
• 3b – I rekkefølge etterfølger: du må slette noden med to barn og erstatte den med den største verdien på høyre undertreet til den slettede noden

1. Dette er det første tilfellet med sletting der du sletter en node som ikke har barn. Som du kan se i diagrammet har 19, 10 og 5 ingen barn. Men vi sletter 19.
2. Slett verdien 19 og fjern koblingen fra noden.
3. Se den nye strukturen til BST uten 19

1. Dette er det andre tilfellet med sletting der du sletter en node som har 1 barn, som du kan se i diagrammet at 9 har ett barn.
2. Slett noden 9 og erstatt den med dens underordnede 10 og legg til en lenke fra 7 til 10
3. Se den nye strukturen til BST uten 9

1. Her vil du slette noden 12 som har to barn
2. Slettingen av noden vil skje basert på forløperregelen i rekkefølge, som betyr at det største elementet på venstre undertre av 12 vil erstatte det.
3. Slett noden 12 og erstatt den med 10 da det er den største verdien på venstre undertre
4. Se den nye strukturen til BST etter sletting av 12

1. 1 Slett en node 12 som har to barn
2. 2 Slettingen av noden vil skje basert på In Order Successor-regelen, som betyr at det største elementet på høyre undertre av 12 vil erstatte det
3. 3 Slett noden 12 og erstatt den med 19 da det er den største verdien på høyre undertre
4. 4 Se den nye strukturen til BST etter sletting 12

Pseudokode for å slette en node

delete (value, root):
    Node x = root
    Node y = NULL
# searching the node
    while x:
    	y = x
    if x.value < value
        x = x.right
    else if x.value > value
        x = x.left
    else if value == x
        break
# if the node is not null, then replace it with successor
    if y.left or y.right:
    	newNode = GetInOrderSuccessor(y)
    	root.value = newNode.value
# After copying the value of successor to the root #we're deleting the successor
    	free(newNode)
    else
    	free(y)

Viktige vilkår

• Sett inn: Setter inn et element i et tre/oppretter et tre.
• Søk: Søker etter et element i et tre.
• Forhåndsbestillingsgjennomgang: Går gjennom et tre på en forhåndsbestillingsmåte.
• Inorder Traversal: Traverserer et tre på en i orden.
• Postordergjennomgang: Traverserer et tre på en etterbestillingsmåte.

Sammendrag

• BST er en avansert nivåalgoritme som utfører ulike operasjoner basert på sammenligning av nodeverdier med rotnoden.
• Ethvert av punktene i et overordnet-underordnet hierarki representerer noden. Minst én overordnet eller rotnode forblir til stede hele tiden.
• Det er et venstre undertre og et høyre undertre. Det venstre undertreet inneholder verdier som er mindre enn rotnoden. Det høyre undertreet inneholder imidlertid en verdi som er større enn rotnoden.
• Hver node kan ha enten null, ett eller to barn.
• Et binært søketre forenkler primære operasjoner som søk, sett inn og slett.
• Slett som den mest komplekse har flere tilfeller, for eksempel en node uten underordnet, node med ett underordnet og node med to underordnede.
• Algoritmen brukes i virkelige løsninger som spill, autofullføringsdata og grafikk.