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

Attributter af binært søgetræ

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

• Træets noder er repræsenteret i et forældre-barn-forhold
• 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 knudepunkter, der er til stede i det venstre undertræ, er mindre end nøglerne til deres overordnede knude
• På samme måde har nøglerne til venstre undertræsknudepunkt mindre værdier end deres overordnede nodes nøgler.

1. Der er hovedknuden 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 node
3. Det venstre undertræ har værdier end den overordnede node

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

• De to vigtigste faktorer, der gør binært søgetræ til en optimal løsning på alle problemer i den virkelige verden, 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 efter, er større eller mindre end den overordnede node, ved noden, hvilken træside den skal søge 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 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æerne er fulde af sidste niveaus mulige undtagelser. På samme måde er alle noder fulde, og dirigerer yderst til venstre.
• Fuldt binært træ: Alle noder har 2 underordnede noder undtagen bladet.
• Balanceret eller perfekt binært træ: I træet har alle noderne to børn. Desuden er der det 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ænger af det element, der skal indsættes, søges eller slettes, efter sammenligningen kan algoritmen nemt slippe venstre eller højre undertræ af rodnoden.

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

• Søg: søger efter 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 Slet-operationen.

Søg Operation

Start altid analysetræet ved rodknuden og flyt derefter længere til enten højre eller venstre undertræ af rodknuden afhængigt af, at det element, der skal lokaliseres, enten er mindre eller større end roden.

1. Elementet, der skal søges i, er 10
2. Sammenlign elementet med rodnoden 12, 10 < 12, så du flytter til 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 højre undertræ
4. Sammenlign derefter 10 med den næste node, som er 9, 10 > 9, kig i det højre undertræsbarn
5. 10 matcher med værdien i noden, 10 = 10, returnerer værdien til brugeren.

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

1. Der er en liste over 6 elementer, der skal indsættes i en BST i rækkefølge fra venstre mod højre
2. Indsæt 12 som rodknudepunktet og sammenlign næste værdier 7 og 9 for at indsætte tilsvarende i højre og venstre undertræ
3. Sammenlign de resterende værdier 19, 5 og 10 med rodnoden 12 og placer dem i overensstemmelse hermed. 19 > 12 placer det som højre barn af 12, 5 < 12 & 5 < 7, og placer det som venstre barn af 7. Sammenlign nu 10, 10 er < 12 & 10 er > 7 & 10 er > 9, plads 10 som 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

For sletning af en node fra en BST er der nogle tilfælde, dvs. sletning af en rod eller sletning af en bladnode. Efter sletning af 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- Node med nul børn: dette er den nemmeste situation, du skal bare slette den node, der ikke har flere børn til højre eller venstre.
• Tilfælde 2 – Node med et 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 Node 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 på venstre undertræ af den slettede node
• 3b – I rækkefølge efterfølger: du skal slette noden med to børn og erstatte den med den største værdi på 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 børn. Som du kan se på 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 af 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, at 9 har et barn.
2. Slet noden 9 og erstat den med dens underordnede 10 og tilføj et link fra 7 til 10
3. Se den nye struktur af BST uden 9

1. Her vil du slette node 12, der har to børn
2. 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.
3. Slet noden 12 og erstat den med 10, da det er den største værdi på venstre undertræ
4. Se den nye struktur for BST efter sletning af 12

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

Pseudokode 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 to the root #we're deleting the successor
    	free(newNode)
    else
    	free(y)

Vigtige vilkår

• Indsæt: Indsætter et element i et træ/opretter et træ.
• Søg: Søger efter et element i et træ.
• Preorder Traversal: Gennemløber et træ på en forudbestillingsmåde.
• Inorder Traversal: Traverserer et træ på en i orden.
• Postordre-gennemgang: Går gennem et træ på en postordre-måde.

Resumé

• BST er en algoritme på avanceret niveau, der udfører forskellige operationer baseret på sammenligning af nodeværdier med rodnoden.
• Ethvert af punkterne i et overordnet-underordnet hierarki repræsenterer noden. Mindst én forælder eller rodnode forbliver til stede hele tiden.
• Der er et venstre undertræ og et højre undertræ. Det venstre undertræ indeholder værdier, der er mindre end rodnoden. Det højre undertræ indeholder dog en værdi, der er større end rodnoden.
• Hver node kan have enten nul, et eller to børn.
• Et binært søgetræ letter primære operationer som at søge, indsætte og slette.
• Slet som den mest komplekse har flere tilfælde, for eksempel en node uden underordnede, knude med et underordnet og knude med to underordnede.
• Algoritmen bruges i virkelige løsninger som spil, autofuldførelsesdata og grafik.