--- 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)
@@ Linia 31: / Linia 31: @@
 **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>

pl/dydaktyka/asd/cwiczenia/2012-heapavl.1336808023.txt.gz · ostatnio zmienione: 2019/06/27 15:51 (edycja zewnętrzna)

Pokaż stronę Poprzednie wersje

Menadżer multimediów Do góry

AIwiki

Menu

Dla Studentów

Old specialized AI courses

SMaDA/SMaIDA/AIDA

Informatyka (EAIiIB)

Studia Dr

Inne materialy dydaktyczne

Archiwum

Dyplomanci

Geist Season of Code

HeKatE

Public

Różnice