Hvad er et binært søgetræ?
Det binære søgetræ er en avanceret algoritme, der bruges til at analysere noden, dens venstre og højre grene, som er modelleret i en træstruktur og returnerer værdien. BST er udtænkt på arkitekturen i en grundlæggende binær søgealgoritme; dermed muliggør det hurtigere opslag, indsættelser og fjernelse af noder. Dette gør programmet virkelig hurtigt og præcist.
I denne vejledning i datastruktur lærer du:
- Hvad er et binært søgetræ?
- Attributter for binært søgetræ
- Hvorfor har vi brug for et binært søgetræ?
- Typer af binære træer
- Hvordan fungerer binært søgetræ?
- Vigtige vilkår
Attributter for binært søgetræ
En BST er lavet af flere noder og består af følgende attributter:
- Noder på træet er repræsenteret i et forhold mellem forælder og barn
- Hver overordnet knude kan have nul underordnede noder eller maksimalt to undernoder eller undertræer på venstre og højre side.
- Hvert undertræ, også kendt som et binært søgetræ, har undergrene til højre og venstre for sig selv.
- Alle knudepunkter er forbundet med nøgleværdipar.
- Tasterne på de noder, der findes i det venstre undertræ, er mindre end nøglerne til deres overordnede knude
- Tilsvarende har de venstre subtrænoders nøgler mindre værdier end deres overordnede nodes nøgler.
- Der er hovedknudepunktet eller overordnet niveau 11. Under det er der venstre og højre knudepunkter / grene med deres egne nøgleværdier
- Det højre undertræ har nøgleværdier, der er større end den overordnede node
- Det venstre undertræ har værdier end den overordnede node
Hvorfor har vi brug for et binært søgetræ?
- De to hovedfaktorer, der gør binært søgetræ til en optimal løsning på eventuelle virkelige problemer er Hastighed og nøjagtighed.
- På grund af det faktum, at den binære søgning er i et grenlignende format med forældre-barn-forhold, ved algoritmen, i hvilken placering af træet elementerne skal søges. Dette mindsker antallet af nøgleværdi-sammenligninger, som programmet skal foretage for at finde det ønskede element.
- Derudover, hvis det element, der skal søges større eller mindre end forældrenoden, ved noden, hvilken træside der skal søges efter. Årsagen er, at det venstre undertræ altid er mindre end det overordnede knudepunkt, og det højre undertræ har værdier, der altid er lig med eller større end det overordnede knudepunkt.
- BST bruges almindeligvis til at implementere komplekse søgninger, robuste spillogik, auto-komplette aktiviteter og grafik.
- Algoritmen understøtter effektivt operationer som søgning, indsættelse og sletning.
Typer af binære træer
Tre slags binære træer er:
- Komplet binært træ: Alle niveauerne i træerne er fulde af sidste niveau mulige undtagelser. Tilsvarende er alle knudepunkter fulde og styrer længst til venstre.
- Fuldt binært træ: Alle knudepunkter har 2 underknudepunkter undtagen bladet.
- Balanceret eller perfekt binært træ: I træet har alle knudepunkter to børn. Derudover er der det samme niveau for hver subnode.
Hvordan fungerer binært søgetræ?
Træet har altid en rodnode og yderligere underknudepunkter, hvad enten det er til venstre eller højre. Algoritmen udfører alle operationerne ved at sammenligne værdier med roden og dens yderligere underknudepunkter i venstre eller højre undertræ i overensstemmelse hermed.
Afhænger af det element, der skal indsættes, søgning eller sletning, efter sammenligningen kan algoritmen let droppe venstre eller højre undertræ af rodnoden.
BST tilbyder primært følgende tre typer operationer til din brug:
- Søg: søger i elementet fra det binære træ
- Indsæt: tilføjer et element til det binære træ
- Slet: slet elementet fra et binært træ
Hver operation har sin egen struktur og metode til udførelse / analyse, men den mest komplekse af alle er Delete-operationen.
Søgning
Start altid at analysere træet ved rodknudepunktet, og flyt derefter længere til enten højre eller venstre undertræ af rodknudepunktet, afhængigt af hvilket element der skal placeres, er enten mindre eller større end roden.
- Det element, der skal søges, er 10
- Sammenlign elementet med rodknudepunktet 12, 10 <12, så du flytter til venstre undertræ. Ingen grund til at analysere det rigtige undertræ
- Sammenlign nu 10 med knude 7, 10> 7, så flyt til højre-undertræet
- Sammenlign derefter 10 med den næste node, som er 9, 10> 9, se i det rigtige undertræsbarn
- 10 matcher værdien i noden, 10 = 10, returner værdien til brugeren.
Indsæt operation
Dette er en meget ligetil operation. Først indsættes rodnoden, derefter sammenlignes den næste værdi med rodnoden. Hvis værdien er større end rod, føjes den til det højre undertræ, og hvis den er mindre end roden, føjes den til venstre undertræ.
- Der er en liste over 6 elementer, der skal indsættes i en BST i rækkefølge fra venstre til højre
- Indsæt 12 som rodknudepunkt, og sammenlign de næste værdier 7 og 9 for at indsætte det tilsvarende i højre og venstre undertræ
- Sammenlign de resterende værdier 19, 5 og 10 med rodnoden 12, og placer dem i overensstemmelse hermed. 19> 12 placer det som det højre barn på 12, 5 <12 & 5 <7, placer det derfor som venstre barn på 7.
- Sammenlign nu 10, 10 er <12 & 10 er> 7 & 10 er> 9, placer 10 som højre undertræ på 9.
Slet handlinger
Slet er den mest avancerede og komplekse blandt alle andre operationer. Der er flere sager behandlet til sletning i BST.
- Tilfælde 1- Knude med nul børn: dette er den nemmeste situation, du skal bare slette den knude, der ikke har flere børn til højre eller venstre.
- Tilfælde 2 - Node med et barn: Når du sletter noden, skal du blot forbinde dens undernode med den overordnede node for den slettede værdi.
- Tilfælde 3 Knude med to børn: dette er den sværeste situation, og den fungerer efter følgende to regler
- 3a - I rækkefølge forgænger: du skal slette noden med to børn og erstatte den med den største værdi i venstre undertræ i den slettede node
- 3b - Efterfølger i rækkefølge: du skal slette noden med to børn og erstatte den med den største værdi i højre undertræ i den slettede node
- Dette er det første tilfælde af sletning, hvor du sletter en node, der ikke har nogen børn. Som du kan se i diagrammet, at 19, 10 og 5 ikke har børn. Men vi sletter 19.
- Slet værdien 19, og fjern linket fra noden.
- Se BST's nye struktur uden 19
- Dette er det andet tilfælde af sletning, hvor du sletter en node, der har 1 barn, som du kan se i diagrammet, at 9 har et barn.
- Slet knudepunkt 9, og udskift det med dets underordnede 10, og tilføj et link fra 7 til 10
- Se BST's nye struktur uden 9
- Her sletter du noden 12, der har to børn
- Sletningen af noden vil ske baseret på forgængerreglen i rækkefølge, hvilket betyder at det største element i venstre undertræ på 12 vil erstatte det.
- Slet knudepunkt 12, og udskift det med 10, da det er den største værdi i venstre undertræ
- Se BST's nye struktur efter sletning af 12
- 1 Slet en node 12, der har to børn
- 2 Sletningen af noden vil ske baseret på In Order Successor-reglen, hvilket betyder at det største element på højre undertræ på 12 erstatter det
- 3 Slet knudepunktet 12 og udskift det med 19, da det er den største værdi på det højre undertræ
- 4 Se den nye struktur for BST efter sletning 12
Vigtige vilkår
- Indsæt - Indsætter et element i et træ / opret et træ.
- Søg - Søger efter et element i et træ.
- Forudbestil gennemgang - Traverserer et træ på en forudbestilt måde.
- Inorder Traversal - Krydser et træ på en rækkefølge.
- Postorder Traversal - Traverserer et træ på en postordre måde.
Resumé
- BST er en avanceret algoritme, der udfører forskellige operationer baseret på sammenligningen af knudepunktværdier med rodknudepunktet.
- Ethvert af punkterne i et forældre-barn hierarki repræsenterer noden. Mindst en forælder eller rodnode forbliver til stede hele tiden.
- Der er et venstre undertræ og det højre undertræ. Det venstre undertræ indeholder værdier, der er mindre end rodnoden. Det rigtige undertræ indeholder dog en værdi, der er større end rodnoden.
- Hver knude kan have enten nul, et eller to børn.
- Et binært søgetræ letter primære operationer som søgning, indsættelse og sletning.
- Slet som det mest komplekse har flere tilfælde, for eksempel en node uden barn, node med et barn og node med to børn.
- Algoritmen bruges i virkelige løsninger som spil, autofuldførelsesdata og grafik.