2. Klasówka 2004/05#
Zadanie 1#
Zaproponuj strukturę danych dla dynamicznego kolorowania lasu. Zakładamy, że liczba wierzchołków w lesie nie jest niezmienna i wynosi \(n\). Możesz przyjąć, że wierzchołki są jednoznacznie identyfikowane przez liczby naturalne z zakresu \(1..n\). Początkowo wszystkie drzewa w lesie są jednowierzchołkowe. Na lesie wykonywane są następujące operacje:
\(Join(u, v)\):: jeśli \(u\) i \(v\) należą do różnych drzew w lesie, to połącz te drzewa krawędzią \(u-v\).
\(Col(u)\):: podaj kolor wierzchołka \(u\).
Do kolorowania wierzchołków lasu można używać tylko dwóch kolorów. Kolory wierzchołków pomiędzy dwiema kolejnymi istotnymi operacjami \(Join\) (czyli takimi, które łączą dwa różne drzewa w jedno) nie mogą ulegać zmianie: za każdym razem gdy pytamy o kolor tego samego wierzchołka, to musimy dostać tę samą odpowiedź.
Zaprojektuj efektywny sposób wykonywania obu operacji i przeanalizuj złożoność zaproponowanych algorytmów. Podaj także, w jaki sposób Twoja struktura danych jest inicjalizowana, i podaj koszt inicjalizacji.
Zadanie 2#
Dane jest \(n\)-wierzchołkowe drzewo binarne \(T\), którego wierzchołki zostały ponumerowane w porządku \(inorder\). Wierzchołki utożsamiamy z ich numerami. Dla każdego wierzchołka \(u\) mamy dane \(left[u]\) oraz \(right[u]\), odpowiednio, lewego syna \(u\), prawego syna \(u\) oraz ojca \(u\). Jeśli taki wierzchołek nie istnieje, to wartością odpowiedniego pola jest \(0\). Na drzewie \(T\) wykonujemy operacje:
\(Rotate(u)\):: jeśli \(u\) nie jest korzeniem \((par[u] \neq 0)\), to wykonaj pojedynczą rotację \(u\) z ojcem.
\(Depth(u)\):: podaj głębokość \(u\) w aktualnym drzewie
Zaprojektuj efektywny sposób wykonywania obu operacji i dokonaj analizy złożoności zaproponowanych przez siebie algorytmów.
Zadanie 3#
Poniżej podano ciąg wskaźników zrównoważenia (wys. lewego poddrzewa - wys. prawego poddrzewa) pewnego AVL-drzewa, wypisany w kolejności in-order:
\(0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0\)
\(-1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, -1, 0\)
Narysuj AVL-drzewa, którym odpowiadają te ciągi.
Bonus:
Udowodnij, że dwóm różnym AVL-drzewom odpowiadają różne ciągi wskaźników. Zaproponuj efektywny algorytm odtwarzania z danego ciągu odpowiadającego mu drzewa i dokonaj analizy jego złożoności.