Mezgla dzēšana no AVL koka ir līdzīga kā binārā meklēšanas kokā. Dzēšana var izjaukt AVL koka līdzsvara faktoru, un tāpēc koks ir jālīdzsvaro, lai saglabātu AVL līmeni. Šim nolūkam mums ir jāveic rotācijas. Divi rotācijas veidi ir L rotācija un R rotācija. Šeit mēs apspriedīsim R rotācijas. L rotācijas ir to spoguļattēli.

Ja dzēšamais mezgls atrodas kritiskā mezgla kreisajā apakškokā, tad L rotācija ir jāpiemēro citādi, ja mezgls, kas jādzēš, atrodas kritiskā mezgla labajā apakškokā. , tiks piemērota R rotācija.

Uzskatīsim, ka A ir kritiskais mezgls un B ir tā kreisā apakškoka saknes mezgls. Ja mezgls X, kas atrodas A labajā apakškokā, ir jāizdzēš, var būt trīs dažādas situācijas:

R0 rotācija (mezglam B ir līdzsvara koeficients 0)

Ja mezglam B ir 0 līdzsvara koeficients un mezgla A līdzsvara koeficients tiek traucēts, dzēšot mezglu X, koks tiks līdzsvarots, rotējot koku, izmantojot R0 rotāciju.

Kritiskais mezgls A tiek pārvietots pa labi, un mezgls B kļūst par koka sakni ar T1 kā kreiso apakškoku. Apakškoki T2 un T3 kļūst par mezgla A kreiso un labo apakškoku. R0 rotācijā iesaistītais process ir parādīts nākamajā attēlā.

Piemērs:

Izdzēsiet mezglu 30 no AVL koka, kas parādīts nākamajā attēlā.

Risinājums

Šajā gadījumā mezglam B ir līdzsvara koeficients 0, tāpēc koks tiks pagriezts, izmantojot R0 rotāciju, kā parādīts nākamajā attēlā. Mezgls B(10) kļūst par sakni, bet mezgls A tiek pārvietots pa labi. Mezgla B labais bērns tagad kļūs par mezgla A kreiso bērnu.

Shilpa shetty vecums

R1 rotācija (mezglam B ir līdzsvara koeficients 1)

R1 Rotācija jāveic, ja mezgla B līdzsvara koeficients ir 1. R1 rotācijā kritiskais mezgls A tiek pārvietots pa labi ar apakškokiem T2 un T3 kā attiecīgi kreiso un labo atvasināto vietu. T1 ir jānovieto kā mezgla B kreisais apakškoks.

R1 rotācijas process ir parādīts nākamajā attēlā.

Piemērs

Izdzēsiet 55. mezglu no AVL koka, kas parādīts nākamajā attēlā.

Risinājums:

Dzēšot 55 no AVL koka, tiek traucēts mezgla 50 līdzsvara koeficients, t.i., mezgls A, kas kļūst par kritisko mezglu. Šis ir R1 rotācijas nosacījums, kurā mezgls A tiks pārvietots pa labi (parādīts zemāk esošajā attēlā). Labās puses no B tagad ir kļuvušas par kreiso no A (t.i., 45).

Risinājumā iesaistītais process ir parādīts nākamajā attēlā.

R-1 rotācija (mezglam B ir līdzsvara koeficients -1)

R-1 rotācija jāveic, ja mezglam B ir līdzsvara koeficients -1. Šis gadījums tiek apstrādāts tāpat kā LR rotācija. Šajā gadījumā mezgls C, kas ir mezgla B labais bērns, kļūst par koka saknes mezglu ar B un A attiecīgi kreiso un labo atvasi.

Apakškoki T1, T2 kļūst par B kreiso un labo apakškoku, savukārt T3, T4 kļūst par A kreiso un labo apakškoku.

R-1 rotācijas process ir parādīts nākamajā attēlā.

Piemērs

Izdzēsiet mezglu 60 no AVL koka, kas parādīts nākamajā attēlā.

mysql nav vienāds

Risinājums:

šajā gadījumā mezglam B ir līdzsvara koeficients -1. Dzēšot mezglu 60, tiek traucēts mezgla 50 līdzsvara koeficients, tāpēc tas ir jāpagriež R-1. Mezgls C, t.i., 45, kļūst par koka sakni ar mezglu B(40) un A(50) kā kreiso un labo atvasi.