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.
ups koncepti
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.
java naključno število
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.
