Mazgo ištrynimas iš AVL medžio yra panašus į dvejetainio paieškos medžio pašalinimą. Ištrynimas gali sutrikdyti AVL medžio balanso koeficientą, todėl norint išlaikyti AVL lygį, medį reikia iš naujo subalansuoti. Šiuo tikslu turime atlikti sukimus. Dviejų tipų sukimas yra L sukimasis ir R pasukimas. Čia aptarsime R sukimus. L sukimai yra veidrodiniai jų vaizdai.

Jei mazgas, kurį reikia ištrinti, yra kairiajame kritinio mazgo antriniame medyje, tada L sukimas turi būti taikomas kitu atveju, jei mazgas, kurį reikia ištrinti, yra kritinio mazgo dešiniajame antriniame medyje. , bus taikomas R pasukimas.

Apsvarstykime, kad A yra kritinis mazgas, o B yra jo kairiojo pomedžio šakninis mazgas. Jei mazgas X, esantis dešiniajame A antriniame medyje, turi būti ištrintas, gali būti trys skirtingos situacijos:

R0 sukimasis (mazgas B turi balanso koeficientą 0)

Jei mazgo B balanso koeficientas yra 0, o mazgo A balanso koeficientas sutrinka ištrynus mazgą X, tada medis bus subalansuotas sukant medį naudojant R0 sukimą.

Kritinis mazgas A perkeliamas į dešinę, o mazgas B tampa medžio šaknimis, o T1 yra kairysis pomedis. Medžiai T2 ir T3 tampa kairiuoju ir dešiniuoju mazgo A pomedžiu. R0 sukimosi procesas parodytas sekančiame paveikslėlyje.

Pavyzdys:

Ištrinkite 30 mazgą iš AVL medžio, parodyto kitame paveikslėlyje.

Sprendimas

Šiuo atveju mazgas B turi balanso koeficientą 0, todėl medis bus pasuktas naudojant R0 pasukimą, kaip parodyta kitame paveikslėlyje. Mazgas B(10) tampa šaknimis, o mazgas A perkeliamas į dešinę. Dešinysis mazgo B vaikas dabar taps kairiuoju mazgo A vaikas.

bash suskaidyta eilutė pagal skyriklį

R1 sukimasis (mazgas B turi balanso koeficientą 1)

R1 Rotacija turi būti atliekama, jei mazgo B balanso koeficientas yra 1. Sukant R1, kritinis mazgas A perkeliamas į dešinę, o pomedžiai T2 ir T3 yra atitinkamai kairysis ir dešinysis antrinis. T1 turi būti dedamas kaip kairysis mazgo B pomedis.

Procesas, susijęs su R1 sukimu, parodytas kitame paveikslėlyje.

Pavyzdys

Ištrinkite 55 mazgą iš AVL medžio, parodyto kitame paveikslėlyje.

alfa beta genėjimas

Sprendimas:

Ištrynus 55 iš AVL medžio, pažeidžiamas mazgo 50 balanso koeficientas, ty mazgo A, kuris tampa kritiniu mazgu. Tai R1 sukimosi sąlyga, kai mazgas A bus perkeltas į dešinę (parodyta paveikslėlyje žemiau). B dešinė dabar tapo A kairiąja (ty 45).

Procesas, susijęs su sprendimu, parodytas toliau pateiktame paveikslėlyje.

R-1 sukimasis (mazgas B turi balanso koeficientą -1)

R-1 sukimas turi būti atliekamas, jei mazgas B turi balanso koeficientą -1. Šis atvejis traktuojamas taip pat, kaip ir LR sukimas. Šiuo atveju mazgas C, kuris yra dešinysis mazgo B vaikas, tampa šakniniu medžio mazgu, o B ir A atitinkamai yra kairioji ir dešinioji.

Medžiai T1, T2 tampa kairiuoju ir dešiniuoju B pomedžiu, o T3, T4 tampa kairiuoju ir dešiniuoju A medžiu.

Procesas, susijęs su R-1 sukimu, parodytas kitame paveikslėlyje.

Pavyzdys

Ištrinkite mazgą 60 iš AVL medžio, parodyto kitame paveikslėlyje.

Sprendimas:

šiuo atveju mazgas B turi balanso koeficientą -1. Ištrynus mazgą 60, sutrinka mazgo 50 balanso koeficientas, todėl jį reikia pasukti R-1. Mazgas C, ty 45, tampa medžio šaknimi, o mazgas B(40) ir A(50) yra jo kairysis ir dešinysis vaikas.