Drzewa AVL

Rysunki rozmaitych operacji na drzewach AVL, stworzone na I roku studiów, do tłumaczenia, żeby nie rzeba było ich za każdym razem rysować od nowa. Może się kiedyś jeszcze komuś przydarzą :)

Wstawianie:

...W budowie...

usuwanie:

Legenda:
Prostokąt - drzewo zrównoważone.
Kółko - Wierzchołek.
Liczby - wspołczynniki balansowania.
Stop - w tym momencie można zakonczyc balansowanie.
Dalej - w tym miejscu nalezy kontynuowac balansowanie na sciezce do korzenia.
Krzyzyk - w tym miejscu usuneliśmy liść, co spowodowało zmniejszenie wysokości w całym drzewie az do wierzcholka, ktory aktualnie rozpatrujemy.

usuwanie typu 1a (po powrocie z lewej) i 1b(po powrocie z prawej)> - BRAK ROTACJI

usuwanie typu 2a (po powrocie z lewej) i 2b(po powrocie z prawej) - BRAK ROTACJI

usuwanie typu 3a (po powrocie z lewej) i 3b(po powrocie z prawej) - ROTACJA POJEDYNCZA

usuwanie typu 4a (po powrocie z lewej) i 4b(po powrocie z prawej) - ROTACJA POJEDYNCZA

usuwanie typu 5a (po powrocie z lewej) i 5b(po powrocie z prawej) - ROTACJA PODWOJNA

Usuwanie - liście:

...W budowie...

uwaga - mozna bardzo latwo wyprowadzic wzorki z poprzednich rodzajow usuwania przyjmujac wysokosc drzewa pustego (NIL) jako 0.