1. Kopce binarne:
   • Sposób organizacji danych.
   • Implementacja tablicowa kopca.
   • Operacje na kopcu:
     • Wstawianie elementu.
     • Usuwanie elementu ze szczytu kopca.
     • Budowanie kopca z wektora nieuporządkowanych danych.
   • Sortowanie przez kopcowanie.
2. Drzewa AVL:
   • Zasada organizacji danych.
   • Operacje na drzewach AVL:
     • Wstawianie elementu.
     • Usuwanie elementu.
     • Wyszukiwanie elementu.
   • Wyważanie drzewa:
     • Przypadki źle wywarzonych drzew
     • Rotacje
3. Drzewa Czerwono-Czarne:
   • Opis idei drzew czerwono-czarnych:
     • wymagania (5 reguł),
     • długość najkrótszej i najdłuższej ścieżki od korzenia do liścia.
   • Operacje na drzewach czerwono-czarnych:
     • Wstawianie elementu.
     • Usuwanie elementu.
     • Wyszukiwanie elementu.
   • Możliwe przypadki przy wykonywaniu ww. operacji i sposoby radzenia sobie z nimi.

Część ćwiczeń będzie wymagała użycia komputerów, więc prosimy o ich przyniesienie.

W archiwum heapsavl.zip znajdują się pliki potrzebne do wykonania ćwiczeń. W archiwum znajdują się następujące pliki:

• binary-heap.cpp - plik zawierający definicje metod klasy reprezentującej kopiec binarny maximum.
• binary-heap.h - plik nagłówkowy dla powyższej klasy, zawierający jej definicje.
• avlnode.cpp - plik zawierający definicję metod klasy reprezentującej drzewo AVL.
• avlnode.h - plik nagłówkowy dla powyższej klasy, zawierający jej definicje.
• avl.cpp - plik zawierający definicję metod klasy reprezentującej drzewo AVL.
• avl.h - oraz plik nagłówkowy.
• main*.cpp - pliki pokazujące przykładowe wykorzystanie klas.

W archiwum znajduje się plik binary-heap.cpp, który posiada dwie nie uzupełnione metody:

void binary_heap::buildHeap(const int* __array, int __size);
int* binary_heap::sort(void);

gdzie:

• buildHeap(const int* array, int size) przyjmuje dwa parametry:
  1. array wskaźnik do nieposortowanej tablicy - size - rozmiar tej tablicy
• sort nie przyjmuje żadnych parametrów nastomiast zwraca wskaźnik do posortowanej tablicy.

Zadaniem jest napisanie programu który wykorzysta kopiec do realizacji algorytmu sortowania (oczywiście przez kopcowanie).
Do tego celu należy:

1. Uzupełnić te dwie metody, przy czym w przypadku metody buildHeap nie można korzystać z metody insert - rozwiązanie nieoptymalne.
2. Napisać funkcję main w której stworzona zostanie nieposortowana tablica,
3. następnie na jej podstawie zbudowany zostanie kopiec i w końcu
4. za pomocą metody sort, otrzymamy tablicę posortowaną (kopiec nie może ulec zniszczeniu).

W archiwum jest plik avl.cpp który ma nie zdefiniowaną metodę

avlnode* avl::fixBalance(avlnode* __node)

która jako argument przyjmuje wskaźnik na węzeł względem którego ma odbyć się rotacja i zwraca wskaźnik na węzeł który po rotacji jest wstawiony na pierwotny. Zadaniem jest napisanie tej metody.
Realizacja zadania jest o tyle prosta że nie trzeba się bawić w poprawianie wag poszczególnych węzłów - robi się to automatycznie dzięki takiej a nie innej implementacji metod (leftWeight oraz rightWeight) klasy avlnode. Oczywiście jest to nie optymalne rozwiązanie ale za to dużo czytelniejsze i przez to lepiej nadaje się do celów prezentacyjnych. Jak widać docelowe rozwiązanie jest krótkie i polega na sprawdzeniu wyżej wymienionych warunków.

