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}$.

Rozwi?zanie

Wynika to z rekurencji definiuj?cej drzewa $T_k$

Zadanie 3

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 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"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 5

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.