Implementering av et binært søketre

2024 Forfatter: Angel Austin | [email protected]. Sist endret: 2023-12-17 05:37

Binært søketre - en strukturert database som inneholder noder, to lenker til andre noder, høyre og venstre. Noder er et objekt i klassen som har data, og NULL er tegnet som markerer slutten av treet.

Det blir ofte referert til som BST, som har en spesiell egenskap: noder større enn roten er plassert til høyre for den, og mindre til venstre.

Generell teori og terminologi

I et binært søketre er hver node, unntatt roten, forbundet med en rettet kant fra en node til en annen, som kalles overordnet. Hver av dem kan kobles til et vilkårlig antall noder, k alt barn. Noder uten "barn" kalles blader (ytre noder). Elementer som ikke er blader kalles indre. Noder med samme forelder er søsken. Den øverste noden kalles roten. I BST, tilordne et element til hver node og sørg for at de har en spesiell egenskap satt for dem.

Treterminologi:

Dybden til en node er antall kanter definert fra roten til den.
Høyden til en node er antallet kanter definert fra den til det dypeste bladet.
Høyden på treet bestemmes av høyden på roten.
Binært søketre er et spesielt design, det gir det beste forholdet mellom høyde og antall noder.
Høyde h med maksim alt N noder O (log N).

Du kan enkelt bevise dette ved å telle nodene på hvert nivå, med start fra roten, forutsatt at den inneholder det største antallet av dem: n=1 + 2 + 4 + … + 2 h-1 + 2 h=2 t + 1 - 1 Å løse dette for h gir h=O (log n).

Fordeler med tre:

Respeiler de strukturelle relasjonene til dataene.
Brukes for å representere hierarkier.
Sørg for effektiv installasjon og søk.
Trær er svært fleksible data, som lar deg flytte undertrær med minimal innsats.

Søkemetode

Generelt, for å finne ut om en verdi er i BST, start et binært søketre ved roten og avgjør om det oppfyller kravene:

være ved roten;
være i venstre undertre av roten;
i høyre undertre av roten.

Hvis intet baseregister er tilfredsstilt, utføres et rekursivt søk i det tilsvarende undertreet. Det er faktisk to grunnleggende alternativer:

Treet er tomt - returner falskt.
Verdien er i rotnoden - return true.

Det skal bemerkes at et binært søketre med et utviklet skjema alltid begynner å søke langs stien fra roten til bladet. I verste fall går det helt til bladet. Derfor er den dårligste tiden proporsjonal med lengden på den lengste veien fra roten til bladet, som er høyden på treet. Generelt er dette når du trenger å vite hvor lang tid det tar å slå opp som en funksjon av antall verdier som er lagret i treet.

Med andre ord er det en sammenheng mellom antall noder i en BST og høyden på et tre, avhengig av dets "form". I verste fall har noder bare ett barn, og et balansert binært søketre er i hovedsak en koblet liste. For eksempel:

Dette treet har 5 noder og høyde=5. Å finne verdier i området 16-19 og 21-29 vil kreve følgende bane fra roten til bladet (noden som inneholder verdien 20), dvs., vil det ta tid proporsjon alt med antall noder. I beste fall har de alle 2 barn, og bladene ligger på samme dybde.

Dette binære søketreet har 7 noder og høyde=3. Generelt vil et tre som dette (fullt tre) ha en høyde på omtrent log 2 (N), der N er antall noder i treet. Verdien av log 2 (N) er antall ganger (2) N kan deles før null er nådd.

Opsummering: den verste tiden som trengs for å søke i BST er O (trehøyde). Det verste tilfellet "lineære" treet er O(N), der N er antall noder i treet. I beste fall er et "komplett" tre O(log N).

BST binært innlegg

Lurer på hvor den skal væreden nye noden er plassert i BST, du må forstå logikken, den må plasseres der brukeren finner den. I tillegg må du huske reglene:

