Zaawansowane algorytmy i struktury danych/Ćwiczenia 14

Zadanie.

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.

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.

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

Rozwiązanie.

Wez statyczny liść v, dodatkowt 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.

Udowodnij indukcyjnie punkt (b) wzmocnionego lematu o kontrakcji.

Rozwiazanie.

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"n całego drzewa T ma jedynego następnika x' takiego, że x'=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"od indukcyjny punktu (b).

Zadanie.

Przypuśćmy, że zmieniamy definicje kontrakcji. Najpierw wykonujemy Rake, a potem (po zakończeniu Rake) wykonujemy Compress. Udowodnij, że liczbą 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.