Sletning af en node fra et AVL-træ ligner det i et binært søgetræ. Sletning kan forstyrre balancefaktoren for et AVL-træ, og træet skal derfor rebalanceres for at opretholde AVLness. Til dette formål skal vi udføre rotationer. De to typer rotationer er L-rotation og R-rotation. Her vil vi diskutere R-rotationer. L rotationer er spejlbillederne af dem.
Hvis knudepunktet, der skal slettes, er til stede i venstre undertræ af den kritiske knude, så skal L-rotation anvendes ellers, hvis knudepunktet, som skal slettes, er til stede i det højre undertræ af den kritiske knude , vil R-rotationen blive anvendt.
Lad os overveje, at A er den kritiske knude, og B er rodknuden i dets venstre undertræ. Hvis node X, der findes i det højre undertræ af A, skal slettes, kan der være tre forskellige situationer:
R0 rotation (Knudepunkt B har balancefaktor 0)
Hvis knudepunktet B har 0 balancefaktor, og balancefaktoren for knudepunkt A forstyrres ved sletning af knudepunktet X, vil træet blive rebalanceret ved at rotere træ ved hjælp af R0 rotation.
Den kritiske knude A flyttes til højre, og knudepunktet B bliver træets rod med T1 som venstre undertræ. Undertræerne T2 og T3 bliver venstre og højre undertræ af knudepunktet A. processen involveret i R0 rotation er vist i det følgende billede.
Eksempel:
Slet noden 30 fra AVL-træet vist i det følgende billede.
Løsning
I dette tilfælde har knudepunktet B balancefaktor 0, derfor vil træet blive roteret ved at bruge R0-rotation som vist i det følgende billede. Noden B(10) bliver roden, mens noden A flyttes til højre. Det højre barn af node B bliver nu det venstre barn af node A.
tilføjelse til array java
R1 Rotation (Node B har balancefaktor 1)
R1 Rotation skal udføres, hvis balancefaktoren for Node B er 1. I R1 rotation flyttes den kritiske node A til højre med undertræerne T2 og T3 som henholdsvis venstre og højre underordnede. T1 skal placeres som venstre undertræ i knudepunktet B.
Processen involveret i R1-rotation er vist på det følgende billede.
Eksempel
Slet Node 55 fra AVL-træet vist i det følgende billede.
Løsning :
Sletning af 55 fra AVL-træet forstyrrer balancefaktoren for knudepunktet 50, dvs. knudepunkt A, som bliver den kritiske knude. Dette er tilstanden for R1-rotation, hvor knudepunktet A vil blive flyttet til højre (vist på billedet nedenfor). Højre for B er nu blevet til venstre for A (dvs. 45).
Processen involveret i løsningen er vist på det følgende billede.
R-1 rotation (knude B har balancefaktor -1)
R-1 rotation skal udføres, hvis knudepunktet B har balancefaktor -1. Dette tilfælde behandles på samme måde som LR-rotation. I dette tilfælde bliver knudepunktet C, som er det højre underordnede af knudepunkt B, træets rodknudepunkt med B og A som henholdsvis venstre og højre underordnede.
Undertræerne T1, T2 bliver venstre og højre undertræer af B, mens T3, T4 bliver venstre og højre undertræer af A.
123 film
Processen involveret i R-1 rotation er vist på det følgende billede.
Eksempel
Slet noden 60 fra AVL-træet vist i det følgende billede.
Løsning:
i dette tilfælde har node B balancefaktor -1. Sletning af knudepunktet 60 forstyrrer balancefaktoren for knudepunktet 50, derfor skal det roteres R-1. Noden C, dvs. 45, bliver træets rod med knudepunktet B(40) og A(50) som venstre og højre underordnede.
