Binært søketre (BST) med eksempel

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 grener, som er modellert i en trestruktur, og returnere verdien. BST er utviklet på arkitekturen til en grunnleggende binær søkealgoritme; dermed muliggjør den raskere oppslag, innsettinger og fjerning av noder. Dette gjør programmet veldig raskt og nøyaktig.

Attributter til binært søketre

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

• Nodene 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 finnes i det venstre undertreet er mindre enn nøklene til den overordnede noden.
• På samme måte er nøklene til nodene som finnes på det høyre undertreet større enn nøklene til den overordnede noden.

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

Hvorfor trenger vi et binært søketre?

• De to viktigste faktorene som gjør et binært søketre til en optimal løsning på ethvert virkelig problem, 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, dersom elementet som skal søkes er større eller mindre enn den overordnede noden, vet noden hvilken treside den skal søke på. Årsaken er at det venstre undertreet alltid er mindre enn den overordnede noden, og det høyre undertreet har verdier som alltid er lik eller større enn den overordnede noden.
• 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ærtre: Alle nivåene i treet er fulle, med et mulig unntak på det siste nivået. På samme måte er alle nodene fulle, og peker helt mot venstre.
• Fullstendig binærtre: Alle nodene har to barnnoder bortsett fra bladet.
• Balansert eller perfekt binært tre: I treet har alle nodene to barn. Dessuten er det samme nivå for hver undernode.

Lær mer om den 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.

Avhengig av elementet som skal settes inn, søkes i eller slettes, kan algoritmen enkelt fjerne venstre eller høyre undertre av rotnoden etter sammenligningen.

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

• Søke: søker etter elementet fra det binære treet.
• Sett inn: legger til et element i det binære treet.
• Slett: sletter elementet fra et binærtre.

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 analysen av treet ved rotnoden, og gå deretter videre til enten høyre eller venstre undertre av rotnoden, avhengig av om elementet som skal lokaliseres er mindre enn eller større enn roten.

1. Elementet som skal søkes etter er 10.
2. Sammenlign elementet med rotnoden 12, 10 < 12, dermed flytter du deg til venstre undertre. Du trenger ikke å analysere høyre undertre.
3. Sammenlign nå 10 med node 7, 10 > 7, så flytt til høyre undertre.
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.

Kallenavn Code for søking 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 enkel operasjon. Først settes rotnoden inn, deretter sammenlignes den neste verdien med rotnoden. Hvis verdien er større enn roten, legges den til i det høyre undertreet, og hvis den er mindre enn roten, legges den til i det venstre undertreet.

1. Det er en liste med seks elementer som må settes inn i en BST i rekkefølge fra venstre mot høyre.
2. Sett inn 12 som rotnode og sammenlign de neste verdiene 7 og 9 for å sette dem inn tilsvarende i høyre og venstre undertre.
3. Sammenlign de gjenværende verdiene 19, 5 og 10 med rotnoden 12 og plasser dem deretter. 19 > 12, plasser den som det høyre barnet til 12; 5 < 12 og 5 < 7, plasser den derfor som det venstre barnet til 7. Sammenlign nå 10, 10 er < 12 og 10 er > 7 og 10 er > 9, plasser 10 som det høyre undertreet til 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 finnes det noen tilfeller, f.eks. sletting av en rotnode 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 den underordnede noden til den overordnede noden til den slettede verdien.
• Tilfelle 3 – Node med to barn: Dette er den vanskeligste situasjonen, og den fungerer etter følgende to regler:
  • 3a – Forgjenger i rekkefølge: Du må slette noden med to barn og erstatte den med den største verdien i det venstre undertreet til den slettede noden.
  • 3b – Etterfølger i rekkefølge: Du må slette noden med to barn og erstatte den med den minste verdien i det høyre undertreet til den slettede noden.

1. Dette er det første tilfellet med sletting, der du sletter en node som ikke har noen barn. Som du kan se i diagrammet, har 19, 10 og 5 ingen barn. Men vi vil slette 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 av sletting, der du sletter en node som har ett barn. Som du kan se i diagrammet, har 9 ett barn.
2. Slett noden 9 og erstatt den med dens barnenode 10, og legg til en lenke fra 7 til 10.
3. Se den nye strukturen til BST uten 9.

1. Her sletter du noden 12 som har to barn.
2. Slettingen av noden vil skje basert på forgjengerregelen i rekkefølge, som betyr at det største elementet i det venstre undertreet av 12 vil erstatte den.
3. Slett noden 12 og erstatt den med 10, ettersom det er den største verdien i det venstre undertreet.
4. Se den nye strukturen til BST etter sletting av 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 minste elementet i det høyre undertreet av 12 vil erstatte den.
3. Slett noden 12 og erstatt den med 19, da det er den minste verdien på det høyre undertreet.
4. Se den nye strukturen til BST etter sletting av 12.

Kallenavn Code for sletting av 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, delete the successor
        free(newNode)
    else
        free(y)

Viktige vilkår

• Sett inn: Setter inn et element i et tre / oppretter et tre.
• Søke: Søker etter et element i et tre.
• Forhåndsbestillingsgjennomgang: Krysser et tre på en forhåndsbestilt måte.
• Ordregjennomgang: Krysser et tre på en ordnet måte.
• Postordre-gjennomgang: Krysser et tre på en etterordre-måte.

Spørsmål og svar