Duplikater er ikke tillatt, forsøk på å sette inn en duplikatverdi vil gi et unntak.
Den offentlige innsettingsmetoden bruker en rekursiv "hjelper"-metode for å faktisk sette inn.
En node som inneholder en ny verdi settes alltid inn som et blad i BST.
Den offentlige innsettingsmetoden returnerer void, men hjelpemetoden returnerer en BSTnode. Den gjør dette for å håndtere tilfellet der noden som sendes til den er null.

Generelt indikerer hjelpemetoden at hvis det opprinnelige binære søketreet er tomt, er resultatet et tre med én node. Ellers vil resultatet være en peker til den samme noden som ble sendt som et argument.

Sletting i binær algoritme

Som du kanskje forventer, innebærer sletting av et element å finne en node som inneholder verdien som skal fjernes. Det er flere ting i denne koden:

BST bruker en hjelper, overbelastet slettemetode. Hvis elementet du leter etter ikke er i treet, vil hjelpemetoden til slutt bli k alt med n==null. Dette anses ikke som en feil, treet endres rett og slett ikke i dette tilfellet. Sletthjelpemetoden returnerer en verdi - en peker til det oppdaterte treet.
Når et blad fjernes, setter fjerningen fra det binære søketreet den tilsvarende underordnede pekeren til dets overordnede til null, eller roten til null hvis den som fjernes ernoden er en rot og har ingen barn.
Merk at sletteanropet må være ett av følgende: root=delete (root, key), n.setLeft (delete (n.getLeft (), key)), n.setRight (delete(n. getRight(), nøkkel)). Derfor er det i alle tre tilfellene riktig at slettemetoden bare returnerer null.
Når søket etter noden som inneholder verdien som skal slettes lykkes, er det tre alternativer: noden som skal slettes er et blad (har ingen barn), noden som skal slettes har ett barn, den har to barn.
Når noden som fjernes har ett barn, kan du ganske enkelt erstatte det med et barn, og returnere en peker til barnet.
Hvis noden som skal slettes har null eller 1 barn, vil slettemetoden "følge banen" fra roten til den noden. Så den dårligste tiden er proporsjonal med høyden på treet, både for søk og innsetting.

Hvis noden som skal fjernes har to barn, tas følgende trinn:

Finn noden som skal slettes, følg banen fra roten til den.
Finn den minste verdien av v i det høyre undertreet, fortsett langs stien til bladet.
Fjern verdien av v rekursivt, følg den samme banen som i trinn 2.
Dermed utføres i verste fall banen fra roten til bladet to ganger.

Rekkefølge av traverser

Traversal er en prosess som besøker alle noder i et tre. Fordi et C binært søketre er en ikke-lineær datastruktur, er det ingen unik traversering. For eksempel noen ganger flere traversalalgoritmergruppert i følgende to typer:

kryssdybde;
første pass.

Det er bare én type breddekryss - omgå nivået. Denne gjennomgangen besøker noder nivå ned og venstre, topp og høyre.

Det finnes tre forskjellige typer dybdekryssinger:

Bestått forhåndsbestilling - besøk først forelderen og deretter venstre og høyre barn.
Passing InOrder - besøker venstre barn, deretter forelder og høyre barn.
Past the PostOrder - besøker venstre barn, deretter høyre barn, så forelderen.

Eksempel på fire traverseringer av et binært søketre:

Forhåndsbestilling - 8, 5, 9, 7, 1, 12, 2, 4, 11, 3.
InOrder - 9, 5, 1, 7, 2, 12, 8, 4, 3, 11.
PostOrder - 9, 1, 2, 12, 7, 5, 3, 11, 4, 8.
LevelOrder - 8, 5, 4, 9, 7, 11, 1, 12, 3, 2.

Figuren viser rekkefølgen nodene besøkes i. Tallet 1 er den første noden i en bestemt traversering, og 7 er den siste noden.

