Implementering af et binært søgetræ

2024 Forfatter: Angel Austin | [email protected]. Sidst ændret: 2023-12-17 05:21

Binært søgetræ - en struktureret database, der indeholder noder, to links til andre noder, højre og venstre. Noder er et objekt af klassen, der har data, og NULL er tegnet, der markerer enden af træet.

Det omtales ofte som BST, som har en speciel egenskab: noder, der er større end roden, er placeret til højre for den, og mindre til venstre.

Generel teori og terminologi

I et binært søgetræ er hver node, eksklusive roden, forbundet med en rettet kant fra en node til en anden, som kaldes forælderen. Hver af dem kan forbindes med et vilkårligt antal noder, kaldet børn. Noder uden "børn" kaldes blade (ydre noder). Elementer, der ikke er blade, kaldes indre. Noder med samme forælder er søskende. Den øverste knude kaldes roden. I BST skal du tildele et element til hver node og sørge for, at de har en speciel egenskab indstillet til dem.

Træterminologi:

Dybden af en node er antallet af kanter defineret fra roden til den.
Højden af en node er antallet af kanter defineret fra den til det dybeste blad.
Højden på træet bestemmes af rodens højde.
Binært søgetræ er et specielt design, det giver det bedste forhold mellem højde og antal noder.
Højde h med N noder højst O (log N).

Du kan nemt bevise dette ved at tælle noderne på hvert niveau, begyndende fra roden, forudsat at det indeholder det største antal af dem: n=1 + 2 + 4 + … + 2 h-1 + 2 h=2 h + 1 - 1 Løsning af dette for h giver h=O (log n).

Fordele ved træ:

Afspejler dataens strukturelle relationer.
Bruges til at repræsentere hierarkier.
Sørg for effektiv installation og søgning.
Træer er meget fleksible data, der giver dig mulighed for at flytte undertræer med minimal indsats.

Søgemetode

For at afgøre, om en værdi er i BST, skal du generelt starte et binært søgetræ ved roden og afgøre, om det opfylder kravene:

være ved roden;
være i venstre undertræ af rod;
i det højre undertræ af rod.

Hvis intet basisregister er opfyldt, udføres en rekursiv søgning i det tilsvarende undertræ. Der er faktisk to grundlæggende muligheder:

Træet er tomt - returner falsk.
Værdien er i rodnoden - returner sand.

Det skal bemærkes, at et binært søgetræ med et udviklet skema altid begynder at søge langs stien fra roden til bladet. I værste fald går det helt til bladet. Derfor er den værste tid proportional med længden af den længste vej fra roden til bladet, som er træets højde. Generelt er det, når du skal vide, hvor lang tid det tager at slå op som funktion af antallet af værdier gemt i træet.

Med andre ord er der en sammenhæng mellem antallet af noder i en BST og højden af et træ, afhængigt af dets "form". I værste tilfælde har noder kun ét barn, og et balanceret binært søgetræ er i det væsentlige en sammenkædet liste. For eksempel:

Dette træ har 5 noder og højde=5. At finde værdier i intervallet 16-19 og 21-29 vil kræve følgende sti fra roden til bladet (den knude, der indeholder værdien 20), dvs., vil det tage tid proportion alt med antallet af noder. I bedste fald har de alle 2 børn, og bladene er placeret i samme dybde.

Dette binære søgetræ har 7 noder og højde=3. Generelt vil et træ som dette (fuldt træ) have en højde på ca. log 2 (N), hvor N er antallet af noder i træet. Værdien af log 2 (N) er antallet af gange (2), som N kan divideres, før nul nås.

Opsummering: den værste tid, der er nødvendig for at søge i BST, er O (træhøjde). Det værste tilfælde "lineære" træ er O(N), hvor N er antallet af noder i træet. I bedste fald er et "komplet" træ O(log N).

BST binært indsæt

Gad vide hvor den skulle væreden nye node er placeret i BST, du skal forstå logikken, den skal placeres, hvor brugeren finder den. Derudover skal du huske reglerne:

