Att ta bort en nod från ett AVL-träd liknar det i ett binärt sökträd. Radering kan störa balansfaktorn för ett AVL-träd och därför måste trädet balanseras om för att bibehålla AVLness. För detta ändamål måste vi utföra rotationer. De två typerna av rotationer är L-rotation och R-rotation. Här kommer vi att diskutera R-rotationer. L-rotationer är spegelbilderna av dem.
Om noden som ska raderas finns i det vänstra underträdet av den kritiska noden, måste L-rotation tillämpas annars om noden som ska raderas finns i det högra underträdet av den kritiska noden , kommer R-rotationen att tillämpas.
Låt oss tänka på att A är den kritiska noden och B är rotnoden till dess vänstra underträd. Om nod X, som finns i det högra underträdet av A, ska raderas, kan det finnas tre olika situationer:
R0-rotation (nod B har balansfaktor 0)
Om nod B har 0 balansfaktor, och balansfaktorn för nod A störs vid radering av nod X, kommer trädet att ombalanseras genom att rotera trädet med användning av R0-rotation.
Den kritiska noden A flyttas till höger och noden B blir trädets rot med T1 som vänster underträd. Underträden T2 och T3 blir det vänstra och högra underträdet för noden A. processen involverad i R0-rotation visas i följande bild.
Exempel:
Ta bort noden 30 från AVL-trädet som visas i följande bild.
Lösning
I det här fallet har noden B balansfaktor 0, därför kommer trädet att roteras genom att använda R0-rotation som visas i följande bild. Noden B(10) blir roten, medan noden A flyttas åt höger. Det högra barnet i nod B kommer nu att bli det vänstra barnet i nod A.
pandas standardavvikelse
R1 Rotation (nod B har balansfaktor 1)
R1-rotation ska utföras om balansfaktorn för Nod B är 1. Vid R1-rotation flyttas den kritiska noden A till höger med underträden T2 och T3 som sitt vänstra respektive högra barn. T1 ska placeras som det vänstra underträdet för noden B.
Processen involverad i R1-rotation visas i följande bild.
Exempel
Ta bort nod 55 från AVL-trädet som visas i följande bild.
Lösning:
Att ta bort 55 från AVL-trädet stör balansfaktorn för noden 50, dvs nod A som blir den kritiska noden. Detta är tillståndet för R1-rotation där noden A kommer att flyttas till höger (visas i bilden nedan). Högern om B har nu blivit vänster om A (dvs. 45).
Processen involverad i lösningen visas i följande bild.
R-1 rotation (nod B har balansfaktor -1)
R-1-rotation ska utföras om noden B har balansfaktor -1. Detta fall behandlas på samma sätt som LR-rotation. I det här fallet blir noden C, som är det högra barnet till nod B, trädets rotnod med B och A som dess vänstra respektive högra barn.
Underträden T1, T2 blir vänster och höger underträd av B medan T3, T4 blir vänster och höger underträd av A.
java heltal till sträng
Processen involverad i R-1-rotation visas i följande bild.
Exempel
Ta bort noden 60 från AVL-trädet som visas i följande bild.
Lösning:
i detta fall har nod B balansfaktor -1. Att ta bort noden 60, stör noden 50:s balansfaktor, därför måste den roteras R-1. Noden C, dvs. 45, blir trädets rot med noden B(40) och A(50) som dess vänstra och högra barn.
