Zaawansowane algorytmy i struktury danych/Ćwiczenia 14

Zadanie 1

Jaka jest minimalna stała $c$ taka, że dla każdego drzewa rozmiaru co najmniej 2 mamy

$|Contract(T)|\le c\cdot |T|$

Rozwiązanie

c=2/3.

Zadanie 2

Uzasadnij, dlaczego $|T_k|=Fi{b}_k<math>oraz<math>Contract(T_k)=T_{k-1}$.

Rozwiazanie

Wynika to z rekurencji definiującej drzewa $T_k$

Zadanie 3

Udowodnij, że $TIM{E}^{\prime }(Fi{b}_k+1)>k$.

Rozwiązanie

.

Weź statyczny liść $v$, dodatkowo korzeń $r$ i zbuduj drzewo, którego korzeniem jest $r$, następnikiem $r$ jest korzeń $T_p$, oraz dodatkowo korzeń $T_p$ ma syna $v$.

Zadanie 4

Udowodnij indukcyjnie punkt (b) wzmocnionego lematu o kontrakcji.

Rozwiązanie

Niech $x$ będzie pierwszym węzłem na ścieżce ze statycznego węzła do korzenia takim, że $|T_x|\ge FI{B}_{k-1}$.

Ponadto niech $T1,T2$ oraz $T3$ będą drzewami zdefiniowanymi następująco: T1 jest równy T z węzłem x jako statyczny liść (z obciętymi poddrzewami o korzeniach p,q, $T2=T_p\otimes x$, oraz $T3=T_q$. Wtedy $|T1|,|T2|\le FI{B}_{k-1}$ oraz $|T3|<FI{B}_{k-1}$.

Po $(k-1)$-szej redukcji drzewa T1 oraz T są zredukowane do jednego węzła z jednym statycznym liściem dzięki założeniu indukcyjnemu (b) . Wszystkie węzły T3 stają się liśćmi po (k-2)-giej redukcji dzięki założeniu indukcyjnemu (b).

W konsekwencji, po redukcji k-1 korzeń całego drzewa T ma jedynego następnika $x^{\prime }$ takiego, że $x^{\prime }=x$ lub $x^{\prime }\in T_p$. Następnie w k-tej redukcji korzeń ma jedyne dowiązanie do węzła statycznego $v$. Kończy to dowód indukcyjny punktu (b).

Zadanie 5

Przypuśćmy, że zmieniamy definicje kontrakcji. Najpierw wykonujemy Rake, a potem (po zakończeniu Rake) wykonujemy Compress. Udowodnij, że liczba kontrakcji jest w dalszym ciągu $O(\log n)$.

Rozwiązanie

.

Liczba zmodyfikowanych kontrakcji jest nie mniejsza niż liczba kontrakcji, które opisujemy w module, a więc w dlaszym ciągu logarytmiczna.