====== Kopce binarne, drzewa AVL i czerwono-czarne ======

===== Teoria do przygotowania =====
  - 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.
  - Drzewa AVL:
    * Zasada organizacji danych.
    * Operacje na drzewach AVL:
      * Wstawianie elementu.
      * Usuwanie elementu.
      * Wyszukiwanie elementu.
    * Wyważanie drzewa:
      * Przypadki źle wywarzonych drzew
      * Rotacje
  - 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.**


===== Ćwiczenia implementacyjne =====

==== Pliki do ćwiczeń ====
W archiwum {{:pl:dydaktyka:asd:cwiczenia: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.

==== Ćwiczenie: kopce binarne ====

W archiwum znajduje się plik ''binary-heap.cpp'', który posiada dwie nie uzupełnione metody:<code c++>
void binary_heap::buildHeap(const int* __array, int __size);
int* binary_heap::sort(void);
</code>gdzie:
  * ''buildHeap(const int* __array, int __size)'' przyjmuje dwa parametry:
    - ''__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:
  - Uzupełnić te dwie metody, przy czym w przypadku metody ''buildHeap'' nie można korzystać z metody ''insert'' - rozwiązanie nieoptymalne.
  - Napisać funkcję ''main'' w której stworzona zostanie nieposortowana tablica,
  - następnie na jej podstawie zbudowany zostanie kopiec i w końcu
  - za pomocą metody sort, otrzymamy tablicę posortowaną (kopiec nie może ulec zniszczeniu).



==== Ćwiczenie: drzewa AVL ====

W archiwum jest plik ''avl.cpp'' który ma nie zdefiniowaną metodę<code c++>
avlnode* avl::fixBalance(avlnode* __node)
</code>
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.





===== Uzupełnienie teoretyczne =====


==== Drzewa czerwono-czarne ====

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

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


{{:pl:dydaktyka:asd:priv:labs2012:rbt-example.svg?600}}

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ł:
  - Każdy węzeł jest czerwony lub czarny.
  - Korzeń jest czarny.
  - Każdy liść jest czarny.
  - Jeśli węzeł jest czerwony, to jego synowie muszą być czarni.
  - 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ł:
  - 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.
  - 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.
  - 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).

=== Wstawianie ===
Operacja wstawiania składa się z trzech etapów:
  - Umieszczenie elementu za pomocą standardowego algorytmu dla drzew poszukiwań binarnych.
  - Pokolorowanie nowego węzła na czerwono.
  - 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):
  - Wstawiony węzeł **N** jest korzeniem drzewa.
  - Rodzic (parent) wstawionego węzła **P** jest czarny (a więc reguły nie zostały naruszone).
  - Rodzic **P** jest czerwony, i brat ojca (wujek - uncle) węzła **U** jest czerwony.
  - Rodzic **P** jest czerwony, wujek **U** jest czarny i **N** jest prawym synem.
  - 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:
<code c>
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;
}
</code>

== Przypadek 1 ==
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ę.

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

== Przypadek 2 ==
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.

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


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

{{:pl:dydaktyka:asd:priv:labs2012:rbt-insert-case3.png}}

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).

<code c>
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);
        }
}
</code>

== Przypadek 4 ==
Rodzic **P** jest czerwony, wujek **U** jest czarny i **N** jest prawym synem.

{{:pl:dydaktyka:asd:priv:labs2012:rbt-insert-case4.png}}

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 [[#przypadek_5|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. 

<code c>
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);
}
</code>




== Przypadek 5 ==
Rodzic **P** jest czerwony, wujek **U** jest czarny i **N** jest lewym synem.

{{:pl:dydaktyka:asd:priv:labs2012:rbt-insert-case5.png}}

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**.

<code c>
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);
}
</code>



=== Usuwanie ===
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:
  - 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.
  - Jeżeli **M** jest czarny, a **C** czerwony, usuwamy **M** a **C** malujemy na czarno - zasady nr 4 i 5 są spełnione.
  - 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:
<code c>
struct node *sibling(struct node *n)
{
        if (n == n->parent->left)
                return n->parent->right;
        else
                return n->parent->left;
}
</code>

Powyższe kroki wykonuje następujący kod:
<code c>
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);
}
</code>

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

== Usuwanie - przypadek 1 ==

**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.

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

== Usuwanie - przypadek 2 ==

{{:pl:dydaktyka:asd:priv:labs2012:rbt-delete-case2.png}}

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

<code c>
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);
}
</code>

== Usuwanie - przypadek 3 ==

{{:pl:dydaktyka:asd:priv:labs2012:rbt-delete-case3.png}}

**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**.

<code c>
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);
}
</code>


== Usuwanie - przypadek 4 ==

{{:pl:dydaktyka:asd:priv:labs2012:rbt-delete-case4.png}}

**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ł.

<code c>
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);
}
</code>


== Usuwanie - przypadek 5 ==

{{:pl:dydaktyka:asd:priv:labs2012:rbt-delete-case5.png}}

**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.


<code c>
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);
}
</code>


== Usuwanie - przypadek 6 ==

{{:pl:dydaktyka:asd:priv:labs2012:rbt-delete-case6.png}}

**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.

<code c>
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);
        }
}
</code>