Przedstawione materiały i przykłady pochodzą z: Wikipedia EN, Wikipedia PL.

Wymagana znajomość odpowiednich rozdziałów z: Cormen - „Wprowadzenie do Algorytmów”.

Drzewa czerwono-czarne (red-black trees, RB trees) to kolejna po drzewach AVL próba rozwiązania problemu drzew samorównoważących. Drzewa RB są nowsze o kilka lat od AVL, operacje wstawiania i usuwania są tu nieco szybsze, ale z uwagi na to że równoważenie nie jest tak skrupulatne jak w AVL, operacje wyszukiwania mogą być nieco wolniejsze. Niezłe zachowanie worst-case, dzięki czemu szeroko stosowane w praktyce, m.in. do harmonogramowania w aktualnych wersjach jądra Linuksa.

Główne różnice w stosunku do klasycznych BST to

• to, że liście nie zawierają danych. W praktyce implementujemy je jako puste elementy, jako wskaźniki do jednego elementu (tzw. sentinel node, aby oszczędzić pamięć), lub wskaźniki do NIL (ale to nieco komplikuje implementację operacji na drzewie),
• każdy węzeł drzewa posiada dodatkowy atrybut, kolor, który może przyjmować wartości czerwony lub czarny.

Drzewo RB musi spełniać pięć reguł:

1. Każdy węzeł jest czerwony lub czarny.
2. Korzeń jest czarny.
3. Każdy liść jest czarny.
4. Jeśli węzeł jest czerwony, to jego synowie muszą być czarni.
5. Każda ścieżka z ustalonego węzła do liścia liczy tyle samo czarnych węzłów.

W efekcie, najdłuższa ścieżka od korzenia do liścia jest co najwyżej dwa razy dłuższa niż ścieżka najkrótsza. Wynika to z własności, które z kolei wynikają z ww. reguł:

1. Zgodnie z własnością 4, żadna ścieżka nie zawiera dwóch czerwonych węzłów pod rząd, jednak może zawierać czarne. Stąd najkrótsza ścieżka od węzła X zawiera wyłącznie n czarnych węzłów.
2. Zgodnie z własnością 5, druga ścieżka wychodząca z węzła X musi zawierać także n czarnych węzłów. Jedynym sposobem, aby miała ona inną łączną długość, jest umieszczenie pomiędzy każdą parą węzłów czarnych węzła czerwonego.
3. Zgodnie z własnością 3, liść kończący obie ścieżki musi być czarny. Jeżeli węzeł X jest czarny, wtedy w ścieżce możemy rozmieścić co najwyżej n-1 węzłów czerwonych, w przeciwnym zaś razie będziemy mieli w niej n czerwonych węzłów (wliczając w to sam X).

Operacja wstawiania składa się z trzech etapów:

1. Umieszczenie elementu za pomocą standardowego algorytmu dla drzew poszukiwań binarnych.
2. Pokolorowanie nowego węzła na czerwono.
3. Ewentualne przywrócenie własności czerwono-czarnych (rozpatrzenie możliwych przypadków).

Po wykonaniu kroków 1 i 2 możemy napotkać na 5 możliwych przypadków (rozpatrujemy je kolejno):

1. Wstawiony węzeł N jest korzeniem drzewa.
2. Rodzic (parent) wstawionego węzła P jest czarny (a więc reguły nie zostały naruszone).
3. Rodzic P jest czerwony, i brat ojca (wujek - uncle) węzła U jest czerwony.
4. Rodzic P jest czerwony, wujek U jest czarny i N jest prawym synem.
5. Rodzic P jest czerwony, wujek U jest czarny i N jest lewym synem.

UWAGA: Przypadki 3-5 występują w dwóch „lustrzanych” wariantach:

• P (rodzic wstawionego węzła) jest lewym synem swojego ojca (G),
• P (rodzic wstawionego węzła) jest prawym synem swojego ojca (G).

