Nowa wersja
|
Poprzednia wersja
|
pl:dydaktyka:asd:cwiczenia:2012-heapavl [2012/05/12 09:33] ikaf utworzono |
pl:dydaktyka:asd:cwiczenia:2012-heapavl [2019/06/27 15:50] (aktualna) |
**Część ćwiczeń będzie wymagała użycia komputerów, więc prosimy o ich przyniesienie.** | **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> |
| |