Disse generelle gjennomgangene kan representeres som en enkelt algoritme, forutsatt at hver node besøkes tre ganger. Euler-turen er en tur rundt et binært tre hvor hver kant blir behandlet som en vegg som brukeren ikke kan krysse. I denne vandringen vil hver node bli besøkt enten til venstre, under eller til høyre. Euler-turen, som besøker nodene til venstre, fører til at preposisjonen omgås. Når nodene nedenfor besøkes, blir de krysset i rekkefølge. Og når nodene til høyre er besøkt - fåtrinn-for-trinn-omgåelse.

Navigering og feilsøking

For å gjøre det lettere å navigere i treet, lag funksjoner som først sjekker om de er venstre eller høyre barn. For å endre posisjonen til en node, må det være enkel tilgang til pekeren ved overordnet node. Det er veldig vanskelig å implementere et tre på riktig måte, så du må kjenne til og bruke feilsøkingsprosesser. Et binært søketre med en implementering har ofte pekere som faktisk ikke angir kjøreretningen.

For å finne ut av dette, brukes en funksjon som sjekker om treet kan være riktig, og hjelper til med å finne mange feil. For eksempel sjekker den om overordnet node er en underordnet node. Med assert(is_wellformed(root)) kan mange feil fanges opp for tidlig. Ved å bruke et par gitte bruddpunkter i denne funksjonen kan du også finne ut nøyaktig hvilken peker som er feil.

Function Konsolenausgabe

Denne funksjonen skyller hele treet til konsollen og er derfor veldig nyttig. Rekkefølgen som treutdatamålet utføres i er:

For å gjøre dette, må du først bestemme hvilken informasjon som skal sendes ut gjennom noden.
Og du må også vite hvor bredt og høyt treet er for å ta hensyn til hvor mye plass du skal ha.
Følgende funksjoner beregner denne informasjonen for treet og hvert undertre. Siden du bare kan skrive til konsollen linje for linje, må du også skrive ut treet linje for linje.
Nå trenger vi en annen måte å trekke oss påhele treet, ikke bare linje for linje.
Ved hjelp av dump-funksjonen kan du lese treet og forbedre utdataalgoritmen betraktelig når det gjelder hastighet.

Denne funksjonen vil imidlertid være vanskelig å bruke på store trær.

Kopier konstruktør og destruktor

Fordi et tre ikke er en triviell datastruktur, er det bedre å implementere en kopikonstruktør, en destruktor og en oppdragsoperatør. Destruktoren er enkel å implementere rekursivt. For veldig store trær kan den håndtere "haugoverløp". I dette tilfellet er det formulert iterativt. Ideen er å fjerne bladet som representerer den minste verdien av alle blader, så det er på venstre side av treet. Å kutte av de første bladene skaper nye, og treet krymper til det endelig slutter å eksistere.

Kopi-konstruktøren kan også implementeres rekursivt, men vær forsiktig hvis et unntak blir kastet. Ellers blir treet fort uoversiktlig og feilutsatt. Det er derfor den iterative versjonen foretrekkes. Tanken er å gå gjennom det gamle treet og det nye treet, som du ville gjort i destruktoren, og klone alle nodene som er i det gamle treet, men ikke de nye.

Med denne metoden er implementeringen av det binære søketreet alltid i en sunn tilstand og kan fjernes av destruktoren selv i en ufullstendig tilstand. Hvis et unntak oppstår, er alt du trenger å gjøre å instruere destruktoren om å slette det halvferdige treet. oppdragsoperatørkan enkelt implementeres ved hjelp av Kopier og bytt.

Opprette et binært søketre

Optimale binære søketrær er utrolig effektive hvis de administreres riktig. Noen regler for binære søketrær:

En overordnet node har maksim alt 2 underordnede noder.
Den venstre underordnede noden er alltid mindre enn den overordnede noden.
En gyldig underordnet node er alltid større enn eller lik den overordnede noden.

Matrisen som skal brukes til å bygge det binære søketreet:

