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

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