Hva er et binært søketre?

Et binært søketre er en av de ulike datastrukturene som hjelper oss med å organisere og sortere data. Det er en effektiv måte å lagre data i et hierarki og er veldig fleksibel.

I denne artikkelen skal vi se nærmere på hvordan det fungerer – sammen med dets egenskaper og applikasjoner.

Hva er et binært søketre?

Et binært søketre er en datastruktur som består av noder – som ligner på koblede lister. Det kan være to typer noder: en forelder og et barn. Rotnoden er startpunktet for strukturen som forgrener seg til to underordnede noder, kalt venstre node og høyre node.

Hver node kan bare refereres av sin overordnede, og vi kan krysse treets noder avhengig av retningen. Det binære søketreet har tre hovedegenskaper:

1. Den venstre noden er mindre enn dens overordnede.
2. Høyre node er større enn overordnet.
3. Venstre og høyre undertrær må være binære søketrær.

Et perfekt binært søketre oppnås når alle nivåer er fylt, og hver node har en venstre og høyre barnenode.

I slekt: Data Science Libraries for Python som enhver dataforsker bør bruke

Grunnleggende operasjoner for et binært søketre

Nå har du fått en bedre ide om hva et binært søketre er, vi kan se på de grunnleggende operasjonene nedenfor.

1. Søkeoperasjon

Søk lar oss finne en bestemt verdi i treet. Vi kan bruke to typer søk: bredde-først-søk (BFS) og dybde-først-søk (DFS). Bredde-først-søk er en søkealgoritme som begynner ved rotnoden og går horisontalt, fra side til side, til målet er funnet. Hver node besøkes én gang under dette søket.

Dybde-først-søk, derimot, krysser treet vertikalt – starter fra rotnoden og arbeider nedover en enkelt gren. Hvis målet blir funnet, avsluttes operasjonen. Men hvis ikke, det og søker de andre nodene.

2. Innsettingsoperasjon

Innsettingsoperasjonen bruker søkeoperasjonen for å bestemme plasseringen der den nye noden skal settes inn. Prosessen starter fra rotnoden, og søket begynner til målet er nådd. Det er tre tilfeller å vurdere med innsetting.

• Tilfelle 1: Når ingen node eksisterer. Noden som skal settes inn vil bli rotnoden.

• Tilfelle 2: Det er ingen barn. I dette tilfellet vil noden sammenlignes med rotnoden. Hvis det er større, vil det bli det rette barnet; ellers blir det venstre barn.

• Tilfelle 3: Når roten og dens barn er tilstede. Den nye noden vil bli sammenlignet med hver node på banen for å bestemme hvilken node den besøker neste gang. Hvis noden er større enn rotnoden, vil den gå nedover det høyre undertreet eller det venstre. På samme måte gjøres sammenligninger på hvert nivå for å avgjøre om det vil gå til høyre eller venstre til det ankommer destinasjonen.

3. Slett operasjon

Slettingsoperasjonen brukes til å fjerne en bestemt node i treet. Sletting anses som vanskelig, ettersom treet må omorganiseres etter fjerning av en node. Det er tre hovedsaker å vurdere:

• Tilfelle 1: Sletting av en bladnode. En bladnode er en node uten noen barn. Dette er det enkleste å fjerne siden det ikke påvirker noen annen node; vi krysser ganske enkelt treet til vi når det og sletter det.

• Tilfelle 2: Sletting av en node med ett barn. Sletting av en forelder med én node vil resultere i at barnet tar sin posisjon, og alle påfølgende noder vil flytte opp et nivå. Det blir ingen endring i undertrærnes struktur.

• Tilfelle 3: Sletting av en node med to barn. Når vi skal fjerne en node med to barn, må vi først finne en påfølgende node som kan ta sin posisjon. To noder kan erstatte den fjernede noden, etterfølgeren eller forgjengeren i rekkefølge. Den inordnede etterfølgeren er det høyre undertreets underordnede lengst til venstre, og den inordnede forgjengeren er det venstre undertreets underordnede lengst til høyre. Vi kopierer innholdet i etterfølgeren/forgjengeren til noden og sletter etterfølgeren/forgjengeren i rekkefølge.

I slekt: Hvordan bygge datastrukturer med JavaScript ES6-klasser

Hvordan krysse et binært søketre

Traversering er prosessen vi navigerer gjennom et binært søketre. Det gjøres for å finne et spesifikt element eller for å skrive ut et omriss av treet. Vi starter alltid fra rotnoden og må følge kantene for å komme til de andre nodene. Hver node bør betraktes som et undertre, og prosessen gjentas til alle noder er besøkt.

• Gjennomgang i ordre: Å krysse i rekkefølge vil produsere et kart i stigende rekkefølge. Med denne metoden starter vi fra venstre undertre og fortsetter til roten og høyre undertre.

• Forhåndsbestilling: I denne metoden besøkes rotnoden først, etterfulgt av venstre undertre og høyre undertre.

• Gjennomgang etter bestilling: Denne gjennomgangen innebærer å besøke rotnoden sist. Vi starter fra venstre undertre, deretter høyre undertre, og deretter rotnoden.

Real-World-applikasjoner

Så hvordan bruker vi binære søketrealgoritmer? Som det kan antas, er de ekstremt effektive til å søke og sortere. Den største styrken til binære trær er deres organiserte struktur. Den gjør det mulig å søke med bemerkelsesverdige hastigheter ved å kutte datamengden vi trenger å analysere med det halve per pass.

Binære søketrær lar oss effektivt vedlikeholde et datasett i dynamisk endring i en organisert form. For programmer som har data satt inn og fjernet ofte, er de svært nyttige. Videospillmotorer bruker en algoritme basert på trær kjent som binær rompartisjon for å hjelpe til med å gjøre objekter ryddige. Microsoft Excel og de fleste regnearkprogramvare bruker binære trær som sin grunnleggende datastruktur.

Du kan bli overrasket over å vite at morsekode bruker et binært søketre for å kode data. En annen fremtredende grunn til at binære søketrær er så nyttige, er deres mange variasjoner. Deres fleksibilitet har ført til at mange varianter er laget for å løse alle slags problemer. Når de brukes riktig, er binære søketrær en stor ressurs.

Binære søketrær: Det perfekte utgangspunktet

En av de viktigste måtene å måle en ingeniørs ekspertise på er gjennom deres kunnskap og anvendelse av datastrukturer. Datastrukturer er nyttige og kan bidra til å skape et mer effektivt system. Binary Search Trees er en flott introduksjon til datastrukturer for enhver utviklere som starter opp.

15 JavaScript-array-metoder du bør mestre i dag

Vil du forstå JavaScript-matriser, men kan ikke få tak i dem? Se våre JavaScript-eksempler for veiledning.

Les Neste

Om forfatteren