9-stromy/9-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 \def\abpic#1{
  11 \medskip
  12 \centerline{\epsfxsize=0.7\hsize\epsfbox{abpic/#1.eps}}
  13 \medskip
  14 }
  15 \def\abpics#1#2{
  16 \medskip
  17 \centerline{\epsfxsize=0.4\hsize\epsfbox{abpic/#1.eps}\qquad\epsfxsize=0.4\hsize\epsfbox{abpic/#2.eps}}
  18 \medskip
  19 }
  20
  21 \prednaska{7}{Vyhledávací stromy}{zapsali M. Øezáè, ©. Masojídek, B. Urbancová}
  22
  23 \h{Vyvá¾ené binární vyhledávací stromy}
  24
  25 V minulé kapitole jsme se zabývali problematikou pøidávání a ubírání prvkù
  26 binárního vyhledávacího stromu a jeho slo¾itostí a zjistili, ¾e v¹e zále¾í
  27 na~hloubce stromu. Víme, ¾e chceme hloubku logaritmickou, ale jak ji mù¾eme
  28 udr¾et pøi~operacích? Øe¹ením je následující definice:
  29
  30 \s{Definice:} {\I Dokonale vyvá¾ení} je takové vyvá¾ení, ve~kterém pro v¹echny vrcholy~$v$ platí $\left\vert \vert L(v)\vert - \vert P(v)\vert \right \vert \leq 1 $.
  31
  32 Toto nám jistì zaji¹»uje logaritmickou hloubku, ale je velmi pracné na udr¾ování.
  33 Zkusíme proto slab¹í podmínku:
  34
  35 \s{Definice:} {\I Hloubkové vyvá¾ení} je takové vyvá¾ení, ve~kterém pro v¹echny vrcholy~$v$ platí $\left \vert h(L(v)) - h(P(v)) \right \vert \leq 1 $.
  36 Stromùm s hloubkovým vyvá¾ením se øíká {\I AVL stromy} a platí o nich následující lemma.
  37
  38 \s{Lemma:} AVL strom o $n$ vrcholech má hloubku $ \O(\log{n}) $.
  39
  40 \proof
  41 Uva¾me $a_k = $ minimální poèet vrcholù AVL stromu o~hloubce $k$.
  42 Lehce spoèteme:
  43 $$\eqalign{
  44 a_0 &= 0 \cr
  45 a_1 &= 1 \cr
  46 a_2 &= 2 \cr
  47 &\vdots \cr
  48 a_k &= 1 + a_{k - 1} + a_{k - 2}. \cr
  49 }$$
  50
  51 Rekurentní vzorec jsme dostali rekurzivním stavìním stromu hloubky $k$: nový koøen a 2 podstromy o hloubce $k - 1$ a $k - 2$.
  52
  53 Indukcí doká¾eme, ¾e $ a_k \geq 2^{k \over 2} $.
  54 První indukèní krok jsme si u¾ ukázali, teï pro $ k \geq 2 $ platí:
  55 $ 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} $
  56
  57 Tímto jsme dokázali, ¾e na ka¾dé hladinì je minimálnì exponenciálnì vrcholù, co¾ nám zaruèuje hloubku $ \O(\log{n})$
  58 \qed
  59
  60 \break
  61 \s{Operace s AVL stromy}
  62
  63 \<Find> se neli¹í od~operace find v~binárních stromech.
  64
  65 Dùraz klademe na operace \<Insert> a \<Delete>, proto¾e pøi~nich musíme o¹etøit udr¾ení struktury AVL~stromù.
  66
  67 První nutnou podmínkou je, ¾e si musíme {\I pamatovat stav} v~ka¾dém vrcholu tohoto stromu. A~to {\I vyvá¾ení} hloubky jeho podstromù.
  68
  69 Umluvíme~se napø. na~tomto oznaèení:
  70
  71 \>Dostaneme tøi typy vrcholù, které se mohou v~AVL~stromu vyskytnout:
  72 \itemize\ibull
  73 \:{\I Vrchol typu~$\oplus$}, pokud je pravý podstrom hlub¹í
  74 \:{\I Vrchol typu~$\ominus$}, pokud je levý podstrom hlub¹í a
  75 \:{\I Vrchol typu~$\odot$ (nulou)}, který má oba syny shodné hloubky.
  76 \endlist
  77
  78 \s {Sestavení} \rm AVL stromu:
  79
  80 Postupujeme po~struktuøe binárního stromu od~listù ke~koøeni a~kontrolujeme, zda jsou vrcholy v~jednom ze~tøí uvedených stavù. Pokud ne, opravíme strom operací jménem rotace.
  81
  82 \s {Rotace}
  83 \treepic{4}
  84 \treepic{5}
  85
  86 Jde o~pøevrácení hrany mezi pùvodním otcem (koøenem podstromu) a nevyvá¾eným vrcholem tak, aby byli i po pøeskupení synové vzhledem k~otcùm správnì uspoøádáni.
  87
  88
  89 \s {Insert} \rm - vlo¾ení vrcholu do~AVL~stromu.
  90
  91 Vlo¾íme jej jako list. Nový list má v¾dy \uv{znaménko} nula $\odot$. Pøedpokládáme, ¾e patøí nalevo od posledního otce. Podíváme~se na~znaménko jeho otce:
  92 \itemize\ibull
  93 \:{\I mìl~$\odot$ (nemìl syna) $\rightarrow$ teï má~$\ominus$}, po struktuøe stromu nahoru posíláme informaci, ¾e se podstrom prohloubil o~1, co¾ mù¾e mít samozøejmì vliv na~znaménka vrcholù na~cestì ke~koøeni.
  94 \:{\I mìl~$\oplus$ (mìl pravého syna, který je listem) $\rightarrow$ teï má~$\odot$}, hloubka podstromu se~nemìní
  95 \:{\I mìl $\ominus$} -- nenastane, proto¾e v binární struktuøe nemohou být dva leví synové
  96 \endlist
  97 \>Pøipadne-li pøidaný list napravo, øe¹íme zrcadlovì.
  98
  99 \treepic{6}
 100 \treepic{7}
 101
 102 \>{\I Prohloubil-li se strom} vlo¾ením nového listu, musíme pracovat s vyvá¾ením:
 103 \itemize\ibull
 104 \:Informace o~prohloubení pøi¹la zleva {\I do~vrcholu typu~$\odot$} $\rightarrow$ mìní jej na~vrchol se~znaménkem~$\ominus$ a informace o~prohloubení je tøeba poslat o~úroveò vý¹.
 105 \:Informace o~prohloubení pøi¹la zleva {\I do~vrcholu typu~$\oplus$} $\rightarrow$ mìní jej na~vrchol se~znaménkem~$\odot$, hloubka je vyrovnána, dál nic neposíláme.
 106 \:Informace o~prohloubení pøi¹la zleva {\I do vrcholu s~$\ominus$} $\rightarrow$
 107
 108 \>rozebereme na~tøi pøípady podle znaménka vrcholu, ze~kterého pøi¹la informace o~prohloubení:
 109 \itemize\ibull
 110 \:Informace pøi¹la {\I z~vrcholu typu~$\ominus$} $\rightarrow$ provedeme rotaci doprava tak, ¾e novým koøenem se~stane vrchol~$y$, ze~kterého pøi¹la informace o~prohloubení.
 111
 112 \treepic{8}
 113
 114 {\I Pozorování 1:} znaménko vrcholù~$y$ a~$x$ je~$\odot$\
 115
 116 {\I Pozorování 2:} hloubka pøed vkládáním byla $h+1$ a~nyní je také $h+1$, tedy nemusíme dále posílat informaci o~prohloubení a mù¾eme skonèit
 117 \:Informace pøi¹la {\I z~vrcholu typu~$\oplus$}
 118 \itemize\ibull
 119 \:uva¾me je¹te vrchol~$z$ jako pravého syna vrcholu~$y$, ze~kterého pri¹la informace o~prohloubení, a~jeho podstromy~$B$ a~$C$
 120 \:vrcholy~$B$ a~$C$ mají hloubku~$h$ nebo $h-1$ $\rightarrow$ oznaème~ji tedy $h-$ (to zøejmì proto¾e vrchol~$y$ má znaménko~$\oplus$, tedy jeho pravý podstrom s~koøenem~$z$ má hloubku~$h+1$ )
 121 \:provedeme dvojrotaci tak, ¾e novým koøenem se stane vrchol~$z$
 122 \endlist
 123 \treepic{9}
 124
 125 {\I Pozorování 1:} znaménko vrcholu~$z$ bude~$\odot$\
 126
 127 {\I Pozorování 2:} znaménka vrcholu~$x$ a~$y$ se~dopoèítají v~závislosti na~hloubce~$B$ a~$C$\
 128
 129 {\I Pozorování 3:} rozdíl hloubky pravého a~levého podstromu bude u~tìchto vrcholù $0$ nebo~$1$\
 130
 131 {\I Pozorování 4:} hloubka pøed vkládáním byla $h+2$ a~nyní je také $h+2$, tedy nemusíme dále posílat informaci o~prohloubení a~mù¾eme skonèit
 132 \:informace pøi¹la {\I z~vrcholu typu~$\odot$} -- to nemù¾e nastat, proto¾e v~tom pøípadì by ne¹lo o~prohloubení
 133 \endlist
 134 \endlist
 135
 136 \s {Delete} -- odebrání vrcholu z~AVL~stromu
 137 \> Buï ma¾eme list nebo ma¾eme vrchol, který mìl nìjaké syny.
 138
 139 \itemize\ibull
 140 \:pokud ma¾eme list, podíváme~se na~typ otce. Pøedpokládáme mazání levého syna.
 141 \itemize\ibull
 142 \:byl typu $\ominus$ (nemìl pravého syna) $\rightarrow$ zmìní~se na~$\odot$ (vrchol teï nemá ¾ádné syny)
 143 \:byl typu $\odot$ (mìl oba syny) $\rightarrow$ zmìní~se na~$\oplus$
 144 \endlist
 145 (ma¾eme-li pravý list, øe¹íme zrcadlovì)
 146 \:ma¾eme vrchol s~jedním (levým nebo pravým) synem $\rightarrow$ syn nastupuje na~místo otce a~získává typ~$\odot$\
 147
 148 \>V~obou pøípadech posílame informaci o~zmìnì hloubky stromu...
 149 \:mazaný vrchol mìl oba syny (listy) $\rightarrow$ vybereme jednoho ze~synù na~místo smazaného otce. Hloubka se nemìní.
 150 \:mazaný vrchol mìl syny podstromy $\rightarrow$ na~jeho místo vezmeme nejvìt¹í prvek levého podstromu (nebo nejmen¹í prvek pravého podstromu) a od~odebraného (nahrazujícího) listu kontrolujeme vyvá¾ení podstromu.
 151 \endlist
 152
 153
 154
 155
 156 \>{\I Úprava vyvá¾ení} stromu po~odebrání listu z~podstromu
 157 \itemize\ibull
 158 \:informace o~zmìnì hloubky pøi¹la z~levého podstromu do~vrcholu typu~$\odot$ $\rightarrow$ vrchol se~zmìní na~$\oplus$ a~dál se hloubka nemìní
 159
 160 \:informace pøi¹la zleva do~vrcholu s~$\ominus$ $\rightarrow$ mìní~se na~$\odot$ a~posíláme informaci o~zmìnì hloubky.
 161
 162 \treepic{10}
 163 \treepic{11}
 164
 165 \:problémová situace nastává, kdy¾ informace o~zmìnì pøi¹la zleva do~vrcholu se~znaménkem~$\oplus$
 166 \endlist
 167 \>Rozebereme na~tøi~pøípady podle znaménka pravého syna nevyvá¾eného vrcholu
 168 \itemize\ibull
 169 \:{\I pravý syn je typu~$\oplus$} $\rightarrow$ provedeme rotaci vlevo, novým koøenem se~stává~$y$ (pravý syn), oba vrcholy zmìní typ na~$\odot$ a~posíláme informaci o~zmìnì hloubky.
 170
 171 \treepic{12}
 172
 173 \:{\I pravý syn je typu~$\odot$} $\rightarrow$ provedeme opìt rotaci vlevo, koøenem se~stává~$y$, následnì se u~$y$ zmìní typ na~$\ominus$ , u~vrcholu~$x$ se typ nemìní. Hloubka stromu se~nemìní, tudí¾ není tøeba posílat informaci.
 174
 175 \treepic{12y}
 176
 177 \:{\I pravý syn je typu~$\ominus$} $\rightarrow$ v~tomto pøípadì uva¾ujeme je¹tì vrchol~$z$ jako levého syna vrcholu~$y$, s~podstromy $B$ a~$C$, podstromy $B$ a~$C$ mají hloubku~$h$ nebo~$h-1$. Provedeme dvojrotaci, napøed vpravo rotujeme vrcholy $z$ a~$y$, potom vlevo vrcholy~$x$ a~$z$ tak, ¾e se $z$ stane novým koøenem, typ vecholu~$x$ bude potom~$\ominus$ nebo~$\odot$, typ~$y$~$\oplus$ nebo~$\odot$ (podle toho, jaké znaménko mìl pùvodnì vrchol~$z$), typ~$z$ bude~$\odot$ a~opìt posíláme informaci o~zmìnì hloubky stromu.
 178
 179 \treepic{13}
 180 \endlist
 181
 182 \h{Obecné vyhledávací stromy}
 183
 184 Pøi ulo¾ení dat na~disku se~sna¾íme, aby~se ètení z~disku provádìlo pokud mo¾no
 185 co nejménìkrát a~nezále¾í nám tolik na~tom, kolik operací se~vykoná v~jednom
 186 uzlu. (Èasovì je operace porovnávání zanedbatelná oproti ètení z~disku.)
 187
 188 Hodilo by se nám tedy mít uzly velké tøeba tak, jako je velká jedna stránka
 189 cache \dots
 190
 191 \s{Definice:} {\I $(a,b)$-strom} pro parametry $a,b$, $a \geq 2$, $b\geq 2a - 1$ je zakoøenìný strom s~uspoøádanými syny a~vnìj¹ími vrcholy, pro který platí
 192 následující axiomy:
 193 \numlist\nparen
 194 \:Data jsou ulo¾ena ve~vnitøních vrcholech a~ka¾dý vrchol obsahuje o~1 ménì klíèù ne¾ má synù.
 195 \:Platí stromové uspoøádání, tedy ¾e $ A < x_1 < B < x_2 < C < x_3 < D $.
 196 \:Koøen má $2$ a¾~$b$ synù, ostatní vnitøní vrcholy $a$ a¾ $b$ synù.
 197 \:V¹echny vnìj¹í vrcholy jsou ve~stejné hloubce (vnìj¹í vrchol$=$list).
 198 \endlist
 199 \>{\I Poznámka:} kdekoli~by mohl být syn a~není, pøipojíme vrchol, kterému øíkáme vnìj¹í vrchol. Mù¾eme si to pøedstavit tøeba jako NULL-pointer.
 200
 201 \abpic{ab-strom11}
 202
 203 \s{Lemma:} $(a,b)$-strom na~$n$~vrcholech má hloubku~$O(\log_a n)$.
 204
 205 \proof
 206 Zjistíme jeho minimální poèet listù (oznaème jej $m$): ka¾dý vrchol a¾ na~koøen má alespoò $a$ synù, hloubku si oznaèíme~$d$ $\rightarrow$
 207 $$m\geq~a^{(d -1)}$$
 208 $$\log_a m \geq d -1$$
 209 $$d \leq 1+ \log_a m$$
 210 \centerline{co¾ je øádovì  $O(\log_a n)$, kde $n$ je poèet vrcholù.}\
 211
 212 \s{Operace s (a,b)-stromy:}
 213
 214 \s{Find}
 215 \item{-}V¾dy zjistíme, mezi které 2 klíèe hledaný vrchol patøí, a potom se zanoøíme hloubìji.\
 216
 217 \>Èasová slo¾itost nalezení prvku v $(a,b)$-stromu je $O(\log b \cdot \log_a n)$, kde $\log b$ je èas strávený na~jednom vrcholu pro zji¹tení, mezi které 2 vrcholy hledaný patøí, $\log_a n$ je hloubka stromu.
 218
 219 \s{Insert}
 220
 221 \>Jako Find, pøièem¾ jestli¾e nena¹el, skonèí na~posledním patøe a~pøidáme klíè
 222 \itemize\ibull
 223 \:pokud pøidáním nepøesáhneme maximální poèet klíèù, mù¾eme\hfil\break skonèit
 224 \abpic{insert1}
 225 \:pokud pøidáním pøesáhneme maximální poèet klíèù
 226 \endlist
 227 \algo
 228 \:rozdìlíme vrchol na~3 èásti: $L$,$x$,$P$
 229 \:$L$ a $P$ jsou nové vrcholy
 230 \:$x$ je hodnota mezi $L$ a $P$, kterou vlo¾íme o patro vý¹ jako klíè oddìlující novì vzniklé vrcholy $L$ a $P$
 231 \:tím jsme pøevedli problém o patro vý¹ a opakujeme algoritmus
 232 \endalgo
 233
 234 \abpics{b-klicu1}{b-klicu2}
 235
 236 \s{Poznámka:} Jestli¾e se dostaneme a¾ do koøene, rozdìlí se koøen na dvì
 237 èásti, vznikne nám nový koøen se dvìma syny (co¾ je povoleno právì kvùli tomuto
 238 pøípadu) a celému stromu vzroste hloubka o jedna.
 239
 240 \s{Korektnost:}
 241 Potøebujeme, aby
 242 $$\vert L\vert \geq a-1$$
 243 $$\vert P\vert \geq a-1$$
 244 po seètení obou nerovností a~priètení 1 na~obì strany rovnice:
 245 $$\vert L\vert +\vert P\vert +1\geq 2a-2+1=2a-1$$
 246 pravá strana je rovna $b$ a~to podle definice $\geq 2a-1$.
 247
 248 \s{Èasová slo¾itost:} vkládání prvku do $(a,b)$-stromu je $O(b\cdot \log_a n)$.
 249
 250 \s{Delete}
 251 \item{-} pøevedeme na~delete z~listu (stejný postup jako u~binárního stromu: jestli¾e to není list, prohodíme tuto hodnotu s~nejmen¹í hodnotou podstromu jeho pravého syna) -- v tomto pøípadì na~klíè posledního vnitøního vrcholu, proto¾e listy jsou vnìj¹í vrcholy bez dat.
 252 \itemize\ibull
 253 \:pokud má vrchol, ze~kterého odebíráme, stále $a-1$ klíèù, mù¾eme skonèit
 254 \:pokud má vrchol $V$, ze~kterého odebíráme, $a-2$ klíèù a~jeho levý sousední vrchol $L$ alespoò $a$ klíèù (klíè otce oddìlující tyto vrcholy oznaème $x$):
 255 \endlist
 256 \algo
 257 \:sma¾eme nejvìt¹í klíè levého sousedního vrcholu $L$ a~nahradíme tím klíè otce obou vrcholù (nahradíme $x$ za~tuto hodnotu)
 258 \:pùvodní klíè otce ($x$) pøidáme jako nejmen¹í klíè odebíranému vrcholu~$V$
 259 \:tím mají oba tyto vrcholy $a-1$ klíèù a mù¾eme skonèit
 260 \endalgo
 261 \abpics{delete21}{delete22}
 262 \itemize\ibull
 263 \:pokud má vrchol $V$, z kterého odebíráme, $a-2$ klíèù a jeho levý sousední vrchol $L$ má $a-1$ klíèù (klíè otce oddìlující tyto vrcholy oznaème $x$):
 264 \endlist
 265 \algo
 266 \:slouèíme $V$,$x$,$L$ do jednoho vrcholu
 267 \:tím jsme problém pøevedli o patro vý¹ a opakujeme algoritmus \par
 268 \endalgo
 269 \abpics{delete31}{delete32}
 270
 271 \>{\I Poznámka:} Dojdeme-li takto a¾ do koøene, na místo klíèe odebraného z koøene lze pou¾ít nejmen¹í nebo nejvìt¹í klíè novì slouèeného podstromu. Ten odebrat lze, proto¾e po slouèení (které bylo pøíèinou této situace), je v nejni¾¹ím vrcholu $2a-2$ klíèù.
 272
 273
 274 \>{\I Èasová slo¾itost:} $$O(b\cdot \log_a n)$$
 275
 276 \bye