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.