Komentarz i ilustracje zakładają, że P (rodzic wstawionego węzła) jest lewym synem swojego ojca (G), natomiast kod rozważa oba przypadki.

Pomonicze funkcje do ekstrakcji dziadka i wuja (nice!) wyglądają tak:

struct node *grandparent(struct node *n)
{
        if ((n != NULL) && (n->parent != NULL))
                return n->parent->parent;
        else
                return NULL;
}
 
struct node *uncle(struct node *n)
{
        struct node *g = grandparent(n);
        if (g == NULL)
                return NULL; // No grandparent means no uncle
        if (n->parent == g->left)
                return g->right;
        else
                return g->left;
}

Wstawiony węzeł N jest korzeniem drzewa.

Malujemy N na czarno, zgodnie z zasadą nr 2 korzeń ma być czarny, a ponieważ jest to korzeń, to dodaje jeden czarny węzeł do każdej ze ścieżek. Kończymy procedurę.

void insert_case1(struct node *n)
{
        if (n->parent == NULL)
                n->color = BLACK;
        else
                insert_case2(n);
}

Rodzic (parent) wstawionego węzła P jest czarny.

Zasada nr 4 jest nienaruszona (bo nie mamy dwóch czerwonych pod rząd w żadnej ścieżce). Zasada nr 5 również, bo nowy czerwony (który posiada dwójkę czarnych dzieci) zastąpił czarny liść, więc liczba czarnych w każdej ścieżce pozostaje niezmieniona.

void insert_case2(struct node *n)
{
        if (n->parent->color == BLACK)
                return; /* Tree is still valid */
        else
                insert_case3(n);
}

Rodzic P jest czerwony, i brat ojca (wujek - uncle) węzła U jest czerwony.

Przemalowujemy P i U na czarno, a dziadka G na czerwono. Liczba czarnych na każdej ścieżce jest zachowana. Dziadek może teraz jednak naruszać zasadę nr 2 (jeżeli jest korzeniem) lub 4 (jeżeli ma czerwonego ojca - pradziadka). Dlatego musimy całą procedurę (od przypadku nr 1) uruchomić rekurencyjnie dla węzła G (rekurencja jest niegroźna, bo ogonowa, więc można zrobić iteracyjnie).

void insert_case3(struct node *n)
{
        struct node *u = uncle(n), *g;
 
        if ((u != NULL) && (u->color == RED)) {
                n->parent->color = BLACK;
                u->color = BLACK;
                g = grandparent(n);
                g->color = RED;
                insert_case1(g);
        } else {
                insert_case4(n);
        }
}

Rodzic P jest czerwony, wujek U jest czarny i N jest prawym synem.

Wykonujemy rotację w lewo, która zamienia role P i N, a ponieważ dalej mamy czerwonego rodzica i dziecko, przetwarzamy dawnego rodzica P (po zamianie oznaczeń P↔N) według procedury dla przypadku 5.

Na skutek powyższej rotacji, niektóre ścieżki które nie przechodziły przez N teraz mogą przez ten węzeł przechodzić, a niektóre które przechodziły przez P mogą już przez niego nie przechodzić. Oba węzły są czerwone, więc zasada nr 5 nie jest naruszona.

void insert_case4(struct node *n)
{
        struct node *g = grandparent(n);
 
        if ((n == n->parent->right) && (n->parent == g->left)) {
                rotate_left(n->parent);
                n = n->left;
        } else if ((n == n->parent->left) && (n->parent == g->right)) {
                rotate_right(n->parent);
                n = n->right;
        }
        insert_case5(n);
}

Rodzic P jest czerwony, wujek U jest czarny i N jest lewym synem.

