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.
