Ostatnio mówiliśmy o drzewach czerowno czarnych. Dziś dokończymy ten temat, a mianowicie omówimy kilka rysunków ilustrujących usuwanie z drzew czerowono czarnych różnych elementów. I tak mamy rysunek pierwszy ilustrujący jakieś drzewo czerwono czarne. Drugi rysunek przedstawia to samo drzewo, ale z usuniętym węzłem z wartością 2:

Ponieważ usunięty węzeł był czerwony, własności drzewa czerwono czarnego nie uległy zmianie, więc korekta nie jest tu potrzebna i aby usunąć ten węzeł o wartości 2 wystarczy go usunąć, a w jego miejsce wkleić węzeł o wartości 4. A teraz kolejny przykład ilustrujący usunięcie węzła z wartością 7. Pierwszy rysunek przedstawia właściwe drzewo z węzłem 7, a kolejne ilustrują doprowadzanie drzewa do takiej postaci, by drzewo było drzewem czerwono czarnym. A więc:

1.
2.

3.
4.

Jak widać w drugim rysunku węzeł został usunięty zgodnie z procedurą dla drzewa BST. W kolejnych dwóch z kolei nastapiła rotacja S wokół P, oraz przekolorowanie S na czerwono i prawego nastepnika S oraz P na czarno. I teraz ostatni z przypadków. Należy usunąć węzeł z wartością 50, czyli korzeń. Pierwszy rysunek przedstawia drzewo czerowno czarne z węzłem 50, a drugi, trzeci i czwarty - operacje na tym drzewie:

Rysunek 1 i 2

Rysunek 3 i 4

Jak widać została tu wykonana rotacja S wokół P po usunięciu węzła, a następnie przekolorowanie S i P.

Podsumowując zagadnienie związane z drzewami czerwono czarnymi można powiedzieć, że drzewo czerwono czarne o n węzłach wewnętrznych ma wysokośc h spełniającą warunek, że
. Operacje takie, jak dodawanie, usuwanie, wyszukiwanie elementu, wyszukiwanie elementu najmniejszego / największego, wskazanie poprzednika / następnika danego elementu działają w czasie O(lg n). Przywracanie własności drzewa RB po dodaniu nowego węzła jest potrzebne tylko w sytuacji, gdy poprzednik dodanego węzła jest czerwony. Usunięcie węzła czerwonego nie zmienia własności drzewa RB (nie jest potrzebna korekta). Po usunięciu, lub dodaniu węzła z lub do drzewa RB wymagane sa (w ramach korekty) co najwyżej dwie rotacje. I to tyle jeśli chodzi o drzewa czerwono czarne.

Kolejnym tematem, jakim się dziś zajmiemy będzie temat związany z algorytmami sortowania wewnętrznego. Istnieją trzy podstawowe algorytmy sortowania. Jest to sortowanie przez wstawienie, przez wybieranie (selekcyjne) i przez zamianę (bąbelkowe). Mamy ponadto cztery efektywne algorytmy sortowania. Jest to sortowanie przez kopcowanie, metodą malejących przyrostów (Shella), szybkie, oraz przez scalenie. Załóżmy, że nasze klucze początkowe to będą: 44 55 12 42 94 18 06 67. Zobaczmy najpierw na schamacie, jak wygląda sortowanie przez wstawienie, oraz jak wygląda jego idea, oraz przykład takiego algorytmu w postaci pseudokodu:

A teraz spójrzmy na algorytm sortowania przez wybieranie:

Kolejny algorytm, to algorytm sortowania przez zamianę (bąbelkowe). Popatrzmy na jakiej zasadzie to sortowanie się odbywa:

Na koniec powiedzmy sobie o jednym z algorytmów efektywnych. Będzie to algorytm sortowania mieszanego. Popatrzmy na jego ilustrację i kod:

Teraz nieco o złożoności obliczeniowej algorytmów sortowania. Zacznijmy od sortowania przez wstawianie. Przy każdym algorytmie spotykamy się zawsze z trzema przypadkami, które zależą od danych wejściowych i od krórych zalezy szybkość wykonania. Jest to przypadek optymistyczny (najlepsze dane wejściowe z możliwych), przypadek pesymistyczny, oraz przypadek średni. Zacznijmy od optymistycznego. Wiedząc, że n to liczba elementów w tablicy, T z indeksem o to liczba porównań związanych z tablicą, oraz że T z indeksem R to liczba przypisań związanych z tablicą, przypadek optymistyczny tyczy się danych wejściowych już posortowanych i jest określany wzorami:

