Zaawansowane algorytmy i struktury danych/Ćwiczenia 14: Różnice pomiędzy wersjami
Nie podano opisu zmian |
Nie podano opisu zmian |
||
| Linia 3: | Linia 3: | ||
Jaka jest minimalna stała c taka, że dla każdego drzewa rozmiaru co najmniej 2 mamy | Jaka jest minimalna stała c taka, że dla każdego drzewa rozmiaru co najmniej 2 mamy | ||
<center><math> | | <center><math> |Contract(T)| \le c\cdot |T| </math> </center> | ||
Rozwiązanie | Rozwiązanie | ||
| Linia 18: | Linia 18: | ||
Rozwiazanie. | Rozwiazanie. | ||
Niech x będzie pierwszym węzłem na ścieżce ze statycznego węzła do korzenia takim, że <math> |T_x|\ge | |||
FIB_{k-1}</math>. | |||
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, | |||
<math> T_p\otimes x</math>, oraz <math> T_q </math>. | <math> T2 = T_p\otimes x</math>, oraz <math> T3= T_q </math>. | ||
Wtedy <math>|T1|, |T2| \le FIB_{k-1}</math> oraz <math> |T3| < FIB_{k-1}</math>. 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 | |||
<math> x'\in T_p</math>. Następnie w k-tej redukcji korzeń ma jedyne dowiązanie do węzła statycznego v. Kończy to | |||
W konsekwencji po redukcji k-1 korze"n | |||
<math> x'\in T_p</math>. | |||
dow"od indukcyjny punktu (b). | dow"od indukcyjny punktu (b). | ||
Wersja z 11:48, 6 wrz 2006
Zadanie.
Jaka jest minimalna stała c taka, że dla każdego drzewa rozmiaru co najmniej 2 mamy
Rozwiązanie
c=2/3.
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 .
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, , oraz . Wtedy oraz . 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 . 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).