Wykonujemy rotację w prawo względem dziadka G. W efekcie dawny ojciec P jest rodzicem zarówno dawnego syna N, jak i dawnego dziadka G. Wiemy, że G musiał być czarny, więc jeżeli zamienimy kolory P oraz G, mamy znów spełnioną zasadę nr 4. Zasada 5 jest również spełniona, gdyż wszystkie ścieżki które przechodziły przez czarny G teraz przechodzą przez (obecnie czarny) P.

void insert_case5(struct node *n)
{
        struct node *g = grandparent(n);
 
        n->parent->color = BLACK;
        g->color = RED;  
        if (n == n->parent->left) 
                rotate_right(g);
        else
                rotate_left(g);
}

Usuwanie węzła posiadającego dwoje dzieci „nie-liściowych” (w nomenklaturze drzew RB) z klasycznego drzewa BST polega na wybraniu maksymalnego elementu z jego lewego poddrzewa (albo minimalnego z prawego) i przeniesieniu do usuwanego węzła. Kopiowanie wartości nie narusza własności drzew RB, więc rozpatrywany tu będzie tylko przypadek usuwania węzła posiadającego co najwyżej jeden węzeł „nie-liściowy”.

Przez M oznaczamy węzeł do usuniecia, przez C - jego wybrane dziecko. Jeżeli jedno z dzieci posiada wartość, przypisujemy to dziecko do C, jeżeli oba dzieci są NIL (liściami), przypisujemy dowolne.

Możliwe przypadki:

1. Jeżeli M jest czerwony, podmieniamy go przez C, który musi być czarny (zasada nr 4) - ten przypadek może mieć miejsce tylko jeżeli M ma dwoje dzieci NIL. Usunęliśmy węzeł czerwony, więc liczba czarnych węzłów w ścieżkach nie może się zmienić (zasada nr 5), a że rodzic czerwonego musiał być czarny, zasada nr 4 również jest spełniona.
2. Jeżeli M jest czarny, a C czerwony, usuwamy M a C malujemy na czarno - zasady nr 4 i 5 są spełnione.
3. Gorzej, jeżeli zarówno M jak i C są czarne. Podmieniamy M przez C, zmieniamy nazwę C na N, a nazwę jego nowego rodzeństwa (czyli drugiego dziecka rodzica usuniętego węzła M) na S. Rodzica usuniętego węzła (czyli nowego rodzica N) oznaczamy jako P, a dzieci węzła S - odpowiednio SL i SR.

Funkcja pomocnicza do szukania rodzeństwa:

struct node *sibling(struct node *n)
{
        if (n == n->parent->left)
                return n->parent->right;
        else
                return n->parent->left;
}

Powyższe kroki wykonuje następujący kod:

void delete_one_child(struct node *n)
{
        /*
         * Precondition: n has at most one non-null child.
         */
        struct node *child = is_leaf(n->right) ? n->left : n->right;
 
        replace_node(n, child);
        if (n->color == BLACK) {
                if (child->color == RED)
                        child->color = BLACK;
                else
                        delete_case1(child);
        }
        free(n);
}

Jeżeli N i jego pierwotny rodzic są czarni, mamy do rozważenia kilka przypadków.

N jest nowym korzeniem. Usunęliśmy jeden węzeł z każdej ścieżki, a nowy korzeń jest czarny, więc własności są zachowane.

void delete_case1(struct node *n)
{
        if (n->parent != NULL)
                delete_case2(n);
}

S jest czerwony. Zamieniamy kolory P i S i wykonujemy rotację w lewo na P, przez co S staje się dziadkiem N.

void delete_case2(struct node *n)
{
        struct node *s = sibling(n);
 
        if (s->color == RED) {
                n->parent->color = RED;
                s->color = BLACK;
                if (n == n->parent->left)
                        rotate_left(n->parent);
                else
                        rotate_right(n->parent);
        } 
        delete_case3(n);
}

