Brisanje čvora iz AVL stabla slično je onom u stablu binarnog pretraživanja. Brisanje može poremetiti faktor ravnoteže AVL stabla i stoga se stablo treba ponovno uravnotežiti kako bi se održala AVLness. U tu svrhu moramo izvoditi rotacije. Dvije vrste rotacije su L rotacija i R rotacija. Ovdje ćemo raspravljati o R rotacijama. L rotacije su njihove zrcalne slike.
Ako je čvor koji se želi obrisati prisutan u lijevom podstablu kritičnog čvora, tada je potrebno primijeniti L rotaciju inače ako je čvor koji se želi obrisati prisutan u desnom podstablu kritičnog čvora. , primijenit će se R rotacija.
Uzmimo u obzir da je A kritični čvor, a B korijenski čvor njegovog lijevog podstabla. Ako čvor X, prisutan u desnom podstablu od A, treba izbrisati, tada mogu postojati tri različite situacije:
R0 rotacija (čvor B ima faktor ravnoteže 0)
Ako čvor B ima faktor ravnoteže 0, a faktor ravnoteže čvora A poremećen nakon brisanja čvora X, tada će stablo biti ponovno uravnoteženo rotiranjem stabla pomoću R0 rotacije.
Kritični čvor A pomiče se udesno, a čvor B postaje korijen stabla s T1 kao lijevim podstablom. Podstabla T2 i T3 postaju lijevo i desno podstablo čvora A. Proces uključen u rotaciju R0 prikazan je na sljedećoj slici.
Primjer:
Izbrišite čvor 30 iz AVL stabla prikazanog na sljedećoj slici.
Riješenje
U ovom slučaju, čvor B ima faktor ravnoteže 0, stoga će stablo biti rotirano pomoću R0 rotacije kao što je prikazano na sljedećoj slici. Čvor B(10) postaje korijen, dok se čvor A pomiče udesno. Desno dijete čvora B sada će postati lijevo dijete čvora A.
numpy jedinstven
R1 rotacija (čvor B ima faktor ravnoteže 1)
R1 rotacija se mora izvršiti ako je faktor ravnoteže čvora B 1. U R1 rotaciji, kritični čvor A se pomiče udesno s podstablima T2 i T3 kao svojim lijevi i desni potomak. T1 treba postaviti kao lijevo podstablo čvora B.
Proces uključen u rotaciju R1 prikazan je na sljedećoj slici.
Primjer
Izbrišite čvor 55 iz AVL stabla prikazanog na sljedećoj slici.
Riješenje :
Brisanje 55 iz AVL stabla remeti faktor ravnoteže čvora 50, tj. čvora A koji postaje kritični čvor. Ovo je stanje R1 rotacije u kojem će se čvor A pomaknuti udesno (prikazano na slici ispod). Desno od B sada postaje lijevo od A (tj. 45).
Proces uključen u rješenje prikazan je na sljedećoj slici.
mreže i vrste mreža
R-1 rotacija (čvor B ima faktor ravnoteže -1)
R-1 rotaciju treba izvesti ako čvor B ima faktor ravnoteže -1. Ovaj slučaj se tretira na isti način kao LR rotacija. U ovom slučaju, čvor C, koji je desno dijete čvora B, postaje korijenski čvor stabla s B i A kao njegovim lijevim i desnim potomcima.
Podstabla T1, T2 postaju lijevo i desno podstablo B, dok T3, T4 postaju lijevo i desno podstablo A.
Proces uključen u rotaciju R-1 prikazan je na sljedećoj slici.
Primjer
Izbrišite čvor 60 iz AVL stabla prikazanog na sljedećoj slici.
Riješenje:
u ovom slučaju, čvor B ima faktor ravnoteže -1. Brisanje čvora 60 remeti faktor ravnoteže čvora 50 stoga ga je potrebno rotirati R-1. Čvor C, tj. 45 postaje korijen stabla s čvorom B(40) i A(50) kao njegovim lijevim i desnim djetetom.