Przypadek pesymistyczny z kolei dotyczy przypadku, gdy dane wejściowe sa posortowane w odwrotnej kolejności. Wówczas przypadek pesymistyczny okreslamy wzorami:

I na koniec przypadek średni:

Tutaj n to ilośc elementów w tablicy, T z indeksem O to liczba porównań klucza, a T z indeksem R to liczba przesunięć elementów w tablicy.

Jeśli chodzi o algorytm sortowania przez wybieranie, to tutaj mamy taką sytuacje, że przypadek optymistyczny jest równy pesymiestycznemu, a to ozbacza, że jest też równy przypadkowi sredniemu. Wszystkie te trzy przypadki dla tego algorytmu określamy wzorami:

No i ostatni algorytm sortowania bąbelkowego. Wzór dla przypadku optymistycznego:

A oto przypadek pesymistyczny:

I przypadek średni:

Teraz z kolei przejdziemy do efektywnych algorytmów sortowania i je sobie omówimy. Stąd nazwa efektywne, bo wszystkie mają złożoność większą niż n do kwadratu. Na poczatek sortowanie przez kopcowanie. Jest ono udoskonaleniem sortowania drzewiastego, które wygląda tak:

Metodę sortowania drzewiastego udoskonalił w roku 1964 J. Williams. Samo sortowanie przez kopcowanie (udoskonalone drzewiaste) składa się z takich dwóch etapów. Najpierw tablicę A przetwarzamy na tablicę reprezentującą kopiec, a nastepnie w pętli od 0 do n-1 wywołujemy funkcję usuwania z kopca (tablicy A) elementu największego. Po wykonaniu ostatniego punktu tablica posortowana jest rosnąco. Przetwarzanie tablicy w kopiec odbywa się metodą wstępująca Floyda:

I teraz popatrzmy jak przykładowo wygląda działanie algorytmu sortowania przez kopcowanie dla tablicy [15 12 6 11 10 2 3 1 8]. Mamy nastepujące drzewo:

Przez cały algorytm przewijają się w kółko (dopóki tablica nie będzie posortowana) trzy kroki. Na początek następuje zamiana korzenia (15) z ostatnim elementem (najniżej i od prawej strony, czyli 8). Potem nastepuje zdjęcie z kopca elementu największego (15) i przywrócenie drzewu własności kopca. Oto idea algorytmu przez kopcowanie:

I jeszcze algorytm:

Analizując ta metodę można stwierdzić, że dla duzych n metoda ta jest bardzo efektywna, oraz że złożonośc czasowa algorytmu (nawet w najgorszym przypadku) wynosi tu
.

A teraz nieco słów o metodzie malejących przyrostów Shella. Podstawą działania algorytmu sortowania Shella jest dzielenie tablicy na podtablice, zawierające elementy oddalone od siebie o h pozycji. Oto idea tego algorytmu:

Sortowanie podtablic może być realizowane dowolną metodą sortowania (najczęściej wykorzystuje się tu sortowanie przez wstawianie). Tablica wyjściowa dzielona jest na
podtablic tworzonych co
-y element. Powstaje zatem
podtablic, przy czym dla każdej wartości h = 1, 2, …,
zachodzi:
. Przykładowo dla
tablica
zostanie podzielona na 3 podtablice: Tab1, Tab2, oraz Tab3 w nastepujący sposób:

Wszystkie podtablice sortowane są niezależnie, a nastepnie tworzone są nowe podtablice przy czym
. Oto jeszcze jeden przykład. Niech dana będzie tablica [5 3 6 7 2 1 9 4 8] i
. Wówczas Tab1 = [5 7 9], Tab2 = [3 2 4], Tab3 = [6 1 8]. Popatrzmy jeszcze na przykład sortowania metodą malejących przyrostów Shella z przyrostami 5, 3, 1:

Algorytm Shella ma jednak dwie cechy, które mogą ulegać zmienie w różnych implementacjach. Jest to sekwencja wartości przyrostów, oraz algorytm sortowania wykorzystywany do sortowania podtablic. Dobrym rozwiązaniem (wynikającym z praktyki) będzie tu wykorzystanie sekwencji przyrostówspełniających warunki:

oraz zakończeniem dzielenia tablicy na podtablice dla takiego
, dla którego cachodzi
. Przykładowo jeśli n równe jest 10 tysięcy, to wówczas sekwencja przyrostów ma postać
,

co znaczy
. O złożoności algorytmu decyduje
i sposób zmiany h.
oznacza zwykłe sortowanie.

A oto, jak wygląda cały algorytm sortowania metodą malejących przyrostów Shella:

---