Изтриването на възел от AVL дърво е подобно на това в двоично дърво за търсене. Изтриването може да наруши балансиращия фактор на AVL дърво и следователно дървото трябва да бъде балансирано отново, за да се поддържа AVLness. За целта трябва да извършваме ротации. Двата типа ротации са L ротация и R ротация. Тук ще обсъдим R ротации. L завъртания са техните огледални изображения.

Ако възелът, който трябва да бъде изтрит, присъства в лявото поддърво на критичния възел, тогава L ротацията трябва да се приложи иначе, ако възелът, който трябва да бъде изтрит, присъства в дясното поддърво на критичния възел , ще се приложи R ротацията.

Нека приемем, че A е критичният възел, а B е коренният възел на неговото ляво поддърво. Ако възел X, присъстващ в дясното поддърво на A, трябва да бъде изтрит, тогава може да има три различни ситуации:

R0 въртене (възел B има фактор на баланс 0)

Ако възел B има коефициент на баланс 0 и коефициентът на баланс на възел A е нарушен при изтриване на възел X, тогава дървото ще бъде балансирано отново чрез завъртане на дървото с помощта на ротация R0.

Критичният възел A се премества надясно и възелът B става корен на дървото с T1 като ляво поддърво. Поддърветата T2 и T3 се превръщат в ляво и дясно поддърво на възел A. Процесът, включен в ротацията на R0, е показан на следното изображение.

Пример:

Изтрийте възела 30 от AVL дървото, показано на следното изображение.

Решение

В този случай възелът B има коефициент на баланс 0, следователно дървото ще се завърти с помощта на ротация R0, както е показано на следващото изображение. Възелът B(10) става корен, докато възелът A се премества вдясно. Дясното дете на възел B сега ще стане ляво дете на възел A.

формат на низ

R1 Ротация (възел B има фактор на баланс 1)

Завъртането на R1 трябва да се извърши, ако коефициентът на баланс на възел B е 1. При въртенето на R1 критичният възел A се премества вдясно, като поддърветата T2 и T3 са съответно негово ляво и дясно дете. T1 трябва да бъде поставен като ляво поддърво на възел B.

Процесът, включен в въртенето на R1, е показан на следното изображение.

Пример

Изтрийте възел 55 от AVL дървото, показано на следното изображение.

char към низ

Решение :

Изтриването на 55 от AVL дървото нарушава балансиращия фактор на възел 50, т.е. възел А, който става критичен възел. Това е състоянието на въртене на R1, при което възелът A ще бъде преместен вдясно (показано на изображението по-долу). Дясното на B сега става ляво на A (т.е. 45).

Процесът, включен в решението, е показан на следното изображение.

R-1 Ротация (възел B има фактор на баланс -1)

Ротация R-1 трябва да се извърши, ако възелът B има фактор на баланс -1. Този случай се третира по същия начин като LR ротацията. В този случай възелът C, който е десният дъщерен възел на възел B, става кореновият възел на дървото с B и A съответно като ляво и дясно дете.

Поддърветата T1, T2 стават ляво и дясно поддървета на B, докато T3, T4 стават ляво и дясно поддървета на A.

Процесът, включен в въртенето на R-1, е показан на следното изображение.

Пример

Изтрийте възела 60 от AVL дървото, показано на следното изображение.

Решение:

в този случай възел B има фактор на баланс -1. Изтриването на възела 60 нарушава балансиращия фактор на възела 50, следователно той трябва да бъде завъртян R-1. Възелът C, т.е. 45, става корен на дървото с възел B(40) и A(50) като ляво и дясно дете.