8-ds/8-ds.tex

   1 \input ../lecnotes.tex
   2
   3 % Vkladani obrazku
   4 \input ../mjipe.tex
   5 \def\treepic#1{
   6 \medskip
   7 \IpeInput{treepic/t#1.ipe}
   8 \medskip
   9 }
  10
  11 \prednaska{8}{Datové struktury}{}
  12
  13 Co si mù¾eme pøedstavit pod pojmem datová struktura? Mù¾eme tøeba chtít udr¾ovat
  14 mno¾inu $X$ prvkù z nìjakého universa $X\subseteq U$ (kde universum mohou být
  15 napøíklad pøirozená èísla).
  16
  17 Na na¹ich datech budeme chtít provádìt následující operace:
  18 \itemize\ibull
  19 \:{\it Insert} -- vlo¾it novou polo¾ku
  20 \:{\it Delete} -- smazat polo¾ku
  21 \:{\it Find} -- najít polo¾ku
  22 \endlist
  23
  24 Èasovou slo¾itost jednotlivých operací poèítejme vzhledem k poètu prvkù obsa¾ených v
  25 datové struktuøe.
  26
  27 Také mù¾eme chtít udr¾ovat slovník, tedy mno¾inu dvojic $(k, v)$ kde $k\in U$ se
  28 nazývá klíè a $v$ hodnota. Dále pøedpokládejme, ¾e $U$ je lineárnì uspoøádaná a prvky
  29 porovnáme v konstantním èase.
  30
  31 V následující tabulce jsou nìkteré mo¾né zpùsoby reprezentace na¹í datové struktury.
  32
  33 \settabs 4 \columns
  34 \+                      & Insert        & Delete        & Find \cr
  35 \+ pole                 & $\Theta (1)$  & $\Theta (n)$ & $\Theta (n)$ \cr
  36 \+ setøídìné pole       & $\Theta (n)$  & $\Theta (n)$ & $\Theta (\log n)$ \cr
  37 \+ spojový seznam       & $\Theta (1)$  & $\Theta (n)$ & $\Theta (n)$ \cr
  38 \+ setøídìný seznam     & $\Theta (n)$  & $\Theta (n)$ & $\Theta (n)$ \cr
  39 \+ vyhledávací stromy   & $\Theta (\log n)$     & $\Theta (\log n)$ & $\Theta (\log n)$ \cr
  40
  41 \s{Pozorování:} Proces binárního vyhledávání v~setøídìném poli se dá reprezentovat
  42 binárním vyhledávacím stromem.
  43
  44 \s{Definice:} {\I Binární strom:} Strom je binární, pokud je zakoøenìný a ka¾dý vrchol
  45 má nejvý¹e dva syny, u nich¾ rozli¹ujeme, který je levý a který pravý.
  46
  47 \s{Definice:} Pro vrchol $v$ znaèíme:
  48 \itemize\ibull
  49 \:$l(v)$ a $p(v)$ -- levý a pravý syn vrcholu $v$
  50 \:$L(v)$ a $P(v)$ -- levý a pravý podstrom vrcholu $v$
  51 \:$S(v)$ -- pøíslu¹ný podstrom s~koøenem $v$
  52 \:$h(v)$ -- hloubka stromu $S(v)$, neboli délka nejdel¹í cesty z koøene do listu
  53 \endlist
  54
  55 \s{Definice:} {\I Binární vyhledávací strom} (BVS): Binární strom je vyhledávací,
  56 pokud v~ka¾dém vrcholu je ulo¾ena dvojice (klíè, hodnota) [ztoto¾níme vrchol s~klíèem]
  57 a pro v¹echny vrcholy platí: $\left ( \forall u \in L(v) : u < v \right ) $ $ \&$ $
  58 \left ( \forall u \in P(v) : u > v \right)$.
  59
  60 \s{Pøíklady binárních vyhledávacích stromù:}
  61
  62 \treepic{2}
  63
  64 \break
  65
  66 Jak budou tedy vypadat operace {\it Find}, {\it Insert} a {\it Delete} na~binárním
  67 vyhledávacím stromu?
  68
  69 {\bo Find$(v,x)$:}
  70 \algo
  71 \:Pokud $v = \emptyset \Rightarrow$ vrátíme $\emptyset$.
  72 \:Pokud $v = x \Rightarrow$ vrátíme $v$.
  73 \:Pokud $v < x \Rightarrow$ vrátíme $\<Find>(p(v),x)$.
  74 \:Pokud $v > x \Rightarrow$ vrátíme $\<Find>(l(v),x)$.
  75 \endalgo
  76
  77 {\bo Insert$(v,x)$:}
  78 \algo
  79 \:Jako \<Find> a na~konci pøidáme list.
  80 \endalgo
  81
  82 {\bo Delete$(v)$:}
  83 \algo
  84 \:Pokud $v$ je list $\Rightarrow$ jednodu¹e list utrhneme.
  85 \:Pokud $v$ má jednoho syna $\Rightarrow$ vrchol \uv{vyøízneme}.
  86 \:Jinak má $v$ oba syny $\Rightarrow$ do vrcholu vlo¾íme minimum z $P(v)$, co¾ bude list, a ten utrhneme.
  87 \endalgo
  88
  89 \s{Poznámka:} Pokud má vrchol $v$ pøi operaci {\it Delete} oba syny, je vlo¾ení minima
  90 z $P(v)$ ekvivalentní s~vlo¾ením maxima z $L(v)$.
  91
  92 \s{Pøíklady operací  {\it Insert} a {\it Delete} na~BVS:}
  93 \treepic{1}
  94 \treepic{3}
  95
  96 \break Èasová slo¾itost v¹ech tøí operací je $\Theta(\<hloubka stromu>)$, co¾ mù¾e být
  97 $\Theta(n)$, kdy¾ budeme mít smùlu a strom bude (témìø) lineární spojový seznam, nebo
  98 $\Theta(\log{n})$ kdy¾ bude strom pìknì vyvá¾enì vystavìný. Vidíme tedy, ¾e slo¾itost
  99 operací stojí a padá s~hloubkou stromu. Proto by se nám líbilo, aby mìl ná¹ strom v¾dy
 100 hloubku $\Theta(\log{n})$. Podívejme se tedy, jak se dá navrhnout binární vyhledávací
 101 strom, aby tuto podmínku splòoval \dots
 102
 103 \h{Vyvá¾ené binární vyhledávací stromy}
 104
 105 \s{Definice:} {\I Dokonalá vyvá¾enost:} Strom je dokonale vyvá¾ený, pokud pro v¹echny
 106 jeho vrcholy platí: $\left \vert \vert L(v)\vert - \vert P(v)\vert \right \vert \leq 1
 107 $.
 108
 109 Takto definovaný binární strom bude mít urèitì logaritmickou hloubku. Jak takový strom
 110 ale konstruovat? To se nám podaøí buï staticky, nebo na~nìm budou operace dra¾¹í ne¾
 111 $\Theta(\log{n})$.
 112
 113 \s{Statická konstrukce dokonale vyvá¾eného BVS:} Vybereme prostøední prvek ze
 114 setøídìného pole (tedy medián posloupnosti) a dáme ho do~koøene stromu. Jeho syny pak
 115 vystavíme rekurzivnì z~levé a pravé pùlky pole. Celá konstrukce tedy trvá $\O(n)$.
 116
 117 \s{Lemma} buï Insert nebo Delete v dokonale vyvá¾eném BVS trvají $\Omega(n)$ (ve
 118 skuteènosti oba, ale dùkaz je mnohem obtí¾nìj¹í).
 119
 120 \proof Nech» $n:=2^k-1$ pak má dokonale vyvá¾ený BVS urèený tvar a je jednoznaèné, co
 121 je v koøeni. Bez újmy na obecnosti mù¾eme pøedpokládat, ¾e nejmen¹í èíslo ve stromì je
 122 $x$ a nejvìt¹í je $x+n-1$.
 123
 124 Proveïme posloupnost operací $$Insert(x+n), Delete(x), Insert(x+n+1), Delete(x+1)
 125 \dots$$ v¾dy se aspoò polovina listù posune o patro vý¹. Víme ¾e listù v na¹em stromì
 126 je $(n+1)/2$. Tedy aspoò jedna z operací Insert nebo Delete trvá $\Theta (n)$.
 127
 128 Vidíme tedy, ¾e to ná¹ problém pøíli¹ neøe¹í. Potøebovali bychom, aby se strom dal
 129 také efektivnì udr¾ovat. Zkusíme proto slab¹í podmínku:
 130
 131 \s{Definice:} {\I Hloubková vyvá¾enost:} Strom je hloubkovì vyvá¾ený, pokud pro
 132 v¹echny jeho vrcholy platí: $\left \vert h(L(v)) - h(P(v)) \right \vert \leq 1 $.
 133
 134 Stromùm s~hloubkovým vyvá¾ením se øíká {\I AVL stromy} (objeviteli je ru¹tí
 135 matematikové G. M. Adelson-Velsky a E. M. Landis, podle nich jsou také pojmenovány) a
 136 platí o~nich následující lemma:
 137
 138 \s{Lemma:} AVL strom na~$n$ vrcholech má hloubku $ \Theta(\log{n}) $.
 139
 140 \proof Uva¾me posloupnost $A_k = $ minimální poèet vrcholù AVL stromù hloubky $k$.
 141 Staèí ukázat, ¾e $A_k$ roste exponenciálnì. Podívejme se na minimální AVL stromy:
 142 $$\eqalign{
 143 A_0 &= 1 \cr
 144 A_1 &= 2 \cr
 145 A_2 &= 4 \cr
 146 A_3 &= 7 \cr
 147 &\vdots \cr
 148 A_k &= 1 + A_{k - 1} + A_{k - 2}. \cr
 149 }$$
 150
 151 Rekurentní vzorec jsme dostali rekurzivním stavìním stromu hloubky $k$: nový koøen a 2
 152 podstromy o~hloubkách $k - 1$ a $k - 2$.
 153
 154 Vidíme tedy, ¾e $A_n = F_{n + 2} - 1$. (Mù¾eme dokázat napø. indukcí.) Teï nám ji¾
 155 staèí dokázat, ¾e posloupnost $A_k$ roste exponenciálnì S výhodou mù¾eme vyu¾ít toho,
 156 ¾e na první pøedná¹ce jsme si ji¾ dokázali, ¾e Fibonacciho èísla rostou exponenciálnì.
 157 Nicménì pro zapomnìtlivé mù¾eme dùkaz ve struènosti zopakovat:
 158
 159 Indukcí doká¾eme, ¾e $ A_k \geq 2^{k \over 2} $. První indukèní krok jsme si u¾
 160 ukázali, teï pro $ k \geq 2 $ platí: $ A_k = 1 + A_{k - 1} + A_{k - 2} > 2^{{k - 1}
 161 \over 2} + 2^{{k - 2} \over 2} = 2^{k \over 2} \cdot (2^{-{1 \over 2}} + 2^{-1}) \cong
 162 2^{k \over 2} \cdot 1.21 > 2^{k \over 2}.$
 163
 164 Tímto jsme dokázali, ¾e na~ka¾dé hladinì je minimálnì exponenciálnì vrcholù, co¾ nám
 165 zaruèuje hloubku $ \Theta(\log{n})$.
 166 \qed
 167
 168 \bye