Ștergerea unui nod dintr-un arbore AVL este similară cu cea dintr-un arbore de căutare binar. Ștergerea poate perturba factorul de echilibru al unui arbore AVL și, prin urmare, arborele trebuie reechilibrat pentru a menține caracterul AVL. În acest scop, trebuie să efectuăm rotații. Cele două tipuri de rotații sunt rotația L și rotația R. Aici vom discuta despre rotațiile R. Rotațiile L sunt imaginile în oglindă ale acestora.
Dacă nodul care urmează să fie șters este prezent în subarborele din stânga al nodului critic, atunci rotația L trebuie aplicată altfel dacă nodul care urmează să fie șters este prezent în subarborele din dreapta al nodului critic. , se va aplica rotația R.
Să considerăm că, A este nodul critic și B este nodul rădăcină al sub-arborelui său din stânga. Dacă nodul X, prezent în sub-arborele din dreapta al lui A, urmează să fie șters, atunci pot exista trei situații diferite:
Rotația R0 (Nodul B are factor de echilibru 0)
Dacă nodul B are 0 factor de echilibru, iar factorul de echilibru al nodului A este perturbat la ștergerea nodului X, atunci arborele va fi reechilibrat prin rotirea arborelui folosind rotația R0.
Nodul critic A este mutat la dreapta și nodul B devine rădăcina arborelui cu T1 ca subarborele stâng. Subarborele T2 și T3 devine subarborele din stânga și din dreapta nodului A. procesul implicat în rotația R0 este prezentat în imaginea următoare.
Exemplu:
Ștergeți nodul 30 din arborele AVL prezentat în imaginea următoare.
Soluţie
În acest caz, nodul B are factor de echilibru 0, prin urmare arborele va fi rotit utilizând rotația R0 așa cum se arată în imaginea următoare. Nodul B(10) devine rădăcină, în timp ce nodul A este mutat la dreapta sa. Fiul din dreapta al nodului B va deveni acum copilul din stânga al nodului A.
recursiunea în java
Rotație R1 (Nodul B are factor de echilibru 1)
Rotația R1 trebuie efectuată dacă factorul de echilibru al Nodului B este 1. În rotația R1, nodul critic A este mutat la dreapta, având sub-arborele T2 și T3 drept copil stâng și, respectiv, drept. T1 trebuie plasat ca sub-arborele din stânga al nodului B.
Procesul implicat în rotația R1 este prezentat în imaginea următoare.
Exemplu
Ștergeți Nodul 55 din arborele AVL prezentat în imaginea următoare.
Solutie:
Ștergerea 55 din arborele AVL perturbă factorul de echilibru al nodului 50, adică nodul A care devine nodul critic. Aceasta este condiția de rotație a R1 în care, nodul A va fi mutat la dreapta sa (prezentat în imaginea de mai jos). Dreapta lui B devine acum stânga lui A (adică 45).
Procesul implicat în soluție este prezentat în imaginea următoare.
Rotație R-1 (Nodul B are factor de echilibru -1)
Rotația R-1 trebuie efectuată dacă nodul B are factor de echilibru -1. Acest caz este tratat în același mod ca și rotația LR. În acest caz, nodul C, care este copilul drept al nodului B, devine nodul rădăcină al arborelui cu B și A drept copii stângi și, respectiv, drept.
Sub-arborele T1, T2 devin sub-arborele din stânga și din dreapta lui B, în timp ce, T3, T4 devin sub-arborele din stânga și din dreapta lui A.
Procesul implicat în rotația R-1 este prezentat în imaginea următoare.
Exemplu
Ștergeți nodul 60 din arborele AVL prezentat în imaginea următoare.
arp o comandă
Soluţie:
în acest caz, nodul B are factor de echilibru -1. Ștergerea nodului 60 deranjează factorul de echilibru al nodului 50, prin urmare, acesta trebuie rotit R-1. Nodul C, adică 45 devine rădăcina arborelui cu nodul B(40) și A(50) drept copil stâng și drept.
