Binært søgetræ (BST) med eksempel

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 returnere værdien. BST er udformet på arkitekturen af ​​en grundlæggende binær søgealgoritme; derfor muliggør den hurtigere opslag, indsættelser og fjernelser af noder. Dette gør programmet virkelig hurtigt og præcist.

Attributter af binært søgetræ

En BST er lavet af flere noder og består af følgende attributter:

• Noderne i træet er repræsenteret i en forælder-barn-relation.
• Hver overordnet node kan have nul underknuder 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 noder er forbundet med nøgleværdi-par.
• Nøglerne til de noder, der findes i det venstre undertræ, er mindre end nøglerne til deres overordnede node.
• Tilsvarende er nøglerne til de noder, der findes i det højre undertræ, større end nøglerne til deres overordnede node.

1. Der er hovednoden eller overordnet niveau 11. Under den er der venstre og højre noder/grene med deres egne nøgleværdier.
2. Det højre undertræ har nøgleværdier, der er større end den overordnede nod.
3. Det venstre undertræ har færre nøgleværdier end den overordnede nod.

Hvorfor har vi brug for et binært søgetræ?

• De to hovedfaktorer, der gør et binært søgetræ til en optimal løsning på ethvert virkeligt problem, 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-relationer, ved algoritmen, hvor i træet elementerne skal søges. Dette reducerer antallet af nøgleværdi-sammenligninger, som programmet skal foretage for at finde det ønskede element.
• Derudover, hvis det element, der skal søges i, er større eller mindre end den overordnede node, ved noden, hvilken træside den skal søge i. Årsagen er, at det venstre undertræ altid er mindre end den overordnede node, og det højre undertræ har værdier, der altid er lig med eller større end den overordnede node.
• BST bruges almindeligvis til at implementere komplekse søgninger, robuste spillogikker, autofuldførelsesaktiviteter og grafik.
• Algoritmen understøtter effektivt operationer som søgning, indsæt og slet.

Typer af binære træer

Tre slags binære træer er:

• Komplet binært træ: Alle niveauerne i træet er fulde, med en mulig undtagelse på det sidste niveau. Tilsvarende er alle noderne fulde og peger yderst til venstre.
• Fuldt binært træ: Alle noderne har 2 underordnede noder undtagen bladet.
• Balanceret eller perfekt binært træ: I træet har alle noder to børn. Derudover er der samme niveau for hver undernode.

Lær mere om Binært træ i datastruktur hvis du er interesseret.

Hvordan fungerer binært søgetræ?

Træet har altid en rodknude og yderligere børneknuder, uanset om det er til venstre eller højre. Algoritmen udfører alle operationerne ved at sammenligne værdier med roden og dens yderligere underordnede noder i venstre eller højre undertræ i overensstemmelse hermed.

Afhængigt af det element, der skal indsættes, søges i eller slettes, kan algoritmen efter sammenligningen nemt fjerne det venstre eller højre undertræ af rodknuden.

BST tilbyder primært følgende tre typer operationer til dit brug:

• Søge: søger efter elementet fra det binære træ.
• Indsæt: tilføjer et element til det binære træ.
• Slette: sletter 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 Slet-operationen.

Søg Operation

Start altid analysen af ​​træet ved rodnoden og bevæg dig derefter videre til enten højre eller venstre undertræ af rodnoden, afhængigt af om det element, der skal lokaliseres, er mindre end eller større end roden.

1. Elementet der skal søges efter er 10.
2. Sammenlign elementet med rodknuden 12, 10 < 12, dermed flytter du til det venstre undertræ. Det er ikke nødvendigt at analysere det højre undertræ.
3. Sammenlign nu 10 med node 7, 10 > 7, så flyt til det højre undertræ.
4. Sammenlign derefter 10 med den næste node, som er 9, 10 > 9, kig i det højre undertræbarn.
5. 10 matcher med værdien i noden, 10 = 10, returnerer værdien til brugeren.

Kaldenavn Code til søgning i BST

search(element, root)
    if !root
        return -1
    if root.value == element
        return 1
    if root.value < element
        search(element, root.right)
    else
        search(element, root.left)

indsatte 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 roden, tilføjes den til det højre undertræ, og hvis den er mindre end roden, tilføjes den til det venstre undertræ.

