Odstranění uzlu ze stromu AVL je podobné jako ve stromu binárního vyhledávání. Odstranění může narušit faktor rovnováhy stromu AVL, a proto je třeba strom znovu vyvážit, aby se zachovala hodnota AVL. Za tímto účelem musíme provést rotace. Dva typy rotace jsou L rotace a R rotace. Zde budeme diskutovat o rotacích R. L rotace jsou jejich zrcadlovým obrazem.

Pokud je uzel, který má být odstraněn, přítomen v levém podstromu kritického uzlu, pak je třeba použít L rotaci, jinak pokud je uzel, který má být odstraněn, přítomen v pravém podstromu kritického uzlu. , bude použita rotace R.

Uvažujme, že A je kritický uzel a B je kořenový uzel jeho levého podstromu. Pokud má být odstraněn uzel X, přítomný v pravém podstromu A, mohou nastat tři různé situace:

Rotace R0 (uzel B má faktor vyvážení 0)

Pokud má uzel B nulový faktor rovnováhy a faktor rovnováhy uzlu A se po vymazání uzlu X naruší, pak bude strom znovu vyvážen rotací stromu pomocí rotace R0.

Kritický uzel A se přesune doprava a uzel B se stane kořenem stromu s T1 jako jeho levým podstromem. Podstromy T2 a T3 se stanou levým a pravým podstromem uzlu A. proces zapojený do rotace R0 je znázorněn na následujícím obrázku.

Příklad:

Odstraňte uzel 30 ze stromu AVL zobrazeného na následujícím obrázku.

Řešení

V tomto případě má uzel B balanční faktor 0, proto se strom otočí pomocí rotace R0, jak je znázorněno na následujícím obrázku. Uzel B(10) se stane kořenem, zatímco uzel A se přesune doprava. Pravý potomek uzlu B se nyní stane levým potomkem uzlu A.

mapa v Javě

Rotace R1 (uzel B má faktor vyvážení 1)

Rotace R1 se má provést, pokud je součinitel rovnováhy uzlu B 1. Při rotaci R1 se kritický uzel A přesune doprava a má podstromy T2 a T3 jako levého a pravého potomka. T1 má být umístěn jako levý podstrom uzlu B.

Proces zapojený do rotace R1 je znázorněn na následujícím obrázku.

Příklad

Odstraňte uzel 55 ze stromu AVL zobrazeného na následujícím obrázku.

Řešení :

Vymazání 55 ze stromu AVL naruší faktor rovnováhy uzlu 50, tj. uzlu A, který se stane kritickým uzlem. Toto je podmínka rotace R1, ve které se uzel A posune doprava (zobrazeno na obrázku níže). Pravá část B se nyní stala levou od A (tj. 45).

Proces řešení je znázorněn na následujícím obrázku.

Rotace R-1 (uzel B má vyvážený faktor -1)

Rotace R-1 se má provést, pokud má uzel B balanční faktor -1. S tímto případem se zachází stejně jako s rotací LR. V tomto případě se uzel C, který je pravým potomkem uzlu B, stane kořenovým uzlem stromu s B a A jako jeho levým a pravým potomkem.

Podstromy T1, T2 se stanou levým a pravým podstromem B, zatímco T3, T4 se stanou levým a pravým podstromem A.

Proces rotace R-1 je znázorněn na následujícím obrázku.

Příklad

Odstraňte uzel 60 ze stromu AVL zobrazeného na následujícím obrázku.

srovnatelný seznam

Řešení:

v tomto případě má uzel B faktor rovnováhy -1. Vymazání uzlu 60 naruší vyvažovací faktor uzlu 50, proto je třeba jej otočit o R-1. Uzel C, tj. 45 se stane kořenem stromu s uzlem B(40) a A(50) jako jeho levým a pravým potomkem.