Duplikater er ikke tilladt, forsøg på at indsætte en dubletværdi vil give en undtagelse.
Den offentlige indsættelsesmetode bruger en rekursiv "hjælper"-metode til faktisk at indsætte.
En node, der indeholder en ny værdi, indsættes altid som et blad i BST.
Den offentlige indsættelsesmetode returnerer void, men hjælpermetoden returnerer en BSTnode. Det gør det for at håndtere det tilfælde, hvor noden, der sendes til den, er null.

Hjælpermetoden indikerer generelt, at hvis det originale binære søgetræ er tomt, er resultatet et træ med én node. Ellers vil resultatet være en pegepind til den samme node, der blev sendt som et argument.

Sletning i binær algoritme

Som du kunne forvente, involverer sletning af et element at finde en node, der indeholder den værdi, der skal fjernes. Der er flere ting i denne kode:

BST bruger en hjælper, overbelastet slettemetode. Hvis det element, du leder efter, ikke er i træet, vil hjælpemetoden til sidst blive kaldt med n==null. Dette betragtes ikke som en fejl, træet ændrer sig simpelthen ikke i dette tilfælde. Slethjælpemetoden returnerer en værdi - en pegepind til det opdaterede træ.
Når et blad fjernes, sætter fjernelse fra det binære søgetræ den tilsvarende underordnede pointer for dets overordnede til null, eller roden til null, hvis den, der fjernes, erknudepunktet er en rod og har ingen børn.
Bemærk, at sletteopkaldet skal være et af følgende: root=delete (rod, tast), n.setLeft (slet (n.getLeft (), tast)), n.setRight (delete(n. getRight(), nøgle)). I alle tre tilfælde er det således korrekt, at slettemetoden blot returnerer null.
Når søgningen efter noden, der indeholder værdien, der skal slettes, lykkes, er der tre muligheder: noden, der skal slettes, er et blad (har ingen børn), noden, der skal slettes, har et underordnet, den har to børn.
Når knudepunktet, der fjernes, har ét underordnet, kan du blot erstatte det med et underordnet og returnere en markør til barnet.
Hvis noden, der skal slettes, har nul eller 1 underordnede, så vil slettemetoden "følge stien" fra roden til den node. Så den værste tid er proportional med træets højde, både for søgning og indsættelse.

Hvis noden, der skal fjernes, har to børn, tages følgende trin:

Find den node, der skal slettes, ved at følge stien fra roden til den.
Find den mindste værdi af v i det højre undertræ, fortsæt langs stien til bladet.
Fjern værdien af v rekursivt, følg den samme sti som i trin 2.
Således udføres i værste fald vejen fra roden til bladet to gange.

Rækkefølge af traverser

Traversal er en proces, der besøger alle noder i et træ. Fordi et C binært søgetræ er en ikke-lineær datastruktur, er der ingen unik gennemgang. For eksempel nogle gange flere traversalalgoritmergrupperet i følgende to typer:

krydsningsdybde;
første pass.

Der er kun én slags breddekrydsning - omgå niveauet. Denne gennemkøring besøger noder niveau ned og venstre, top og højre.

Der er tre forskellige typer dybdekrydsninger:

Bestå forudbestilling - besøg først forælderen og derefter venstre og højre barn.
Passing InOrder - besøger det venstre barn, derefter forælderen og det højre barn.
Forbi postordren - besøger det venstre barn, derefter det højre barn og derefter forælderen.

Eksempel på fire gennemløb af et binært søgetræ:

Forudbestilling - 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 rækkefølgen, hvori noder besøges. Tallet 1 er den første knude i en bestemt gennemløb, og 7 er den sidste knude.