P, S i dzieci S są czarne. Malujemy S na czerwono. Teraz wszystkie ścieżki przechodzące przez S, czyli dokładnie te które nie przechodzą przez N, mają o jeden czarny węzeł mniej. Ponieważ usunęliśmy rodzica P który był czarny, liczniki po lewej i prawej stronie tego poddrzewa się zgadzają. Niestety, ścieżki prowadzące przez P mają o jeden czarny węzeł mniej niż te które nie przechodzą przez P. Dlatego uruchamiamy procedurę rebalansowania począwszy od P.

void delete_case3(struct node *n)
{
        struct node *s = sibling(n);
 
        if ((n->parent->color == BLACK) &&
            (s->color == BLACK) &&
            (s->left->color == BLACK) &&
            (s->right->color == BLACK)) {
                s->color = RED;
                delete_case1(n->parent);
        } else
                delete_case4(n);
}

S i jego dzieci są czarni, ale P jest czerwony. Zamieniamy więc kolory P i S. Dodaje to jeden czarny węzeł do ścieżek prowadzących przez N, co kompensuje usunięty węzeł.

void delete_case4(struct node *n)
{
        struct node *s = sibling(n);
 
        if ((n->parent->color == RED) &&
            (s->color == BLACK) &&
            (s->left->color == BLACK) &&
            (s->right->color == BLACK)) {
                s->color = RED;
                n->parent->color = BLACK;
        } else
                delete_case5(n);
}

S jest czarny, SL czerwony, SR czarny, a N jest lewym dzieckiem. Wykonujemy rotację w prawo w S, tak że SL staje się rodzicem S i nowym rodzeństwem N. Teraz zamieniamy kolor S i jego rodzica.

void delete_case5(struct node *n)
{
        struct node *s = sibling(n);
 
        if  (s->color == BLACK) { /* this if statement is trivial, 
due to case 2 (even though case 2 changed the sibling to a sibling's child, 
the sibling's child can't be red, since no red parent can have a red child). */
/* the following statements just force the red to be on the left of the left of the parent, 
   or right of the right, so case six will rotate correctly. */
                if ((n == n->parent->left) &&
                    (s->right->color == BLACK) &&
                    (s->left->color == RED)) { /* this last test is trivial too due to cases 2-4. */
                        s->color = RED;
                        s->left->color = BLACK;
                        rotate_right(s);
                } else if ((n == n->parent->right) &&
                           (s->left->color == BLACK) &&
                           (s->right->color == RED)) {/* this last test is trivial too due to cases 2-4. */
                        s->color = RED;
                        s->right->color = BLACK;
                        rotate_left(s);
                }
        }
        delete_case6(n);
}

S jest czarny, SR czerwony, a N jest lewym dzieckiem. Wykonujemy rotację w lewo w P, tak że S staje się rodzicem P i SR. N zyskuje dodatkowego czarnego przodka: albo P stał się czarny, albo był czarny a S został dodany jako czarny dziadek. Ścieżki prowadzące przez N mają więc teraz dodatkowy czarny węzeł.

Dla ścieżek nie prowadzących przez N mamy możliwości:

• Prowadzą przez nowe rodzeństwo N. Takie ścieżki muszą prowadzić przez P i S (wcześniej i teraz), więc liczba czarnych węzłów się nie zmienia.
• Prowadzą przez nowego wuja N, SR. Wcześniej takie ścieżki musiały prowadzić przez S, rodzica S i SR (który był czerwony), ale teraz prowadzą tylko przez S, który przyjął kolor swojego dawnego rodzica, oraz SR, który został przemalowany z czerwonego na czarny.

Oba przypadki oznaczają, że liczba czarnych węzłów na tych ścieżkach nie uległa zmianie. Zasady nr 4 i 5 są więc znów spełnione.

void delete_case6(struct node *n)
{
        struct node *s = sibling(n);
 
        s->color = n->parent->color;
        n->parent->color = BLACK;
 
        if (n == n->parent->left) {
                s->right->color = BLACK;
                rotate_left(n->parent);
        } else {
                s->left->color = BLACK;
                rotate_right(n->parent);
        }
}