Solmun poistaminen AVL-puusta on samanlaista kuin binäärihakupuussa. Poistaminen voi häiritä AVL-puun tasapainokerrointa ja siksi puu on tasapainotettava uudelleen AVL-arvon säilyttämiseksi. Tätä tarkoitusta varten meidän on suoritettava kiertoja. Kaksi kiertotyyppiä ovat L-kierto ja R-kierto. Täällä keskustelemme R-kierroksista. L-kierrokset ovat niiden peilikuvia.
Jos poistettava solmu on kriittisen solmun vasemmassa alipuussa, L-kiertoa on käytettävä muussa tapauksessa, jos poistettava solmu on kriittisen solmun oikeanpuoleisessa alipuussa. , R-kiertoa käytetään.
Otetaan, että A on kriittinen solmu ja B on sen vasemman alipuun juurisolmu. Jos A:n oikeanpuoleisessa alipuussa oleva solmu X poistetaan, voi olla kolme erilaista tilannetta:
R0-kierto (solmun B tasapainokerroin 0)
Jos solmun B tasapainokerroin on 0 ja solmun A tasapainokerroin häiriintyy poistettaessa solmu X, niin puu tasapainotetaan uudelleen pyörittämällä puuta käyttämällä R0-kiertoa.
Kriittinen solmu A siirretään sen oikealle puolelle ja solmusta B tulee puun juuri ja T1 vasen alipuu. Osapuista T2 ja T3 tulee solmun A vasen ja oikea alipuu. R0-kiertoon liittyvä prosessi on esitetty seuraavassa kuvassa.
Esimerkki:
Poista solmu 30 seuraavassa kuvassa näkyvästä AVL-puusta.
Ratkaisu
Tässä tapauksessa solmun B tasapainokerroin 0, joten puuta pyöritetään käyttämällä R0-kiertoa seuraavan kuvan mukaisesti. Solmusta B(10) tulee juuri, kun taas solmu A siirretään sen oikealle puolelle. Solmun B oikeasta lapsesta tulee nyt solmun A vasen lapsi.
java-arvo enum
R1-kierto (solmun B tasapainokerroin 1)
R1 Rotaatio on suoritettava, jos solmun B tasapainokerroin on 1. R1-rotaatiossa kriittinen solmu A siirretään oikealle, jolloin alipuut T2 ja T3 ovat vasen ja oikea lapsi. T1 tulee sijoittaa solmun B vasemmaksi alipuuksi.
R1-kiertoon liittyvä prosessi on esitetty seuraavassa kuvassa.
Esimerkki
Poista solmu 55 seuraavassa kuvassa näkyvästä AVL-puusta.
vain nimimerkki
Ratkaisu :
55:n poistaminen AVL-puusta häiritsee solmun 50 tasapainokerrointa eli solmun A, josta tulee kriittinen solmu. Tämä on R1-kierron ehto, jossa solmu A siirretään oikealle (näkyy alla olevassa kuvassa). B:n oikeasta on nyt tullut A:n vasen (eli 45).
Ratkaisuun liittyvä prosessi on esitetty seuraavassa kuvassa.
R-1-kierto (solmun B tasapainokerroin -1)
R-1-kierto on suoritettava, jos solmulla B on tasapainokerroin -1. Tätä tapausta käsitellään samalla tavalla kuin LR-kiertoa. Tässä tapauksessa solmusta C, joka on solmun B oikea lapsi, tulee puun juurisolmu, jonka vasen ja oikea lapsi on B ja A.
Osapuista T1, T2 tulee B:n vasen ja oikea alipuu, kun taas T3, T4 tulevat A:n vasemmaksi ja oikeaksi alipuuksi.
R-1-kiertoon liittyvä prosessi on esitetty seuraavassa kuvassa.
Esimerkki
Poista solmu 60 seuraavassa kuvassa näkyvästä AVL-puusta.
Ratkaisu:
tässä tapauksessa solmun B tasapainokerroin -1. Solmun 60 poistaminen häiritsee solmun 50 tasapainokerrointa, joten sitä on käännettävä R-1. Solmusta C eli 45 tulee puun juuri ja solmu B(40) ja A(50) ovat sen vasen ja oikea lapsi.