Disse generelle gennemløb kan repræsenteres som en enkelt algoritme, forudsat at hver node besøges tre gange. Euler-turen er en tur rundt om et binært træ, hvor hver kant behandles som en mur, som brugeren ikke kan krydse. I denne gåtur vil hver knude blive besøgt enten til venstre, under eller til højre. Euler-turen, som besøger noderne til venstre, får præpositionen til at blive omgået. Når knudepunkterne nedenfor besøges, bliver de krydset i rækkefølge. Og når noderne til højre er besøgt - fåtrin-for-trin omgåelse.

Navigation og fejlretning

For at gøre det nemmere at navigere i træet skal du oprette funktioner, der først kontrollerer, om de er venstre eller højre underordnede. For at ændre positionen af en node skal der være nem adgang til markøren ved den overordnede node. Korrekt implementering af et træ er meget vanskeligt, så du skal kende og anvende fejlfindingsprocesser. Et binært søgetræ med en implementering har ofte pointere, der faktisk ikke angiver kørselsretningen.

For at finde ud af det hele, bruges en funktion, der tjekker om træet kan være korrekt, og hjælper med at finde mange fejl. For eksempel tjekker den, om den overordnede node er en underordnet node. Med assert(is_wellformed(root)) kan mange fejl fanges for tidligt. Ved at bruge et par givne brudpunkter i denne funktion kan du også bestemme præcis, hvilken markør der er forkert.

Function Konsolenausgabe

Denne funktion skyller hele træet til konsollen og er derfor meget nyttig. Den rækkefølge, som træoutputmålet udføres i, er:

For at gøre dette skal du først bestemme, hvilken information der skal udsendes gennem noden.
Og du skal også vide, hvor bredt og højt træet er for at tage højde for, hvor meget plads der skal efterlades.
De følgende funktioner beregner denne information for træet og hvert undertræ. Da du kun kan skrive til konsollen linje for linje, skal du også udskrive træet linje for linje.
Nu har vi brug for en anden måde at trække os påhele træet, ikke kun linje for linje.
Ved hjælp af dump-funktionen kan du læse træet og forbedre outputalgoritmen markant, hvad angår hastighed.

Denne funktion vil dog være svær at bruge på store træer.

Kopier konstruktør og destruktor

Fordi et træ ikke er en triviel datastruktur, er det bedre at implementere en kopikonstruktør, en destruktor og en tildelingsoperator. Destruktoren er nem at implementere rekursivt. Til meget store træer kan den klare "dyngeoverløb". I dette tilfælde er det formuleret iterativt. Ideen er at fjerne bladet, der repræsenterer den mindste værdi af alle blade, så det er på venstre side af træet. At skære de første blade af skaber nye, og træet krymper, indtil det endelig holder op med at eksistere.

Kopi-konstruktøren kan også implementeres rekursivt, men vær forsigtig, hvis der er en undtagelse. Ellers bliver træet hurtigt forvirrende og fejludsat. Derfor foretrækkes den iterative version. Ideen er at gå gennem det gamle træ og det nye træ, som du ville gøre i destruktoren, og klone alle de noder, der er i det gamle træ, men ikke de nye.

Med denne metode er implementeringen af det binære søgetræ altid i en sund tilstand og kan fjernes af destruktoren selv i en ufuldstændig tilstand. Hvis der opstår en undtagelse, er det eneste, du skal gøre, at instruere destruktoren om at slette det halvfærdige træ. opgaveoperatørkan nemt implementeres ved hjælp af Copy & Swap.

Oprettelse af et binært søgetræ

Optimale binære søgetræer er utroligt effektive, hvis de administreres korrekt. Nogle regler for binære søgetræer:

En overordnet node har højst 2 underordnede noder.
Den venstre underordnede node er altid mindre end den overordnede node.
En gyldig underordnet node er altid større end eller lig med den overordnede node.

Arrayet, der vil blive brugt til at bygge det binære søgetræ:

