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

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

Rozwiązanie

c=2/3.

Zadanie.

Udowodnij indukcyjnie punkt (b) wzmocnionego lematu o kontrakcji.

Rozwiazanie.

    Niech   $|T|\le FI{B}_k$. Niech  xbędzie  pierwszym w"ez"lem na "scie"rce ze statycznego w"ez"la do korzenia takim, "re $|T_x|\ge FI{B}_{k-1}$. Ponadto niech  $T1$, $T2$ oraz $T3$ b"ed"a drzewami odpowiednio: T z węzłem x jako stayczny liść (z obciętymi poddrzewami o korzeniach p,q,

$T_p\otimes x$, oraz $T_q$.

Wtedy $|T1|,|T2|\le FI{B}_{k-1}$ oraz Parser nie mógł rozpoznać (błąd składni): {\displaystyle |T3| < FIB_{k-1}M/math>. Po (k-1)-szej redukcji drzewa T1$ oraz T2 sa zredukowane do jednego w"ez"la z jednym statycznym li"sciem , dzi"eki za"lo"reniu indukcyjnemu (b) . Wszystkie w"ez"ly T3 staj"a si"e li"s"cmi po (k-2)-giej redukcji dzi"eki za"lo"reniu indukcyjnemu (b). W konsekwencji po redukcji k-1 korze"n ca"lego drzewa T ma jedynego nast"epnika x' takiego, "re x'=x lub <math> x'\in T_p} . Nast"epnie w k-tej redukcji korze"n ma jedyne dowi"azanie do w"ez"la statycznego v. Ko"nczy to dow"od indukcyjny punktu (b).