Dziś przejdziemy do tematu związanego z drzewami losowymi i drzepcami. O losowym drzewie BST o n wartościach mówimy, że jest to drzewo BST, które powstaje z drzewa pustego w wyniku wstawienia wartości (kluczy) w losowej kolejności przy założeniu, że każda z n! permutacji tych wartości jest jednakowo prawdopodobna. Można pokazać, że oczekiwana wartośc drzewa losowego BST o n kluczach wynosi
, czyli inaczej:
. Warto wiedzieć, że losowe drzewo BST ma tendencję bycia zrównoważonym. I teraz nieco o samym drzepcu. Drzepiec to drzewo BST, w którym porządek wstawiania elementów określany jest w pewien specjalny sposób. W każdym węźle drzepca oprócz pola wartości występuje pole prioryetet, którego wartością jest losowo określana liczba niezależnie dla każdego węzła (przy założeniu, że wszystkie wartości i wszystkie priorytety są różne. Elementy, czyli węzły w drzepcusa uporządkowane w taki sposób, że wartości (klucze) spełniają kryteria drzewa BST, natomiast priorytety spełniają własność kopca minimalnego, czyli z z najmniejszym priorytetem w korzeniu. Drzepiec jest więc połączeniem drzewa BST i kopca. Pomocne jest, aby mysleć o drzepcach w następujący sposób. Załóżmy, że wstawiamy do drzepca węzły
wraz ze związanymi z nimi wartościami (kluczami). Aby otrzymać drzepiec wstawiamy te węzły w kolejności wyznaczonej przez ich (losowo ustalone) prioytety, co znaczy, że
jest wstawiany przez
, jeżeli priorytet(
) < priorytet (
). No i popatrzmy na przykład takiego drzepca:

Zobaczmy teraz jak wygląda cała idea wstawiania węzła do drzepca:

I teraz przejdziemy do drzew silnie uporządkowanych. Jednym z takiech drzew jest drzewo AVL. Nazwa drzewa powstała od nazwisk Adelson - Velskii, Landis. Te osoby w 1962 stworzyli ten właśnie rodzaj drzewa. Drzewo AVL jest rozwinięciem drzewa BST z zachowaniem wszystkich jego własności, natomiast dla każdego wierzchołka w drzewie AVL wysokości jego dwóch poddrzew (lewego i prawego) o korzeniu w tym wierzchołku różnią się co najwyżej o 1. Węzeł oprócz pól danych oraz lewego i prawego wskaxnika ma też pole opisujące różnicę wysokości lewego i prawego poddrzewa. Z definicji wynika, że to pole może mieć wartości ze zbioru {-1, 0, 1}.

Zobaczmy teraz, jak się oblicza wagi wierzchołków tego drzewa. Dla każdego wierzchołka drzewa x współczynnik zrównoważenia w(x) ma postać:

, gdzie LD i PD sa odpowiednio lewym i prawym poddrzewem o korzeniu x. Drzewo BST jest drzewem AVL wtedy i tylko wtedy, gdy dla każdego wierzchołka x:
. Teraz jakie operacje możemy wykonywać na drzewie AVL. Na pewno możena dokonac wyszukiwania. Z kolei wiedząc, że drzewo AVL jest też drzewem BST, więc ta operacja wygląda tak, jak dla drzew BST. Kolejna operacja to wstawianie. Wstawianie polega tu na wyszukaniu miejsca w drzewie, a następnie wstawieniu elementu (tak, jak w BST). Ponieważ podczas tej operacji struktura drzewa zmienia się i może nie zostać zachowany warunek AVL (dotyczący róznicy w wysokości poddrzew) trzeba tę strukturę przywrócić. Wymagana jest więc takzwana rotacja. Na ponoższych rysunkach zostało przedstawione drzewo wyjściowe. Do niego dodajemy węzeł z wartością 3 i otrzymujemy drzewo z nowym węzłem:

No i kolej na usuwanie. Polega ono na wyszukaniu elementu w drzeiwe, a następnie jego usunięciu (tak, jak w BST). Z kolei tutaj może zajść potrzeba przywrócenia zrównoważonej struktury drzewa i tu wymagana jest rotacja. Rotacja polega na zmianie konfiguracji węzłów. Głównym celem jest tu przywrócenie struktury drzewa AVL. Wyróżniamy cztery rodzaje rotacji: lewe i prawe, oraz pojedyncze i podwójne. Natomiast nim omówimy te dwie pierwsze warto wspomnieć, że usunięcie elementu z drzewa AVL może zmniejszyć wysokośc tego poddrzewa i dlatego stosuje się tutaj rotację. Oto to samo drzewo, co wprzykładzie, ale już zrównoważone:

No i teraz omówmy lewą i prawą rotację. Lewa rotacja lub rotacja w lewo węzła y wokół węzła x polega na obrocie węzła y wokół wyróżnionego węzła x przeciwnie do ruchu wskazówek zegara. W wyniku rotacji węzeł staje się nowym korzeniem poddrzewa, a węzeł x staje się jego lewym synem. Z kolei lewy syn węzła y zostaje prawym synem węzła x. Taką rotację można wykonać jeżeli prawy syn węzła y nie jest NULL.

Prawa rotacja lub rotacja w prawo węzła x wokół węzła y polega na obrocie węzła x wokół wyróżnionego węzła y zgodnie z ruchem wskazówek zegara. W wyniku rotacji węzeł x staje się nowym korzeniem poddrzewa, a węzeł y staje się jego prawym synem. Z kolei prawy syn węzła x zostaje loewym synem węzła y. Taką rotację można wykonać jeżeli lewy syn węzła x nie jest NULL. I na razie na tym skończymy wykład.

---