En heltalsmatrix med syv værdier i usorteret rækkefølge.
Den første værdi i arrayet er 10, så det første trin i opbygningen af træet er at skabe en 10 rodnode, som vist her.
Med et sæt rodnoder vil alle andre værdier være børn af denne node. Med henvisning til reglerne er det første skridt, der skal tages for at tilføje 7 til træet, at sammenligne det med rodnoden.
Hvis værdien 7 er mindre end 10, bliver den venstre underordnede node.
Hvis værdien 7 er større end eller lig med 10, flyttes den til højre. Da 7 vides at være mindre end 10, er den udpeget som den venstre underordnede node.
Udfør rekursivt sammenligninger for hvert element.
Følg det samme mønster, udfør den samme sammenligning med den 14. værdi i arrayet.
Sammenligning af værdien 14 med rodnoden 10, vel vidende at 14 er det korrekte underordnede.
Vandrer gennem arrayet,kom til 20.
Start med at sammenligne matrixen med 10, alt efter hvad der er størst. Så flyt til højre og sammenlign det med 14, han er over 14 og har ingen børn til højre.
Nu er der en værdi på 1. Følg samme mønster som de andre værdier, sammenlign 1 med 10, flyt til venstre og sammenlign med 7 og til sidst med det 1 venstre underordnede af den 7. node.
Hvis værdien er 5, skal du sammenligne den med 10. Da 5 er mindre end 10, skal du gå til venstre og sammenligne den med 7.
Ved at 5 er mindre end 7, fortsæt ned i træet og sammenlign 5 med 1 værdi.
Hvis 1 ikke har nogen børn, og 5 er større end 1, så er 5 et gyldigt underordnet af 1 node.
Indsæt endelig værdien 8 i træet.
Når 8 er mindre end 10, skal du flytte det til venstre og sammenligne det med 7, 8 er større end 7, så flyt det til højre og færdiggør træet, hvilket gør 8 til et rigtigt barn på 7.

Få og evaluere den enkle elegance af optimale binære søgetræer. Ligesom mange emner inden for programmering kommer kraften ved binære søgetræer fra deres evne til at opløse data i små, relaterede komponenter. Fra nu af kan du arbejde med det fulde datasæt på en organiseret måde.

Potentielle binære søgeproblemer

Binære søgetræer er fantastiske, men der er et par forbehold, du skal huske på. De er norm alt kun effektive, hvis de er afbalancerede. Et balanceret træ er et træ, hvoriforskellen mellem højderne af undertræerne i enhver knude i træet er højst én. Lad os se på et eksempel, der kan hjælpe med at tydeliggøre reglerne. Lad os forestille os, at arrayet starter som sorterbart.

Hvis du forsøger at køre en binær søgetræ-algoritme på dette træ, vil den fungere nøjagtigt, som om den bare gentog arrayet, indtil den ønskede værdi er fundet. Styrken ved binær søgning ligger i evnen til hurtigt at bortfiltrere uønskede værdier. Når et træ ikke er afbalanceret, vil det ikke give de samme fordele som et balanceret træ.

Det er meget vigtigt at undersøge de data, brugeren arbejder med, når der oprettes et binært søgetræ. Du kan integrere rutiner såsom matrixrandomisering, før du implementerer et binært søgetræ for heltal for at balancere det.

Binære søgeberegningseksempler

Vi er nødt til at bestemme, hvilken slags træ der vil resultere, hvis 25 indsættes i følgende binære søgetræ:

5 15

/ /

2 12 20

Når du indsætter x i et træ T, der endnu ikke indeholder x, placeres nøglen x altid i et nyt blad. I forbindelse hermed kommer det nye træ til at se sådan ud:

5 15

/ /

2 12 20

Hvilken slags træ ville du få, hvis du indsatte 7 i det følgende binære søgetræ?

5 15

/ /

2 12 20

Svar:

5 15

/ / /

2 7 12 20

Et binært søgetræ kan bruges til at gemme ethvert objekt. Fordelen ved at bruge et binært søgetræ i stedet for en linket liste er, at hvis træet er rimeligt afbalanceret og mere som et "fuldt" træ end et "lineært", kan indsættelse, søgning og alle sletningsoperationer implementeres til at køre i O(log N) tid.