Brisanje vozlišča iz drevesa AVL je podobno kot v binarnem iskalnem drevesu. Izbris lahko zmoti faktor ravnotežja drevesa AVL, zato je treba drevo ponovno uravnotežiti, da se ohrani AVLness. V ta namen moramo izvajati rotacije. Dve vrsti rotacije sta L rotacija in R rotacija. Tukaj bomo razpravljali o rotacijah R. L rotacije so njihove zrcalne slike.

Če je vozlišče, ki ga je treba izbrisati, prisotno v levem poddrevesu kritičnega vozlišča, potem je treba uporabiti rotacijo L drugače, če je vozlišče, ki ga je treba izbrisati, prisotno v desnem poddrevesu kritičnega vozlišča. , bo uporabljena rotacija R.

Upoštevajmo, da je A kritično vozlišče, B pa korensko vozlišče njegovega levega poddrevesa. Če je treba vozlišče X, ki je prisotno v desnem poddrevesu A, izbrisati, potem lahko pride do treh različnih situacij:

Rotacija R0 (vozlišče B ima faktor ravnovesja 0)

Če ima vozlišče B faktor ravnotežja 0 in je faktor ravnotežja vozlišča A moten ob izbrisu vozlišča X, bo drevo ponovno uravnoteženo z vrtenjem drevesa z uporabo rotacije R0.

Kritično vozlišče A se premakne v desno in vozlišče B postane koren drevesa s T1 kot levim poddrevesom. Poddrevesi T2 in T3 postaneta levo in desno poddrevo vozlišča A. Postopek, vključen v rotacijo R0, je prikazan na naslednji sliki.

primer:

Izbrišite vozlišče 30 iz drevesa AVL, prikazanega na naslednji sliki.

rešitev

V tem primeru ima vozlišče B faktor ravnotežja 0, zato bo drevo zasukano z uporabo rotacije R0, kot je prikazano na naslednji sliki. Vozlišče B(10) postane koren, medtem ko se vozlišče A premakne v desno. Desni otrok vozlišča B bo zdaj postal levi otrok vozlišča A.

Vrtenje R1 (vozlišče B ima faktor ravnovesja 1)

Rotacijo R1 je treba izvesti, če je faktor ravnovesja vozlišča B 1. Pri rotaciji R1 se kritično vozlišče A premakne v desno in ima poddrevesi T2 in T3 kot svojega levega oziroma desnega otroka. T1 je treba postaviti kot levo poddrevo vozlišča B.

Postopek, vključen v rotacijo R1, je prikazan na naslednji sliki.

Primer

Izbrišite vozlišče 55 iz drevesa AVL, prikazanega na naslednji sliki.

rešitev:

Brisanje 55 iz drevesa AVL poruši faktor ravnovesja vozlišča 50, tj. vozlišča A, ki postane kritično vozlišče. To je pogoj rotacije R1, v katerem bo vozlišče A premaknjeno v desno (prikazano na spodnji sliki). Desna od B je zdaj postala leva od A (tj. 45).

Postopek, vključen v rešitev, je prikazan na naslednji sliki.

Vrtenje R-1 (vozlišče B ima faktor ravnotežja -1)

Rotacijo R-1 je treba izvesti, če ima vozlišče B faktor ravnotežja -1. Ta primer obravnavamo na enak način kot rotacijo LR. V tem primeru vozlišče C, ki je desni otrok vozlišča B, postane korensko vozlišče drevesa z B in A kot njegovim levim oziroma desnim otrokom.

Poddrevesa T1, T2 postaneta levo in desno poddrevo drevesa B, medtem ko T3, T4 postaneta levo in desno poddreveso drevesa A.

Postopek, vključen v rotacijo R-1, je prikazan na naslednji sliki.

Primer

Izbrišite vozlišče 60 iz drevesa AVL, prikazanega na naslednji sliki.

rešitev:

v tem primeru ima vozlišče B faktor ravnotežja -1. Brisanje vozlišča 60 moti faktor ravnovesja vozlišča 50, zato ga je treba zavrteti R-1. Vozlišče C, tj. 45, postane koren drevesa z vozliščema B(40) in A(50) kot njegovim levim in desnim otrokom.