Å 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.
