2009/11-stromy/11-stromy.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{11}{Vyhledávací stromy}{}
  12
  13 Pøedstavme si následující problém: potøebujeme si udr¾ovat urèitá setøídìná data, napøíklad slovník. Polo¾kami jsou uspoøádané dvojice (klíè, hodnota). Klíèe jsou unikátní a jsou to prvky nìjakého lineárnì uspoøádaného universa. Hodnoty mohou být libovolné.
  14
  15 Na na¹ich datech budeme chtít provádìt následující operace:
  16 \itemize\ibull
  17 \:{\it Insert} -- vlo¾it novou polo¾ku
  18 \:{\it Delete} -- smazat polo¾ku
  19 \:{\it Find} -- najít polo¾ku
  20 \:{\it Max $\&$ Min} -- vybrat polo¾ku s~nejvìt¹ím, resp. nejmen¹ím klíèem
  21 \:{\it Pred $\&$ Succ} -- vybrat polo¾ku s~klíèem nejbli¾¹ím men¹ím, resp. vìt¹ím
  22 \endlist
  23
  24 Jak by vypadalo nejjednodu¹¹í øe¹ení? Staticky bychom data mohli udr¾ovat v~setøídìném poli. Takové pole se vyrobí v~èase $\Theta(n \cdot \log{n})$. Operace {\it Find} by trvala $\Theta(\log{n})$ (vyhledávali bychom samozøejmì binárnì). Ale problém by nastal s~operacemi {\it Insert} a {\it Delete}, které by se takto implementovat nedaly, nebo by trvaly hodnì dlouho (napø. v~pøípadì {\it Insertu} bychom museli celé pole pøestavìt).
  25
  26 \s{Pozorování:} Proces binárního vyhledávání v~setøídìném poli se dá reprezentovat binárním vyhledávacím stromem.
  27
  28 \s{Definice:} {\I Binární strom:} Strom je binární, pokud je zakoøenìný a ka¾dý vrchol má nejvý¹e dva syny, u nich¾ rozli¹ujeme, který je levý a který pravý.
  29
  30 \s{Definice:} Pro vrchol $v$ znaèíme:
  31 \itemize\ibull
  32 \:$l(v)$ a $p(v)$ -- levý a pravý syn vrcholu $v$
  33 \:$L(v)$ a $P(v)$ -- levý a pravý podstrom vrcholu $v$
  34 \:$S(v)$ -- pøíslu¹ný podstrom s~koøenem $v$
  35 \:$h(v)$ -- hloubka stromu $S(v)$, neboli délka nejdel¹í cesty z koøene do listu
  36 \endlist
  37
  38 \s{Definice:} {\I Binární vyhledávací strom} (BVS): Binární strom je vyhledávací, pokud v~ka¾dém vrcholu je ulo¾ena dvojice (klíè, hodnota) [ztoto¾níme vrchol s~klíèem] a pro v¹echny vrcholy platí: $\left ( \forall u \in L(v) : u < v \right ) $ $ \&$ $ \left ( \forall u \in P(v) : u > v \right )$.
  39
  40 \s{Pøíklady binárních vyhledávacích stromù:}
  41
  42 \treepic{2}
  43
  44 \break
  45
  46 Jak budou tedy vypadat operace {\it Find}, {\it Insert} a {\it Delete} na~binárním vyhledávacím stromu?
  47
  48 {\bo Find$(v,x)$:}
  49 \algo
  50 \:Pokud $v = \emptyset \Rightarrow$ vrátíme $\emptyset$.
  51 \:Pokud $v = x \Rightarrow$ vrátíme $v$.
  52 \:Pokud $v < x \Rightarrow$ vrátíme $\<Find>(p(v),x)$.
  53 \:Pokud $v > x \Rightarrow$ vrátíme $\<Find>(l(v),x)$.
  54 \endalgo
  55
  56 {\bo Insert$(v,x)$:}
  57 \algo
  58 \:Jako \<Find> a na~konci pøidáme list.
  59 \endalgo
  60
  61 {\bo Delete$(v)$:}
  62 \algo
  63 \:Pokud $v$ je list $\Rightarrow$ jednodu¹e list utrhneme.
  64 \:Pokud $v$ má jednoho syna $\Rightarrow$ vrchol \uv{vyøízneme}.
  65 \:Jinak má $v$ oba syny $\Rightarrow$ do vrcholu vlo¾íme minimum z $P(v)$, co¾ bude list, a ten utrhneme.
  66 \endalgo
  67
  68 \s{Poznámka:} Pokud má vrchol $v$ pøi operaci {\it Delete} oba syny, je vlo¾ení minima z $P(v)$ ekvivalentní s~vlo¾ením maxima z $L(v)$.
  69
  70 \s{Pøíklady operací  {\it Insert} a {\it Delete} na~BVS:}
  71 \treepic{1}
  72 \treepic{3}
  73
  74 \break
  75 Èasová slo¾itost v¹ech tøí operací je $\Theta(\<hloubka stromu>)$, co¾ mù¾e být $\Theta(n)$, kdy¾ budeme mít smùlu a strom bude (témìø) lineární spojový seznam, nebo $\Theta(\log{n})$ kdy¾ bude strom pìknì vyvá¾enì vystavìný. Vidíme tedy, ¾e slo¾itost operací stojí a padá s~hloubkou stromu. Proto by se nám líbilo, aby mìl ná¹ strom v¾dy hloubku $\Theta(\log{n})$. Podívejme se tedy, jak se dá navrhnout binární vyhledávací strom, aby tuto podmínku splòoval \dots
  76
  77 \h{Vyvá¾ené binární vyhledávací stromy}
  78
  79 \s{Definice:} {\I Dokonalá vyvá¾enost:} Strom je dokonale vyvá¾ený, pokud pro v¹echny jeho vrcholy platí: $\left \vert \vert L(v)\vert - \vert P(v)\vert \right \vert \leq 1 $.
  80
  81 Takto definovaný binární strom bude mít urèitì logaritmickou hloubku. Jak takový strom ale konstruovat? To se nám podaøí buï staticky, nebo na~nìm budou operace dra¾¹í ne¾ $\Theta(\log{n})$.
  82
  83 \s{Statická konstrukce dokonale vyvá¾eného BVS:} Vybereme prostøední prvek ze setøídìného pole (tedy medián posloupnosti) a dáme ho do~koøene stromu. Jeho syny pak vystavíme rekurzivnì z~levé a pravé pùlky pole. Celá konstrukce tedy trvá $\O(n)$.
  84
  85 Vidíme tedy, ¾e to ná¹ problém pøíli¹ neøe¹í. Potøebovali bychom, aby se strom dal také efektivnì udr¾ovat. Zkusíme proto slab¹í podmínku:
  86
  87 \s{Definice:} {\I Hloubková vyvá¾enost:} Strom je hloubkovì vyvá¾ený, pokud pro v¹echny jeho vrcholy platí: $\left \vert h(L(v)) - h(P(v)) \right \vert \leq 1 $.
  88
  89 Stromùm s~hloubkovým vyvá¾ením se øíká {\I AVL stromy} (objeviteli je ru¹tí matematikové G. M. Adelson-Velsky a E. M. Landis, podle nich jsou také pojmenovány) a platí o~nich následující lemma:
  90
  91 \s{Lemma:} AVL strom na~$n$ vrcholech má hloubku $ \Theta(\log{n}) $.
  92
  93 \proof
  94 Uva¾me posloupnost $A_k = $ minimální poèet vrcholù AVL stromù hloubky $k$. Staèí ukázat, ¾e $A_k$ roste exponenciálnì. Podívejme se na minimální AVL stromy:
  95 $$\eqalign{
  96 A_0 &= 1 \cr
  97 A_1 &= 2 \cr
  98 A_2 &= 4 \cr
  99 A_3 &= 7 \cr
 100 &\vdots \cr
 101 A_k &= 1 + A_{k - 1} + A_{k - 2}. \cr
 102 }$$
 103
 104 Rekurentní vzorec jsme dostali rekurzivním stavìním stromu hloubky $k$: nový koøen a 2 podstromy o~hloubkách $k - 1$ a $k - 2$.
 105
 106 Vidíme tedy, ¾e $A_n = F_{n + 2} - 1$. (Mù¾eme dokázat napø. indukcí.)
 107 Teï nám ji¾ staèí dokázat, ¾e posloupnost $A_k$ roste exponenciálnì S výhodou mù¾eme vyu¾ít toho, ¾e na první pøedná¹ce jsme si ji¾ dokázali, ¾e Fibonacciho èísla rostou exponenciálnì. Nicménì pro zapomnìtlivé mù¾eme dùkaz ve struènosti zopakovat:
 108
 109 Indukcí doká¾eme, ¾e $ A_k \geq 2^{k \over 2} $.
 110 První indukèní krok jsme si u¾ ukázali, teï pro $ k \geq 2 $ platí:
 111 $ A_k = 1 + A_{k - 1} + A_{k - 2} > 2^{{k - 1} \over 2} + 2^{{k - 2} \over 2} = 2^{k \over 2} \cdot (2^{-{1 \over 2}} + 2^{-1}) \cong 2^{k \over 2} \cdot 1.21 > 2^{k \over 2}.$
 112
 113 Tímto jsme dokázali, ¾e na~ka¾dé hladinì je minimálnì exponenciálnì vrcholù, co¾ nám zaruèuje hloubku $ \Theta(\log{n})$.
 114 \qed
 115
 116 \bye