En heltallsmatrise med sju verdier i usortert rekkefølge.
Den første verdien i matrisen er 10, så det første trinnet i å bygge treet er å lage en 10 rotnode, som vist her.
Med et sett med rotnoder vil alle andre verdier være underordnede av denne noden. Med henvisning til reglene, det første trinnet som må tas for å legge til 7 til treet er å sammenligne det med rotnoden.
Hvis verdien 7 er mindre enn 10, blir den venstre underordnede node.
Hvis verdien 7 er større enn eller lik 10, flyttes den til høyre. Siden 7 er kjent for å være mindre enn 10, er den utpekt som venstre underordnet node.
Utfør rekursivt sammenligninger for hvert element.
Følg det samme mønsteret, utfør den samme sammenligningen mot den 14. verdien i matrisen.
Sammenligning av verdien 14 med rotnoden 10, vel vitende om at 14 er det riktige barnet.
Å gå gjennom matrisen,kom til 20.
Begynn med å sammenligne matrisen med 10, avhengig av hva som er størst. Så flytt til høyre og sammenlign det med 14, han er over 14 og har ingen barn til høyre.
Nå er det en verdi på 1. Følg samme mønster som de andre verdiene, sammenlign 1 til 10, flytt til venstre og sammenlign med 7 og til slutt med det 1 venstre barnet til den 7. noden.
Hvis verdien er 5, sammenlign den med 10. Siden 5 er mindre enn 10, gå til venstre og sammenlign den med 7.
Vet at 5 er mindre enn 7, fortsett nedover treet og sammenlign 5 med 1 verdi.
Hvis 1 ikke har noen barn og 5 er større enn 1, er 5 et gyldig barn av 1 node.
Sett til slutt verdien 8 inn i treet.
Når 8 er mindre enn 10, flytt den til venstre og sammenlign den med 7, 8 er større enn 7, så flytt den til høyre og fullfør treet, og gjør 8 til et riktig barn på 7.

Å få og evaluere den enkle elegansen til optimale binære søketrær. Som mange emner innen programmering, kommer kraften til binære søketrær fra deres evne til å løse data i små, relaterte komponenter. Fra nå av kan du jobbe med hele datasettet på en organisert måte.

potensielle binære søkeproblemer

Binære søketrær er flotte, men det er noen forbehold du må huske på. De er vanligvis bare effektive hvis de er balanserte. Et balansert tre er et tre derforskjellen mellom høydene til undertrærne til en hvilken som helst node i treet er maksim alt én. La oss se på et eksempel som kan bidra til å tydeliggjøre reglene. La oss forestille oss at matrisen starter som sorterbar.

Hvis du prøver å kjøre en binær søketrealgoritme på dette treet, vil det fungere nøyaktig som om det bare skulle iterere gjennom matrisen til ønsket verdi er funnet. Kraften til binært søk ligger i muligheten til raskt å filtrere ut uønskede verdier. Når et tre ikke er balansert, vil det ikke gi de samme fordelene som et balansert tre.

Det er veldig viktig å undersøke dataene brukeren jobber med når man oppretter et binært søketre. Du kan integrere rutiner som array randomisering før du implementerer et binært søketre for heltall for å balansere det ut.

Eksempler på beregning av binære søk

Vi må finne ut hva slags tre som vil resultere hvis 25 settes inn i følgende binære søketre:

5 15

/ /

2 12 20

Når du setter inn x i et tre T som ennå ikke inneholder x, plasseres alltid nøkkelen x i et nytt blad. I forbindelse med dette vil det nye treet se slik ut:

5 15

/ /

2 12 20

Hva slags tre ville du fått hvis du satt inn 7 i følgende binære søketre?

5 15

/ /

2 12 20

Svar:

5 15

/ / /

2 7 12 20

Et binært søketre kan brukes til å lagre ethvert objekt. Fordelen med å bruke et binært søketre i stedet for en koblet liste er at hvis treet er rimelig balansert og mer som et "fullt" tre enn et "lineært", kan innsetting, søk og alle sletteoperasjoner implementeres for å kjøre i O(log N) tid.