Hva er et binært søketre?
Det binære søketreet er en avansert algoritme som brukes til å analysere noden, dens venstre og høyre gren, som er modellert i en trestruktur og returnerer verdien. BST er utformet på arkitekturen til en grunnleggende binær søkealgoritme; dermed muliggjør det raskere oppslag, innsetting og fjerning av noder. Dette gjør programmet veldig raskt og nøyaktig.
I denne opplæringen for datastruktur lærer du:
- Hva er et binært søketre?
- Attributter til binært søketre
- Hvorfor trenger vi et binært søketre?
- Typer binære trær
- Hvordan fungerer binært søketre?
- Viktige vilkår
Attributter til binært søketre
En BST er laget av flere noder og består av følgende attributter:
- Noder på treet er representert i et foreldre-barn forhold
- Hver foreldrenode 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 på høyre og venstre side av seg selv.
- Alle nodene er knyttet til nøkkelverdipar.
- Nøklene til nodene som er tilstede på venstre undertre er mindre enn nøklene til foreldrenoden
- På samme måte har nøklene til venstre for de subtree noder mindre verdier enn nøklene til foreldrenoden.
- Det er hovednoden eller foreldrenivået 11. Under det er det venstre og høyre noder / grener med egne nøkkelverdier
- Det høyre undertreet har nøkkelverdier som er større enn foreldrenoden
- Det venstre undertreet har verdier enn foreldrenoden
Hvorfor trenger vi et binært søketre?
- De to viktigste faktorene som gjør binært søketre til en optimal løsning på eventuelle virkelige 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-forhold, vet algoritmen på hvilken plassering av treet elementene må søkes. Dette reduserer antall nøkkelverdisammenligninger programmet må gjøre for å finne ønsket element.
- I tillegg, hvis elementet som skal søkes større eller mindre enn foreldrenoden, vet noden hvilken treside du skal søke etter. Årsaken er at det venstre under-treet alltid er mindre enn foreldrenoden, og det høyre under-treet har verdier som alltid er lik eller større enn foreldrenoden.
- BST brukes ofte til å implementere komplekse søk, robust spilllogikk, automatisk fullføring av aktiviteter 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ærtre: Alle nivåene i trærne er fulle av mulige unntak fra siste nivå. Tilsvarende er alle nodene fulle, og styrer helt til venstre.
- Fullt binært tre: Alle nodene har to barn noder unntatt bladet.
- Balansert eller perfekt binært tre: I treet har alle nodene to barn. Dessuten er det samme nivå i hver subnode.
Hvordan fungerer binært søketre?
Treet har alltid en rotnode og ytterligere underordnede noder, enten det er til venstre eller høyre. Algoritmen utfører alle operasjonene ved å sammenligne verdier med roten og dens ytterligere underordnede noder i venstre eller høyre undertre tilsvarende.
Avhenger av elementet som skal settes inn, søk eller slettes, etter sammenligningen, kan algoritmen lett slippe venstre eller høyre undertre av rotnoden.
BST tilbyr primært følgende tre typer operasjoner for din bruk:
- Søk: søker i elementet fra det binære treet
- Sett inn: legger til et element i 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 Delete-operasjonen.
Søkeoperasjon
Start alltid å analysere treet ved rotnoden, og flytt deretter videre til enten høyre eller venstre undertre av rotnoden, avhengig av at elementet som skal lokaliseres er enten mindre eller større enn roten.
- Elementet som skal søkes er 10
- Sammenlign elementet med rotnoden 12, 10 <12, og flytt deg derfor til venstre undertrær. Ingen grunn til å analysere det rette undertreet
- Sammenlign nå 10 med node 7, 10> 7, så flytt til høyre undertrær
- Sammenlign deretter 10 med neste node, som er 9, 10> 9, se i det rette undertrærbarnet
- 10 samsvarer med verdien i noden, 10 = 10, returner verdien til brukeren.
Sett inn 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.
- Det er en liste over 6 elementer som må settes inn i en BST i rekkefølge fra venstre til høyre
- Sett inn 12 som rotnode og sammenlign neste verdier 7 og 9 for å sette inn tilsvarende i høyre og venstre undertrær
- Sammenlign de gjenværende verdiene 19, 5 og 10 med rotnoden 12 og plasser dem deretter. 19> 12 plasser det som det høyre barnet til 12, 5 <12 & 5 <7, og plasser det derfor som venstre barn på 7.
- Sammenlign nå 10, 10 er <12 & 10 er> 7 & 10 er> 9, plasser 10 som høyre undertre på 9.
Slett operasjoner
Slett er den mest avanserte og komplekse blant alle andre operasjoner. Det er flere saker behandlet for sletting i BST.
- Sak 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 bare den underordnede noden til foreldrenoden til den slettede verdien.
- Sak 3 Knutepunkt 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 undertre av den slettede noden
- 3b - I ordrefølger: du må slette noden med to barn og erstatte den med den største verdien på høyre undertre av den slettede noden
- Dette er det første tilfellet av sletting der du sletter en node som ikke har barn. Som du kan se i diagrammet at 19, 10 og 5 ikke har barn. Men vi vil slette 19.
- Slett verdien 19 og fjern lenken fra noden.
- Se den nye strukturen til BST uten 19
- Dette er det andre tilfellet av sletting der du sletter en node som har 1 barn, som du kan se i diagrammet at 9 har ett barn.
- Slett noden 9 og erstatt den med barnet 10 og legg til en lenke fra 7 til 10
- Se den nye strukturen til BST uten 9
- Her vil du slette noden 12 som har to barn
- Sletting av noden vil skje basert på forgjengersregelen i rekkefølge, noe som betyr at det største elementet på venstre undertre på 12 vil erstatte det.
- Slett noden 12 og erstatt den med 10, da den er den største verdien på venstre undertrær
- Se den nye strukturen til BST etter å ha slettet 12
- 1 Slett en node 12 som har to barn
- 2 Slettingen av noden vil skje basert på In Order Successor-regelen, som betyr at det største elementet på høyre undertre på 12 vil erstatte det
- 3 Slett noden 12 og erstatt den med 19, da den er den største verdien på høyre undertrær
- 4 Vis den nye strukturen til BST etter å ha slettet 12
Viktige vilkår
- Sett inn - Setter inn et element i et tre / opprett et tre.
- Søk - Søker etter et element i et tre.
- Preorder Traversal - Traverserer et tre på forhåndsbestilt måte.
- Inorder Traversal - Traverserer et tre på en ordnet måte.
- Postorder Traversal - Traverserer et tre på en postordre måte.
Sammendrag
- BST er en avansert algoritme som utfører forskjellige operasjoner basert på sammenligning av nodeverdier med rotnoden.
- Ethvert av punktene i et foreldre-barn-hierarki representerer noden. Minst en foreldre eller rotnode forblir til stede hele tiden.
- Det er et venstre undertreet og det høyre undertreet. Det venstre undertreet inneholder verdier som er mindre enn rotnoden. Det rette 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 muliggjør primære operasjoner som søk, sett inn og slett.
- Slette som det mest komplekse har flere tilfeller, for eksempel en node uten barn, node med ett barn og node med to barn.
- Algoritmen brukes i virkelige løsninger som spill, autofullførte data og grafikk.