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:array wskaźnik do nieposortowanej tablicy
-
size
- rozmiar tej tablicysort
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:
buildHeap
nie można korzystać z metody insert
- rozwiązanie nieoptymalne.main
w której stworzona zostanie nieposortowana tablica,
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
Drzewo RB musi spełniać pięć reguł:
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ł:
Operacja wstawiania składa się z trzech etapów:
Po wykonaniu kroków 1 i 2 możemy napotkać na 5 możliwych przypadków (rozpatrujemy je kolejno):
UWAGA: Przypadki 3-5 występują w dwóch „lustrzanych” wariantach:
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:
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:
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); } }