1. Der er en liste med 6 elementer, der skal indsættes i en BST i rækkefølge fra venstre mod højre.
2. Indsæt 12 som rodknude og sammenlign de næste værdier 7 og 9 for at indsætte dem i det højre og venstre undertræ.
3. Sammenlign de resterende værdier 19, 5 og 10 med rodknuden 12, og placer dem i overensstemmelse hermed. 19 > 12, placer den som det højre barn af 12; 5 < 12 og 5 < 7, placer den derfor som det venstre barn af 7. Sammenlign nu 10, 10 er < 12, og 10 er > 7, og 10 er > 9, placer 10 som det højre undertræ af 9.

Pseudokode til at indsætte en node i BST

insert (element, root)
    Node x = root
    Node y = NULL
    while x:
        y = x
        if x.value < element.value
            x = x.right
        else
            x = x.left
    if y.value < element
        y.right = element
    else
        y.left = element

Slette Operationer

Der er nogle tilfælde, hvor man kan slette en node fra en BST, f.eks. slette en rod eller slette en bladnode. Efter at have slettet en rod, skal vi også tænke på rodknuden.

Sig, at vi vil slette en bladknude, vi kan bare slette den, men hvis vi vil slette en rod, skal vi erstatte rodens værdi med en anden knude. Lad os tage følgende eksempel:

• Tilfælde 1 – Knude med nul børn: Dette er den nemmeste situation, du skal bare slette den node, som ikke har yderligere underordnede til højre eller venstre.
• Tilfælde 2 – Knude med ét barn: Når du har slettet noden, skal du blot forbinde dens underordnede node med den overordnede node for den slettede værdi.
• Case 3 – Knude med to børn: Dette er den vanskeligste situation, og den fungerer ud fra følgende to regler:
  • 3a – Forgænger i rækkefølge: Du skal slette noden med to undernoder og erstatte den med den største værdi i det venstre undertræ af den slettede node.
  • 3b – Efterfølger i rækkefølge: Du skal slette noden med to undernoder og erstatte den med den mindste værdi i det højre undertræ af den slettede node.

1. 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, har 19, 10 og 5 ingen børn. Men vi sletter 19.
2. Slet værdien 19 og fjern linket fra noden.
3. Se den nye struktur for BST uden 19.

1. Dette er det andet tilfælde af sletning, hvor du sletter en node, der har 1 barn. Som du kan se i diagrammet, har 9 ét barn.
2. Slet noden 9 og erstat den med dens underordnede noden 10, og tilføj et link fra 7 til 10.
3. Se den nye struktur for BST uden 9.

1. Her sletter du node 12, der har to underordnede.
2. Sletningen af ​​noden vil ske baseret på forgængerreglen i rækkefølge, hvilket betyder, at det største element i det venstre undertræ af 12 vil erstatte det.
3. Slet knude 12 og erstat den med 10, da det er den største værdi i det venstre undertræ.
4. Se den nye struktur af BST efter sletning af 12.

1. Slet en node 12, der har to underordnede.
2. Sletningen af ​​noden vil ske baseret på In-Order Successor-reglen, hvilket betyder, at det mindste element i det højre undertræ af 12 vil erstatte den.
3. Slet knude 12 og erstat den med 19, da det er den mindste værdi i det højre undertræ.
4. Se den nye struktur af BST efter sletning af 12.

Kaldenavn Code til sletning af en node

delete (value, root):
    Node x = root
    Node y = NULL
    # searching the node
    while x:
        y = x
        if x.value < value
            x = x.right
        else if x.value > value
            x = x.left
        else if value == x
            break
    # if the node is not null, then replace it with successor
    if y.left or y.right:
        newNode = GetInOrderSuccessor(y)
        root.value = newNode.value
        # after copying the value of successor, delete the successor
        free(newNode)
    else
        free(y)

Vigtige vilkår

• Indsæt: Indsætter et element i et træ / opretter et træ.
• Søge: Søger efter et element i et træ.
• Forudbestillingsgennemgang: Krydser et træ på en forudbestilt måde.
• Inorder gennemkørsel: Krydser et træ på en rækkefølge.
• Postordre-gennemgang: Krydser et træ på en postordre måde.

Ofte Stillede Spørgsmål