Hvad er et binært søgetræ?

Et binært søgetræ er en af ​​de forskellige datastrukturer, der hjælper os med at organisere og sortere data. Det er en effektiv måde at gemme data i et hierarki og er meget fleksibel.

I denne artikel vil vi se nærmere på, hvordan det virker – sammen med dets egenskaber og applikationer.

Hvad er et binært søgetræ?

Et binært søgetræ er en datastruktur, der er sammensat af noder – svarende til linkede lister. Der kan være to typer noder: en forælder og et barn. Rodknuden er startpunktet for strukturen, der forgrener sig til to underordnede knudepunkter, kaldet venstre knude og højre knude.

Hver knude kan kun refereres af sin forælder, og vi kan krydse træets knudepunkter afhængigt af retningen. Det binære søgetræ har tre hovedegenskaber:

1. Den venstre knude er mindre end dens forælder.
2. Den højre node er større end dens forælder.
3. Venstre og højre undertræer skal være binære søgetræer.

Et perfekt binært søgetræ opnås, når alle niveauer er fyldt, og hver knude har en venstre og højre underknude.

Relaterede: Data Science-biblioteker til Python, som enhver dataforsker bør bruge

Grundlæggende betjening af et binært søgetræ

Nu har du fået en bedre idé om, hvad et binært søgetræ er, vi kan se på dets grundlæggende funktioner nedenfor.

1. Søgeoperation

Søgning giver os mulighed for at finde en bestemt værdi i træet. Vi kan bruge to typer søgninger: bredde-først-søgning (BFS) og dybde-først-søgning (DFS). Bredde-først-søgning er en søgealgoritme, der begynder ved rodknudepunktet og krydser vandret fra side til side, indtil målet er fundet. Hver node besøges én gang under denne søgning.

Dybde-første søgning på den anden side krydser træet lodret - startende fra rodknuden og arbejder ned ad en enkelt gren. Hvis målet er fundet, afsluttes operationen. Men hvis ikke, det og søger de andre noder.

2. Indsæt operation

Indsættelsesoperationen udnytter søgeoperationen til at bestemme placeringen, hvor den nye knude skal indsættes. Processen starter fra rodnoden, og søgningen begynder, indtil destinationen er nået. Der er tre tilfælde at overveje med indsættelse.

• Case 1: Når ingen node eksisterer. Den knude, der skal indsættes, bliver rodknuden.

• Case 2: Der er ingen børn. I dette tilfælde vil noden blive sammenlignet med rodnoden. Hvis det er større, bliver det det rigtige barn; ellers bliver det det venstre barn.

• Case 3: Når roden og dens børn er til stede. Den nye node vil blive sammenlignet med hver node på sin vej for at bestemme, hvilken node den besøger næste gang. Hvis noden er større end rodknuden, vil den krydse ned i højre undertræ eller venstre. På samme måde foretages sammenligninger på hvert niveau for at afgøre, om det vil gå til højre eller venstre, indtil det ankommer til sin destination.

3. Slet handling

Sletningsoperationen bruges til at fjerne en bestemt node i træet. Sletning betragtes som vanskelig, da træet skal omorganiseres i overensstemmelse hermed efter at have fjernet en node. Der er tre hovedsager at overveje:

• Case 1: Sletning af en bladknude. En bladknude er en knude uden børn. Dette er det nemmeste at fjerne, da det ikke påvirker nogen anden node; vi krydser simpelthen træet indtil vi når det og sletter det.

• Case 2: Sletning af en node med et barn. Sletning af en forælder med én node vil resultere i, at barnet tager sin position, og alle efterfølgende noder vil rykke et niveau op. Der vil ikke være nogen ændring i undertræernes struktur.

• Case 3: Sletning af en node med to børn. Når vi skal fjerne en node med to børn, skal vi først finde en efterfølgende node, der kan tage sin position. To noder kan erstatte den fjernede node, efterfølgeren eller forgængeren i rækkefølgen. Den inordnede efterfølger er det højre undertræs underordnede længst til venstre, og den inordnede forgænger er det venstre undertræs længst til højre underordnede. Vi kopierer indholdet af efterfølgeren/forgængeren til noden og sletter efterfølgeren/forgængeren i rækkefølge.

Relaterede: Sådan bygger du datastrukturer med JavaScript ES6-klasser

Sådan krydser du et binært søgetræ

Traversal er den proces, hvorigennem vi navigerer i et binært søgetræ. Det gøres for at lokalisere et bestemt emne eller for at udskrive en oversigt over træet. Vi starter altid fra rodknuden og skal følge kanterne for at komme til de andre knudepunkter. Hver node bør betragtes som et undertræ, og processen gentages, indtil alle noder er besøgt.

• Gennemgang i ordre: At krydse i rækkefølge vil producere et kort i stigende rækkefølge. Med denne metode starter vi fra venstre undertræ og fortsætter til rod og højre undertræ.

• Forudbestilling gennemkørsel: I denne metode besøges rodknuden først, efterfulgt af venstre undertræ og højre undertræ.

• Gennemgang efter ordre: Denne gennemkøring involverer at besøge rodknuden sidst. Vi starter fra venstre undertræ, derefter højre undertræ og derefter rodknudepunktet.

Real-World-applikationer

Så hvordan bruger vi binære søgetræalgoritmer? Som det kan formodes, er de ekstremt effektive til at søge og sortere. Den største styrke ved binære træer er deres organiserede struktur. Det gør det muligt at søge med bemærkelsesværdige hastigheder ved at reducere mængden af ​​data, vi skal analysere, med det halve pr.

Binære søgetræer giver os mulighed for effektivt at vedligeholde et dynamisk skiftende datasæt i en organiseret form. For programmer, der ofte har indsat og fjernet data, er de meget nyttige. Videospilsmotorer bruger en algoritme baseret på træer kendt som binær rumpartition for at hjælpe med at gøre objekter velordnet. Microsoft Excel og de fleste regnearkssoftware bruger binære træer som deres grundlæggende datastruktur.

Du kan blive overrasket over at vide, at morsekode bruger et binært søgetræ til at kode data. En anden fremtrædende årsag til, at binære søgetræer er så nyttige, er deres mange variationer. Deres fleksibilitet har ført til, at der er skabt adskillige varianter til at løse alle mulige problemer. Når de bruges korrekt, er binære søgetræer et stort aktiv.

Binære søgetræer: Det perfekte udgangspunkt

En af de vigtigste måder at måle en ingeniørs ekspertise på er gennem deres viden og anvendelse af datastrukturer. Datastrukturer er nyttige og kan hjælpe med at skabe et mere effektivt system. Binære søgetræer er en fantastisk introduktion til datastrukturer for enhver udvikler, der starter.

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

Vil du forstå JavaScript-arrays, men kan du ikke få styr på dem? Tjek vores JavaScript-array-eksempler for vejledning.

Læs Næste

Om forfatteren