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? V na¹ich programech èasto chceme
  14 nìkteré vìci abstrahovat (pou¾itím funkcí, objektù\dots). Proè tedy nezkusit
  15 abstrahovat i operace s daty? Napøed si urèíme, co s na¹imi daty budeme provádìt a pak
  16 vymyslíme jejich co nejrychlej¹í reprezentaci.
  17
  18 Mù¾eme tøeba chtít udr¾ovat koneènou {\it mno¾inu} $X$ prvkù z nìjakého universa $X\subseteq
  19 U$. Kde universum mohou být napøíklad pøirozená èísla, tedy universum mù¾e být
  20 nekoneèné na rozdíl od $X$.
  21
  22 Na na¹ich datech budeme chtít provádìt následující operace:
  23 \itemize\ibull
  24 \:{\it Insert} -- vlo¾it novou polo¾ku
  25 \:{\it Delete} -- smazat polo¾ku
  26 \:{\it Find} -- najít polo¾ku
  27 \endlist
  28
  29 Jak mìøit èasovou slo¾itost? Urèitì ji nechceme mìøit vùèi délce vstupu, proto¾e ho
  30 nemusíme mít celý najednou ve struktuøe. Èasovou slo¾itost jednotlivých operací tedy
  31 poèítejme vzhledem k poètu prvkù obsa¾ených v datové struktuøe v daný okam¾ik.
  32
  33 Také mù¾eme chtít udr¾ovat {\it slovník}, tedy mno¾inu dvojic $(k, v)$ kde $k\in U$ se
  34 nazývá klíè a $v$ hodnota. Dále pøedpokládejme, ¾e $U$ je lineárnì uspoøádaná a
  35 s~klíèi i hodnotami pracujeme v konstantním èase.
  36
  37 Dále budeme zkoumat jen slovník, proto¾e mno¾ina je jen jeho speciálním pøípadem.
  38
  39 Po slovníku budeme chtít:
  40 \itemize\ibull
  41 \:{\it Insert($k$, $v$)} -- vlo¾it novou hodnotu spolu s klíèem (pøedpokládajíce, ¾e ve
  42 struktuøe dosud tento klíè není pøítomen)
  43 \:{\it Delete($k$)} -- smazat polo¾ku podle klíèe
  44 \:{\it Find($k$)} -- najít polo¾ku podle klíèe
  45 \endlist
  46
  47 V následující tabulce jsou nìkteré mo¾né zpùsoby reprezentace na¹í datové struktury:
  48
  49 \settabs 4 \columns
  50 \+                      & \<Insert>     & \<Delete>     & \<Find> \cr
  51 \+ pole                 & $\Theta (1)$  & $\Theta (n)$  & $\Theta (n)$ \cr
  52 \+ setøídìné pole       & $\Theta (n)$  & $\Theta (n)$  & $\Theta (\log n)$ \cr
  53 \+ spojový seznam       & $\Theta (1)$  & $\Theta (n)$  & $\Theta (n)$ \cr
  54 \+ setøídìný seznam     & $\Theta (n)$  & $\Theta (n)$  & $\Theta (n)$ \cr
  55 \+ vyhledávací stromy   & $\Theta (\log n)$     & $\Theta (\log n)$     & $\Theta (\log n)$ \cr
  56
  57 \smallskip
  58
  59 \s{Pozorování:} Proces binárního vyhledávání v~setøídìném poli se dá reprezentovat
  60 binárním vyhledávacím stromem.
  61
  62 \s{Definice:} {\I Binární strom:} Strom je binární, pokud je zakoøenìný a ka¾dý vrchol
  63 má nejvý¹e dva syny, u nich¾ rozli¹ujeme, který je levý a který pravý.
  64
  65 \s{Definice:} Pro vrchol $v$ znaèíme:
  66 \itemize\ibull
  67 \:$l(v)$ a $p(v)$ -- levý a pravý syn vrcholu $v$
  68 \:$L(v)$ a $P(v)$ -- levý a pravý podstrom vrcholu $v$
  69 \:$S(v)$ -- pøíslu¹ný podstrom s~koøenem $v$
  70 \:$h(v)$ -- hloubka stromu $S(v)$ -- délka nejdel¹í cesty z koøene do listu
  71 \endlist
  72
  73 \s{Definice:} {\I Binární vyhledávací strom} (BVS): Binární strom je vyhledávací,
  74 pokud v~ka¾dém vrcholu je ulo¾ena dvojice (klíè, hodnota) [ztoto¾níme vrchol s~klíèem]
  75 a pro v¹echny vrcholy platí: $\left ( \forall u \in L(v) : u < v \right ) $ $ \&$ $
  76 \left ( \forall u \in P(v) : u > v \right)$.
  77
  78 \s{Pøíklady binárních vyhledávacích stromù:}
  79
  80 \treepic{2}
  81
  82 Jak budou tedy vypadat operace {\it Find}, {\it Insert} a {\it Delete} na~binárním
  83 vyhledávacím stromu?
  84
  85 {\bo Find$(v,x)$:}
  86 \algo
  87 \:Pokud $v = \emptyset \Rightarrow$ vrátíme $\emptyset$.
  88 \:Pokud $v = x \Rightarrow$ vrátíme $v$.
  89 \:Pokud $v < x \Rightarrow$ vrátíme $\<Find>(p(v),x)$.
  90 \:Pokud $v > x \Rightarrow$ vrátíme $\<Find>(l(v),x)$.
  91 \endalgo
  92
  93 {\bo Insert$(v,x)$:}
  94 \algo
  95 \:Jako \<Find> a na~konci pøidáme list.
  96 \endalgo
  97
  98 {\bo Delete$(v)$:}
  99 \algo
 100 \:Pokud $v$ je list $\Rightarrow$ jednodu¹e list utrhneme.
 101 \:Pokud $v$ má jednoho syna $\Rightarrow$ vrchol \uv{vyøízneme}.
 102 \:Jinak má $v$ oba syny $\Rightarrow$ do vrcholu vlo¾íme minimum z $P(v)$, minimum u¾
 103 umíme smazat proto¾e je to buï list nebo má jen pravého syna.
 104 \endalgo
 105
 106 \s{Poznámka:} Pokud má vrchol $v$ pøi operaci {\it Delete} oba syny, je vlo¾ení minima
 107 z $P(v)$ ekvivalentní s~vlo¾ením maxima z $L(v)$.
 108
 109 \break
 110
 111 \s{Pøíklady operací  {\it Insert} a {\it Delete} na~BVS:}
 112 \treepic{1}
 113 \treepic{3}
 114
 115 Èasová slo¾itost v¹ech tøí operací je $\Theta(\<hloubka stromu>)$, co¾ mù¾e být
 116 $\Theta(n)$, kdy¾ budeme mít smùlu a strom bude (témìø) lineární spojový seznam.
 117 Takovéto degenerované stromy vzniknou snadno, napøíklad pøidáváním setøídìné
 118 posloupnosti. Naopak kdy¾ bude strom pìknì vyvá¾enì vystavìný, dostaneme slo¾itost
 119 $\Theta(\log{n})$. Vidíme tedy, ¾e slo¾itost operací stojí a padá s~hloubkou stromu.
 120 Proto by se nám líbilo, aby mìl ná¹ strom v¾dy hloubku $\Theta(\log{n})$. Podívejme se
 121 tedy, jak se dá navrhnout binární vyhledávací strom, aby tuto podmínku splòoval \dots
 122
 123 \h{Vyvá¾ené binární vyhledávací stromy}
 124
 125 \s{Definice:} {\I Dokonalá vyvá¾enost:} Strom je dokonale vyvá¾ený, pokud pro v¹echny
 126 jeho vrcholy platí: $\left \vert \vert L(v)\vert - \vert P(v)\vert \right \vert \leq 1
 127 $.
 128
 129 Takto definovaný binární strom bude mít urèitì logaritmickou hloubku. Jak takový strom
 130 ale konstruovat? To se nám podaøí buï staticky, nebo na~nìm budou operace dra¾¹í ne¾
 131 $\Theta(\log{n})$.
 132
 133 \s{Statická konstrukce dokonale vyvá¾eného BVS:} Vybereme prostøední prvek ze
 134 setøídìného pole (tedy medián posloupnosti) a dáme ho do~koøene stromu. Jeho syny pak
 135 vystavíme rekurzivnì z~levé a pravé pùlky pole. Celá konstrukce tedy trvá $\O(n)$.
 136
 137 \s{Lemma:} Buï {\it Insert} nebo {\it Delete} v dokonale vyvá¾eném BVS trvá $\Omega(n)$ (ve
 138 skuteènosti oba, ale dùkaz je o trochu obtí¾nìj¹í).
 139
 140 \proof Nech» $n=2^k-1$. Pak má dokonale vyvá¾ený BVS urèený tvar a je jednoznaèné,
 141 která hodnota je ve kterém vrcholu. Nech» nejmen¹í èíslo ve stromì je $x$ a nejvìt¹í je $x+n-1$.
 142
 143 Proveïme posloupnost operací $$\<Insert>(x+n), \<Delete>(x), \<Insert>(x+n+1),
 144 \<Delete>(x+1) \dots$$
 145 za ka¾dou dvojici operací se aspoò polovina listù posune o patro vý¹. Víme ¾e listù v na¹em stromì
 146 je $(n+1)/2$. Tedy aspoò jedna z operací {\it Insert} nebo {\it Delete} trvá $\Omega (n)$.
 147
 148 Vidíme tedy, ¾e to ná¹ problém pøíli¹ neøe¹í. Potøebovali bychom, aby se strom dal
 149 také efektivnì udr¾ovat. Zkusíme proto slab¹í podmínku:
 150
 151 \s{Definice:} {\I Hloubková vyvá¾enost:} Strom je hloubkovì vyvá¾ený, pokud pro
 152 v¹echny jeho vrcholy platí: $\left \vert h(L(v)) - h(P(v)) \right \vert \leq 1 $.
 153
 154 Stromùm s~hloubkovým vyvá¾ením se øíká {\I AVL stromy} (objeviteli je ru¹tí
 155 matematikové G. M. Adìµson-Veµskij a E. M. Landis, podle nich jsou také pojmenovány) a
 156 platí o~nich následující lemma:
 157
 158 \s{Lemma:} AVL strom na~$n$ vrcholech má hloubku $ \Theta(\log{n}) $.
 159
 160 \proof Uva¾me posloupnost $A_k = $ minimální poèet vrcholù AVL stromu hloubky $k$.
 161 Staèí ukázat, ¾e $A_k$ roste exponenciálnì.
 162
 163 Jak bude vypadat minimální AVL strom o $k$ hladinách? S poètem hladin urèitì poroste
 164 poèet vrcholù, proto pro ka¾dý vrchol budeme chtít, aby se hloubky jeho synù li¹ily.
 165 Tedy koøen bude mít syna hloubky $k-1$ a syna hloubky $k-2$, takové, ¾e jeho synové
 166 jsou minimální AVL stromy o daném poètu hladin.
 167
 168 Podívejme se na minimální AVL stromy:
 169 $$\eqalign{
 170 A_0 &= 1 \cr
 171 A_1 &= 2 \cr
 172 A_2 &= 4 \cr
 173 A_3 &= 7 \cr
 174 &\vdots \cr
 175 A_k &= 1 + A_{k - 1} + A_{k - 2}. \cr
 176 }$$
 177
 178 Rekurentní vzorec jsme dostali rekurzivním stavìním stromu hloubky $k$: nový koøen a 2
 179 podstromy o~hloubkách $k - 1$ a $k - 2$.
 180
 181 Indukcí bychom snadno dokázali, ¾e $A_n=F_{n+2}-1$ (kde $F_n$ je $n$-té Fibonacciho
 182 èíslo). My se v¹ak bez analýzy Fibonacciho posloupnosti obejdeme, proto¾e nám staèí
 183 dokázat, ¾e $A_k$ rostou exponenciálnì a nepotøebujeme pøesný vzorec pro hodnotu
 184 $A_k$.
 185
 186 Indukcí doká¾eme, ¾e $ A_k \geq 2^{k \over 2} $. První indukèní krok jsme si u¾
 187 ukázali, teï pro $ k \geq 2 $ platí: $ A_k = 1 + A_{k - 1} + A_{k - 2} > 2^{{k - 1}
 188 \over 2} + 2^{{k - 2} \over 2} = 2^{k \over 2} \cdot (2^{-{1 \over 2}} + 2^{-1}) \cong
 189 2^{k \over 2} \cdot 1.21 > 2^{k \over 2}.$
 190
 191 Tímto jsme dokázali, ¾e na~ka¾dé hladinì je minimálnì exponenciálnì vrcholù, co¾ nám
 192 zaruèuje hloubku $\O(\log{n})$. Druhou nerovnost nahlédneme zkoumáním $B_k$
 193 maximálního poètu vrcholù AVL stromu hloubky $k$.
 194 \qed
 195
 196 \bye