Å slette en node fra et AVL-tre ligner på det i et binært søketre. Sletting kan forstyrre balansefaktoren til et AVL-tre, og derfor må treet rebalanseres for å opprettholde AVLness. For dette formålet må vi utføre rotasjoner. De to typene rotasjoner er L-rotasjon og R-rotasjon. Her vil vi diskutere R-rotasjoner. L-rotasjoner er speilbildene av dem.

Hvis noden som skal slettes er tilstede i det venstre undertreet til den kritiske noden, må L-rotasjon brukes ellers hvis noden som skal slettes er tilstede i det høyre undertreet til den kritiske noden , vil R-rotasjonen bli brukt.

La oss vurdere at A er den kritiske noden og B er rotnoden til dets venstre undertre. Hvis node X, tilstede i det høyre undertreet til A, skal slettes, kan det være tre forskjellige situasjoner:

R0-rotasjon (Node B har balansefaktor 0)

Hvis node B har 0 balansefaktor, og balansefaktoren til node A forstyrres ved sletting av node X, vil treet bli rebalansert ved å rotere tre ved å bruke R0 rotasjon.

Den kritiske noden A flyttes til høyre og noden B blir roten til treet med T1 som venstre undertre. Undertrærne T2 og T3 blir venstre og høyre undertre til noden A. prosessen involvert i R0-rotasjon er vist i det følgende bildet.

Eksempel:

Slett noden 30 fra AVL-treet vist i det følgende bildet.

Løsning

I dette tilfellet har noden B balansefaktor 0, derfor vil treet roteres ved å bruke R0-rotasjon som vist i følgende bilde. Noden B(10) blir roten, mens noden A flyttes til høyre. Det høyre barnet til node B vil nå bli det venstre barnet til node A.

legge til array java

R1 Rotasjon (Node B har balansefaktor 1)

R1-rotasjon skal utføres hvis balansefaktoren til node B er 1. I R1-rotasjon flyttes den kritiske noden A til høyre med undertrærne T2 og T3 som henholdsvis venstre og høyre barn. T1 skal plasseres som det venstre undertreet til noden B.

Prosessen involvert i R1-rotasjon er vist i bildet nedenfor.

Eksempel

Slett Node 55 fra AVL-treet vist i det følgende bildet.

Løsning :

Sletting av 55 fra AVL-treet forstyrrer balansefaktoren til noden 50, dvs. node A som blir den kritiske noden. Dette er tilstanden til R1-rotasjon der noden A flyttes til høyre (vist på bildet nedenfor). Høyre for B er nå blitt til venstre for A (dvs. 45).

Prosessen involvert i løsningen er vist i bildet nedenfor.

R-1 rotasjon (Node B har balansefaktor -1)

R-1 rotasjon skal utføres hvis noden B har balansefaktor -1. Denne saken behandles på samme måte som LR-rotasjon. I dette tilfellet blir noden C, som er det høyre barnet til node B, rotnoden til treet med B og A som henholdsvis venstre og høyre barn.

Undertrærne T1, T2 blir venstre og høyre undertrær til B, mens T3, T4 blir venstre og høyre undertrær til A.

123 film

Prosessen involvert i R-1-rotasjon er vist i følgende bilde.

Eksempel

Slett noden 60 fra AVL-treet vist i følgende bilde.

Løsning:

i dette tilfellet har node B balansefaktor -1. Sletting av noden 60 forstyrrer balansefaktoren til noden 50, derfor må den roteres R-1. Noden C, dvs. 45, blir roten til treet med noden B(40) og A(50) som venstre og høyre barn.