7-stromy/7-stromy.tex

   1 \input ../lecnotes.tex
   2
   3 \prednaska{7}{Stromy}{zapsali Miroslav Øezáè, ©tìpán Masojídek, Barbora Urbancová}
   4
   5 \h{Binární}
   6
   7 V minulé kapitole jsme se zabývali problematikou pøidávání a ubírání prvkù binárního stromu a jeho slo¾itostí a zjistili, ¾e v¹e zále¾í na~hloubce stromu. Víme, ¾e chceme hloubku logaritmickou, ale jak ji mù¾eme udr¾et pøi~operacích? Øe¹ením jsou
   8
   9
  10 \h{AVL stromy}
  11
  12 tedy stromy, hloubka jejich¾ pravého a levého podstromu se~li¹í maximálnì o~jednotku
  13 \par
  14
  15 \> {\I Operace s AVL stromy:}
  16
  17
  18 \s {FIND}
  19
  20 \> se~neli¹í od~operace find v~binárních stromech.\
  21
  22
  23 Dùraz klademe na operace \it INSERT \rm a \it DELETE \rm , proto¾e pøi~nich musíme o¹etøit udr¾ení struktury AVL~stromù..
  24
  25
  26
  27 První nutnou podmí podmínkou je, ¾e si musíme \bf pamatovat stav \rm v~ka¾dém vrcholu tohoto stromu. A~to jednak hladinu alias \bf hloubku\rm , ve~které se vrchol vyskytuje, tedy vzdálenost tohoto vrcholu od~koøene stromu, a~za~druhé \bf vyvá¾ení \rm hloubky jeho podstromù.
  28 Umluvíme~se napø. na~pravidle, ¾e pokud je levý podstrom hlub¹í, vrchol má hodnotu minus $\ominus$ a pokud je pravý podstrom hlub¹í, vrchol má hodnotu plus $\oplus$.
  29
  30 \>Tím dostáváme tøi typy vrcholù, které se mohou v~AVL~stromu vyskytnout:
  31
  32 \item{$\bullet$}\it Vrchol se~znaménkem~$\oplus$ \rm
  33
  34 \item{$\bullet$}\it Vrchol se~znaménkem~$\ominus$ \rm a
  35
  36 \item{$\bullet$}\it Vrchol se~znaménkem~$\odot$ (nulou), \rm který má oba syny schodné hloubky.
  37
  38
  39 \s {SESTAVENÍ} \rm AVL stromu:
  40
  41 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 ho operací jménem rotace.
  42
  43 \s {Rotace}
  44 \vglue 2 in
  45 \centerline{Prosím vlo¾it obrázek ``Rotace".}
  46
  47 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.
  48
  49
  50 \s {INSERT} \rm - vlo¾ení vrcholu do~AVL~stromu.
  51
  52 Vlo¾íme jej jako list. Nový list má v¾dy "znaménko" nula $\odot$. Pøedpokládáme, ¾e patøí nalevo od posledního otce. Podíváme~se na~znaménko jeho otce:
  53 \itemize\ibull
  54 \: \bf mìl~$\odot$ (nemìl syna) $\rightarrow$ teï má~$\ominus$ \rm , 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.
  55 \: \bf mìl~$\oplus$ (mìl pravého syna, který je listem) $\rightarrow$ teï má~$\odot$ \rm , hloubka podstromu se~nemìní
  56 \: \bf mìl $\ominus$ \rm $\leftarrow$ nenastane, proto¾e v binární struktuøe nejmohou být dva leví synové
  57 \par Pøipadne-li pøidaný list napravo, øe¹íme zrcadlovì.
  58 \endlist
  59 \vglue 2 in
  60
  61
  62 \centerline{Prosím vlo¾it obrázek ``Pøidání listu samotné''.}
  63
  64
  65 \>\bf Prohloubil-li se strom \rm vlo¾ením nového listu, musíme pracovat s vyvá¾ením:
  66 \algo
  67 \: informace o~prohloubení pøi¹la zleva \bf do~vrcholu se~znam.~$\odot$ \rm $\rightarrow$ mìní jej na~vrchol se~znaménkem~$\ominus$ a informace o~prohloubení je tøeba poslat o~úroveò vý¹
  68 \: informace o~prohloubení pøi¹la zleva \bf do~vrcholu se~znam.~$\oplus$ \rm $\rightarrow$ mìní jej na~vrchol se~znaménkem~$\odot$, hloubka je vyrovnána, dál nic neposíláme
  69 \: informace o~prohloubení pøi¹la zleva \bf do vrcholu s~$\ominus$ $\rightarrow$\rm
  70 \endalgo
  71
  72 \> $\rightarrow$ rozebereme na~tøi pøípady podle znaménka vrcholu, ze~kterého pøi¹la informace o~prohloubení.
  73 \itemize\ibull
  74 \: informace pøi¹la \bf z~vrcholu se~znaménkem~$\ominus$\rm $\rightarrow$ provedeme rotaci doprava tak, ¾e novým koøenem se~stane vrchol~$y$, ze~kterého pøi¹la informace o~prohloubení
  75 \vglue 2 in
  76 \centerline{Prosím vlo¾it obrázek ``y je $\ominus$"}
  77 {\I Pozorování 1:} znaménko vrcholù~$y$ a~$x$ je~$\odot$\
  78
  79 {\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
  80 \: informace pøi¹la \bf z~vrcholu se~znaménkem~$\oplus$\rm
  81 \itemitem{-}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$
  82 \itemitem{-} 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$ )
  83 \itemitem{-}provedeme dvojrotaci tak, ¾e novým koøenem se~stane vrchol~$z$
  84 \vglue 2 in
  85
  86 \centerline{Prosím vlo¾it obrázek ``$y$ jako $\oplus$''}
  87
  88
  89 {\I Pozorování 1:} znaménko vrcholu~$z$ bude~$\odot$\
  90
  91 {\I Pozorování 2:} znaménka vrcholu~$x$ a~$y$ se~dopoèítají v~závislosti na~hloubce~$B$ a~$C$\
  92
  93 {\I Pozorování 3:} rozdíl hloubky pravého a~levého podstromu u~tìchto vrcholù bude~$0$ nebo~$1$\
  94
  95 {\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
  96 \: informace pøi¹la \bf z~vrcholu se~znaménkem~$\odot$ \rm $\leftarrow$ to nemù¾e nastat, proto¾e v~tom pøípadì by ne¹lo o~prohloubení
  97 \endlist
  98
  99
 100 \s {DELETE} \rm - odebrání vrcholu z~AVL~stromu
 101
 102
 103 \> Buï ma¾eme list nebo ma¾eme vrchol, který mìl nìjaké syny.
 104
 105 \itemize\ibull
 106 \: pokud ma¾eme list, podíváme~se na~znaménko otce.  Pøedpokládáme mazání levého syna.
 107 \itemize\ibull
 108 \: mìl znaménko $\ominus$ (nemìl pravého syna) $\rightarrow$ zmìní~se na~$\odot$ (vrchol teï nemá ¾ádné syny)
 109 \: mìl znaménko $\odot$ (mìl oba syny) $\rightarrow$ zmìní~se na~$\oplus$
 110 \endlist
 111 (ma¾eme-li pravý list, øe¹íme zrcadlovì)
 112 \: ma¾eme vrchol s~jedním (levým nebo pravým) synem $\rightarrow$ syn nastupuje na~místo otce a~získává zn.~$\odot$\
 113
 114 \> V~obou pøípadech posílame informaci o~zmìnì hloubky stromu..
 115 \: mazaný vrchol mìl oba syny (listy) $\rightarrow$ vybereme jednoho ze~synù na~místo smazaného otce. Hloubka se nemìní.
 116 \: 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.
 117 \endlist
 118
 119
 120
 121
 122 \bf Úprava vyvá¾ení \rm stromu po~odebrání listu z~podstromu
 123 \algo
 124 \: informace o~zmìnì hloubky pøi¹la z~levého podstromu do~vrcholu se~znaménkem $\odot$ $\rightarrow$ vrchol se~zmìní na~$\oplus$ a~dál se hloubka nemìní
 125
 126 \: informace pøi¹la zleva do~vrcholu s~$\ominus$ $\rightarrow$ mìní~se na~$\odot$ a~posíláme informaci o~zmìnì hloubky.
 127
 128 \: problémová situace nastává, kdy¾ informace o~zmìnì pøi¹la zleva do~vrcholu se~znaménkem~$\oplus$~$\rightarrow$
 129 \endalgo
 130 \> $\rightarrow$ rozebereme na~tøi~pøípady podle znaménka pravého syna nevyvá¾eného vrcholu
 131 \itemize\ibull
 132 \: pravý syn má znaménko~$\oplus$ $\rightarrow$ provedeme rotaci vlevo, novým koøenem se~stává~$y$ (pravý syn), oba vrcholy zmìní znaménko na~$\odot$ a~posíláme informaci o~zmìnì hloubky
 133 \vglue 2 in
 134 \centerline{Prosím vlo¾it obrázek ``opaèný syn má $\oplus$''}
 135
 136 \: pravý syn má znaménko~$\odot$ $\rightarrow$ provedeme opìt rotaci vlevo, koøenem se~stává~$y$, následnì se u~$y$ zmìní znaménko na~$\ominus$ , u~vrcholu~$x$ se znaménko nemìní. Hloubka stromu se~nemìní, tudí¾ není tøeba posílat informaci..
 137 \vglue 2 in
 138 \centerline{Prosím vlo¾it obrázek ``opaèný syn má $\odot$''}
 139
 140 \: pravý syn má znaménko $\ominus$
 141 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, znaménko vecholu~$x$ bude potom~$\ominus$ nebo~$\odot$, znaménko~$y$~$\oplus$ nebo~$\odot$ (podle toho, jaké znaménko mìl pùvodnì vrchol~$z$), znaméko~$z$ bude~$\odot$ a~opìt posíláme informaci o~zmìnì hloubky stromu.
 142 \vglue 2 in
 143 \centerline{Prosím vlo¾it obrázek ``opaèný syn má $\ominus$''}
 144 \endlist
 145
 146 \h{Obecné stromy}
 147
 148 (Stromy s více vìtvemi)
 149
 150 \>\it Proè se tímto zabývat? \rm
 151 \par
 152 Pøi ulo¾ení dat na~disku se~sna¾íme, aby~se ètení z~disku provádìlo pokud mo¾no co nejménìkrát a~nezále¾í nám tolik na~tom, kolik operací se~vykoná v~jednom uzlu. (Èasovì je operace porovnávání zanedbatelná oproti ètení z~disku)
 153
 154
 155 \s {Def:} \bf (a,b) strom \rm 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í:
 156 \par
 157 \> (pozn.: kdekoli~by mohl být syn a~není, pøipojíme vrchol, kterému øíkáme vnìj¹í vrchol)
 158
 159
 160 \item{Ax 1)} data jsou ulo¾ena ve~vnitøních vrcholech a~ka¾dý vrchol obsahuje o~1 ménì klíèù ne¾ má synù
 161 \item{Ax 2)} platí stromové uspoøádání
 162 \item{Ax 3)} koøen má $2$ a¾~$b$ synù, ostatní vnitøní vrcholy $a$ a¾ $b$ synù
 163 \item{Ax 4)} v¹echny vnìj¹í vrcholy jsou ve~stejné hloubce (vnìj¹í vrchol$=$list)
 164 \vglue 2 in
 165
 166 \centerline {Prosím vlo¾it obrázek "ab strom11.gif"}
 167
 168 $$ A < x_1 < B < x_2 < C < x_3 < D $$
 169
 170 \s {Lemma:} $(a,b)$ strom na~$n$~vrcholech má hloubku~$O(\log_a n)$.
 171
 172 \proof
 173 Zjistíme jeho minimální poèet listù (oznaème jej $m$): ka¾dý vrchol a¾ na~koøen má alespoò $a$ synù $\rightarrow$\
 174 $$m\geq~a^{(hloubka -1)}$$
 175 $$\log_a m \geq hloubka -1$$
 176 $$hloubka \leq 1+ \log_a m$$
 177 \centerline{co¾ je øádovì  $O(\log_a n)$, kde n je poèet vrcholù.}\
 178
 179 \> \it Operace s (a,b) stromy:\
 180
 181
 182 \s {FIND}\rm
 183 \item{-}V¾dy zjistíme, mezi které 2 klíèe hledaný vrchol patøí a potom se zanoøíme hloubìji.\
 184
 185 \> Èasová slo¾itost:
 186 $$O(\log b \cdot \log_a n)$$
 187 $\log b$ je èas strávený na~jednom vrcholu pro zji¹tení, mezi které 2 vrcholy hledaný patøí, $\log_a n$ je hloubka stromu.\
 188
 189
 190 \s {INSERT}
 191
 192 \> Jako Find, pøièem¾ jestli¾e nena¹el, skonèí na~posledním patøe a~pøidáme klíè
 193 \itemize\ibull
 194 \: pokud pøidáním nepøesáhneme maximální poèet klíèù mù¾eme skonèit
 195 \vglue 2 in
 196 \centerline {Prosím vlo¾it obrázek "insert1.gif"}
 197 \: pokud pøidáním pøesáhneme maximální poèet klíèù
 198 \endlist
 199 \itemitem{*}rozdìlíme vrchol na~3 èásti: L,x,P
 200 \itemitem{*}L a P jsou nové vrcholy
 201 \itemitem{*}x je hodnota mezi L a P, kterou vlo¾íme o patro vý¹ jako klíè oddìlující novì vzniklé vrcholy L a P
 202 \itemitem{*}tím jsme pøevedli problém o patro vý¹ a opakujeme algoritmus
 203 \vglue 2 in
 204
 205 \centerline{Prosím vlo¾it obrázek "b klicu1.gif" a "b klicu2.gif"}
 206
 207
 208 \> pozn.: jestli¾e se dostaneme a¾ do koøene, rozdìlí se koøen na 2 èásti, vznikne nám nový koøen se 2ma syny (co¾ je povoleno) a celému stromu vzroste hloubka o 1
 209 \par
 210 \s {Korektnost:}
 211 Potøebujeme, aby
 212 $$|L|\geq a-1$$
 213 $$|P|\geq a-1$$
 214 po seètení obou nerovností a~priètení 1 na~obì strany rovnice:
 215 $$|L|+|P|+1\geq 2a-2+1=2a-1$$
 216 pravá strana je rovna $b$ a~to podle definice $\geq 2a-1$. \par
 217 \s {Èasová slo¾itost:}
 218 $$O(b\cdot \log_a n)$$
 219
 220
 221 \s {DELETE}
 222 \item{-} pøevedeme na~delete z~listu (stejný postup jako u~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.
 223 \itemize\ibull
 224 \: pokud má vrchol, ze~kterého odebíráme stále $a-1$ kl\'\ièù, mù¾eme skonèit
 225 \: 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$):
 226 \endlist
 227 \algo
 228 \: sma¾eme nejvìt¹í klíè levého sousedního vrvholu(L) a~nahradíme tím klíè otce obou vrcholù (nahradíme $x$ za~tuto hodnotu)
 229 \: pùvodní klíè otce($x$) pøidáme jako nejmen¹í klíè odebíranému vrcholu(V)
 230 \: tím mají oba tyto vrcholy $a-1$ klíèù a mù¾eme skonèit
 231 \endalgo
 232 \vglue 2 in
 233 \centerline{Prosm vlo¾it obrzek "delete21.gif" a "delete22.gif"}
 234 \itemize\ibull
 235 \: pokud má vhchol, z kterého odebíráme(V) $a-2$ klíèù a jeho levý sousední vrchol(L) $a-1$ klíèù (klíè otce oddìlující tyto vrcholy oznaème $x$):
 236 \endlist
 237 \algo
 238 \: slouèíme $V,x,L$ do jednoho vrcholu
 239 \: tím jsme problém pøevedli o patro vý¹ a opakujeme algoritmus \par
 240 \endalgo
 241 \vglue 2 in
 242 \centerline{Prosím vlo¾it obrázek "delete31.gif" a "delete32.gif"}
 243
 244 \> pozn. 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íèù.
 245
 246 \> \bf Èasová slo¾itost: $$O(b\cdot \log_a n)$$
 247
 248 \bye