\input ../lecnotes.tex
-\prednaska{7}{Stromy}{zapsali Miroslav Øezáè, \v Stìpán Masojídek, Barbora Urbancová}
+\prednaska{7}{Stromy}{zapsali Miroslav Øezáè, ©tìpán Masojídek, Barbora Urbancová}
\h{Binární}
-V minulé kapitole jsme se zabývali problematikou pøidávání a ub\'\i{}r\'an\'\i{} prvk\accent23u bin\'arn\'\i{}ho stromu a jeho slo\v zitost\'\i{} a zjistili, \v ze v\v se z\'ale\v z\'\i{} na~hloubce stromu. V\'\i{}me, \v ze chceme hloubku logaritmickou, ale jak ji m\accent23u\v zeme udr\v zet p\v ri~operac\'\i{}ch? \v Re\v sen\'\i{}m jsou
-\
+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
-\h {AVL stromy}
+\h{AVL stromy}
-tedy stromy, hloubka jejich\v z prav\'eho a lev\'eho podstromu se~li\v s\'\i{} maxim\'aln\v e o~jednotku
+tedy stromy, hloubka jejich¾ pravého a levého podstromu se~li¹í maximálnì o~jednotku
\par
\> {\I Operace s AVL stromy:}
-\
\s {FIND}
-\> se~neli\v s\'\i{} od~operace find v~bin\'arn\'\i{}ch stromech.\
-\
+\> se~neli¹í od~operace find v~binárních stromech.\
-Dùraz klademe na operace \it INSERT \rm a \it DELETE \rm , proto\v ze p\v ri~nich mus\'\i{}me o\v setøit udr\v zení struktury AVL~stromù..
+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ù..
-Prvn\'\i{} nutnou podm\'\i{} podm\'\i{}nkou je, \v ze si mus\'\i{}me \bf pamatovat stav \rm v~ka\v zd\'em vrcholu tohoto stromu. A~to jednak hladinu alias \bf hloubku\rm , ve~kter\'e se vrchol vyskytuje, tedy vzd\'alenost tohoto vrcholu od~ko\v rene stromu, a~za~druh\'e \bf vyv\'a\v zen\'\i{} \rm hloubky jeho podstrom\accent23u.
-Umluv\'\i{}me~se nap\v r. na~pravidle, \v ze pokud je lev\'y podstrom hlub\v s\'\i{}, vrchol m\'a hodnotu minus $\ominus$ a pokud je prav\'y podstrom hlub\v s\'\i{}, vrchol m\'a hodnotu plus $\oplus$.
+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ù.
+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$.
-\>T\'\i{}m dost\'av\'ame t\v ri typy vrchol\accent23u, kter\'e se mohou v~AVL~stromu vyskytnout:
+\>Tím dostáváme tøi typy vrcholù, které se mohou v~AVL~stromu vyskytnout:
-\item{$\bullet$}\it Vrchol se~znam\'enkem~$\oplus$ \rm
+\item{$\bullet$}\it Vrchol se~znaménkem~$\oplus$ \rm
-\item{$\bullet$}\it Vrchol se~znam\'enkem~$\ominus$ \rm a
+\item{$\bullet$}\it Vrchol se~znaménkem~$\ominus$ \rm a
-\item{$\bullet$}\it Vrchol se~znam\'enkem~$\odot$ (nulou), \rm kter\'y m\'a oba syny schodn\'e hloubky.
-\
+\item{$\bullet$}\it Vrchol se~znaménkem~$\odot$ (nulou), \rm který má oba syny schodné hloubky.
-\s {SESTAVEN\'I} \rm AVL stromu:
+\s {SESTAVENÍ} \rm AVL stromu:
-Postupujeme po~struktu\v re bin\'arn\'\i{}ho stromu od~list\accent23u ke~ko\v reni a~kontrolujeme, zda jsou vrcholy v~jednom ze~t\v r\'\i{} uveden\'ych stav\accent23u. Pokud ne, oprav\'\i{}me ho operac\'\i{} jm\'enem rotace.
-\
+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.
\s {Rotace}
\vglue 2 in
-\centerline{Pros\'\i{}m vlo\v zit obr\'azek ``Rotace".}
+\centerline{Prosím vlo¾it obrázek ``Rotace".}
-Jde o~p\v revr\'acen\'\i{} hrany mezi p\accent23uvodn\'\i{}m otcem (ko\v renem podstromu) a nevyv\'a\v zen\'ym vrcholem tak, aby byli i po pøeskupení synov\'e vzhledem k~otc\accent23um spr\'avn\v e uspo\v r\'ad\'ani.
-\
+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.
-\
-\s {INSERT} \rm - vlo\v zen\'\i{} vrcholu do~AVL~stromu.
+\s {INSERT} \rm - vlo¾ení vrcholu do~AVL~stromu.
-Vlo\v z\'\i{}me jej jako list. Nov\'y list m\'a v\v zdy "znam\'enko" nula $\odot$. Pøedpokládáme, \v ze patøí nalevo od posledního otce. Pod\'\i{}v\'ame~se na~znam\'enko jeho otce:
+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:
\itemize\ibull
-\: \bf m\v el~$\odot$ (nem\v el syna) $\rightarrow$ teï m\'a~$\ominus$ \rm , po struktu\v re stromu nahoru pos\'\i{}l\'ame informaci, \v ze se podstrom prohloubil o~1, co\v z m\accent23u\v ze m\'\i{}t samoz\v rejm\v e vliv na~znam\'enka vrchol\accent23u na~cest\v e ke~ko\v reni.
-\: \bf m\v el~$\oplus$ (m\v el prav\'eho syna, kter\'y je listem) $\rightarrow$ teï m\'a~$\odot$ \rm , hloubka podstromu se~nem\v en\'\i{}
-\: \bf mìl $\ominus$ \rm $\leftarrow$ nenastane, proto\v ze v binární struktuøe nejmohou být dva leví synové
-\par P\v ripadne-li p\v ridan\'y list napravo, \v re\v s\'\i{}me zrcadlov\v e.
+\: \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.
+\: \bf mìl~$\oplus$ (mìl pravého syna, který je listem) $\rightarrow$ teï má~$\odot$ \rm , hloubka podstromu se~nemìní
+\: \bf mìl $\ominus$ \rm $\leftarrow$ nenastane, proto¾e v binární struktuøe nejmohou být dva leví synové
+\par Pøipadne-li pøidaný list napravo, øe¹íme zrcadlovì.
\endlist
\vglue 2 in
-\centerline{Pros\'\i{}m vlo\v zit obr\'azek ``P\v rid\'an\'\i{} listu samotn\'e''.}
-\
+\centerline{Prosím vlo¾it obrázek ``Pøidání listu samotné''.}
-\>\bf Prohloubil-li se strom \rm vlo\v zen\'\i{}m nov\'eho listu, mus\'\i{}me pracovat s vyvá\v zením:
+\>\bf Prohloubil-li se strom \rm vlo¾ením nového listu, musíme pracovat s vyvá¾ením:
\algo
-\: informace o~prohlouben\'\i{} p\v ri\v sla zleva \bf do~vrcholu se~znam.~$\odot$ \rm $\rightarrow$ m\v en\'\i{} jej na~vrchol se~znam\'enkem~$\ominus$ a informace o~prohlouben\'\i{} je t\v reba poslat o~\'urove\v n v\'y\v s
-\: informace o~prohlouben\'\i{} p\v ri\v sla zleva \bf do~vrcholu se~znam.~$\oplus$ \rm $\rightarrow$ m\v en\'\i{} jej na~vrchol se~znam\'enkem~$\odot$, hloubka je vyrovn\'ana, d\'al nic nepos\'\i{}l\'ame
-\: informace o~prohlouben\'\i{} p\v ri\v sla zleva \bf do vrcholu s~$\ominus$ $\rightarrow$\rm
+\: 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ý¹
+\: 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
+\: informace o~prohloubení pøi¹la zleva \bf do vrcholu s~$\ominus$ $\rightarrow$\rm
\endalgo
-\> $\rightarrow$ rozebereme na~t\v ri p\v r\'\i{}pady podle znam\'enka vrcholu, ze~kter\'eho p\v ri\v sla informace o~prohlouben\'\i{}.
+\> $\rightarrow$ rozebereme na~tøi pøípady podle znaménka vrcholu, ze~kterého pøi¹la informace o~prohloubení.
\itemize\ibull
-\: informace p\v ri\v sla \bf z~vrcholu se~znam\'enkem~$\ominus$\rm $\rightarrow$ provedeme rotaci doprava tak, \v ze nov\'ym ko\v renem se~stane vrchol~$y$, ze~kter\'eho p\v ri\v sla informace o~prohlouben\'\i{}
+\: 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í
\vglue 2 in
-\centerline{Pros\'\i{}m vlo\v zit obr\'azek ``y je $\ominus$"}
-{\I Pozorování 1:} znam\'enko vrchol\accent23u~$y$ a~$x$ je~$\odot$\
-
-{\I Pozorování 2:} hloubka p\v red vkl\'ad\'an\'\i{}m byla $h+1$ a~nyn\'\i{} je tak\'e $h+1$, tedy nemus\'\i{}me d\'ale pos\'\i{}lat informaci o~prohlouben\'\i{} a m\accent23 u\v zeme skon\v cit
-\: informace p\v ri\v sla \bf z~vrcholu se~znam\'enkem~$\oplus$\rm
-\itemitem{-}uva\v zme je\v ste vrchol~$z$ jako prav\'eho syna vrcholu~$y$, ze~kter\'eho pri\v sla informace o~prohlouben\'\i{}, a~jeho podstromy~$B$ a~$C$
-\itemitem{-} vrcholy~$B$ a~$C$ maj\'\i{} hloubku~$h$ nebo $h-1$ $\rightarrow$ ozna\v cme~ji tedy $h-$ (to z\v rejm\v e proto\v ze vrchol~$y$ m\'a znam\'enko~$\oplus$, tedy jeho prav\'y podstrom s~ko\v renem~$z$ m\'a hloubku~$h+1$ )
-\itemitem{-}provedeme dvojrotaci tak, \v ze nov\'ym ko\v renem se~stane vrchol~$z$
+\centerline{Prosím vlo¾it obrázek ``y je $\ominus$"}
+{\I Pozorování 1:} znaménko vrcholù~$y$ a~$x$ je~$\odot$\
+
+{\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
+\: informace pøi¹la \bf z~vrcholu se~znaménkem~$\oplus$\rm
+\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$
+\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$ )
+\itemitem{-}provedeme dvojrotaci tak, ¾e novým koøenem se~stane vrchol~$z$
\vglue 2 in
-\centerline{Pros\'\i{}m vlo\v zit obr\'azek ``$y$ jako $\oplus$''}
-\
+\centerline{Prosím vlo¾it obrázek ``$y$ jako $\oplus$''}
-{\I Pozorov\'an\'\i{} 1:} znam\'enko vrcholu~$z$ bude~$\odot$\
+{\I Pozorování 1:} znaménko vrcholu~$z$ bude~$\odot$\
-{\I Pozorování 2:} znam\'enka vrcholu~$x$ a~$y$ se~dopo\v c\'\i{}taj\'\i{} v~z\'avislosti na~hloubce~$B$ a~$C$\
+{\I Pozorování 2:} znaménka vrcholu~$x$ a~$y$ se~dopoèítají v~závislosti na~hloubce~$B$ a~$C$\
-{\I Pozorování 3:} rozd\'\i{}l hloubky prav\'eho a~lev\'eho podstromu u~t\v echto vrchol\accent23u bude~$0$ nebo~$1$\
+{\I Pozorování 3:} rozdíl hloubky pravého a~levého podstromu u~tìchto vrcholù bude~$0$ nebo~$1$\
-{\I Pozorování 4:} hloubka p\v red vkl\'ad\'an\'\i{}m byla $h+2$ a~nyn\'\i{} je tak\'e $h+2$, tedy nemus\'\i{}me d\'ale pos\'\i{}lat informaci o~prohlouben\'\i{} a~m\accent23u\v zeme skon\v cit
-\: informace p\v ri\v sla \bf z~vrcholu se~znam\'enkem~$\odot$ \rm $\leftarrow$ to nem\accent23u\v ze nastat, proto\v ze v~tom pøípadì by ne\v slo o~prohloubení
+{\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
+\: 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í
\endlist
-\
-\
\s {DELETE} \rm - odebrání vrcholu z~AVL~stromu
-\
-\
-\> Buï ma\v zeme list nebo ma\v zeme vrchol, který mìl nìjaké syny.
+\> Buï ma¾eme list nebo ma¾eme vrchol, který mìl nìjaké syny.
\itemize\ibull
-\: pokud ma\v zeme list, podíváme~se na~znaménko otce. Pøedpokládáme mazání levého syna.
+\: pokud ma¾eme list, podíváme~se na~znaménko otce. Pøedpokládáme mazání levého syna.
\itemize\ibull
-\: mìl znaménko $\ominus$ (nemìl pravého syna) $\rightarrow$ zmìní~se na~$\odot$ (vrchol teï nemá \v zádné syny)
+\: mìl znaménko $\ominus$ (nemìl pravého syna) $\rightarrow$ zmìní~se na~$\odot$ (vrchol teï nemá ¾ádné syny)
\: mìl znaménko $\odot$ (mìl oba syny) $\rightarrow$ zmìní~se na~$\oplus$
\endlist
-(ma\v zeme-li pravý list, øe\v síme zrcadlovì)
-\: ma\v zeme vrchol s~jedním (levým nebo pravým) synem $\rightarrow$ syn nastupuje na~místo otce a~získává zn.~$\odot$\
+(ma¾eme-li pravý list, øe¹íme zrcadlovì)
+\: 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$\
\> V~obou pøípadech posílame informaci o~zmìnì hloubky stromu..
\: mazaný vrchol mìl oba syny (listy) $\rightarrow$ vybereme jednoho ze~synù na~místo smazaného otce. Hloubka se nemìní.
-\: mazaný vrchol mìl syny podstromy $\rightarrow$ na~jeho místo vezmeme nejvìt\v sí prvek levého podstromu (nebo nejmen\v sí prvek pravého podstromu) a od~odebraného (nahrazujícího) listu kontrolujeme vyvá\v zení podstromu.
+\: 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.
\endlist
-\
-\bf \' Uprava vyvá\v zení \rm stromu po~odebrání listu z~podstromu
+\bf Úprava vyvá¾ení \rm stromu po~odebrání listu z~podstromu
\algo
-\: informace o~zmìnì hloubky pøi\v sla z~levého podstromu do~vrcholu se~znaménkem $\odot$ $\rightarrow$ vrchol se~zmìní na~$\oplus$ a~dál se hloubka nemìní
+\: 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í
-\: informace pøi\v sla zleva do~vrcholu s~$\ominus$ $\rightarrow$ mìní~se na~$\odot$ a~posíláme informaci o~zmìnì hloubky.
+\: informace pøi¹la zleva do~vrcholu s~$\ominus$ $\rightarrow$ mìní~se na~$\odot$ a~posíláme informaci o~zmìnì hloubky.
-\: problémová situace nastává, kdy\v z informace o~zmìnì pøi\v sla zleva do~vrcholu se~znaménkem~$\oplus$~$\rightarrow$
+\: problémová situace nastává, kdy¾ informace o~zmìnì pøi¹la zleva do~vrcholu se~znaménkem~$\oplus$~$\rightarrow$
\endalgo
-\> $\rightarrow$ rozebereme na~tøi~pøípady podle znaménka pravého syna nevyvá\v zeného vrcholu
+\> $\rightarrow$ rozebereme na~tøi~pøípady podle znaménka pravého syna nevyvá¾eného vrcholu
\itemize\ibull
\: 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
\vglue 2 in
-\centerline{Prosím vlo\v zit obrázek ``opaèný syn má $\oplus$''}
+\centerline{Prosím vlo¾it obrázek ``opaèný syn má $\oplus$''}
-\: 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í\v z není tøeba posílat informaci..
+\: 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..
\vglue 2 in
-\centerline{Prosím vlo\v zit obrázek ``opaèný syn má $\odot$''}
+\centerline{Prosím vlo¾it obrázek ``opaèný syn má $\odot$''}
\: pravý syn má znaménko $\ominus$
-v~tomto pøípadì uva\v zujeme je\v stì 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, \v ze 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.
+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.
\vglue 2 in
-\centerline{Prosím vlo\v zit obrázek ``opaèný syn má $\ominus$''}
+\centerline{Prosím vlo¾it obrázek ``opaèný syn má $\ominus$''}
\endlist
-\
-\h {Obecn\'e stromy}
-\
+\h{Obecné stromy}
-(Stromy s v\'\i{}ce v\v etvemi)
-\
+(Stromy s více vìtvemi)
-\>\it Pro\v c se t\'\i{}mto zab\'yvat? \rm
+\>\it Proè se tímto zabývat? \rm
\par
-P\v ri ulo\v zen\'\i{} dat na~disku se~sna\v z\'\i{}me, aby~se \v cten\'\i{} z~disku prov\'ad\v elo pokud mo\v zno co nejm\'en\v ekr\'at a~nez\'ale\v z\'\i{} n\'am tolik na~tom, kolik operac\'\i{} se~vykon\'a v~jednom uzlu. (\v Casov\v e je operace porovn\'av\'an\'\i{} zanedbateln\'a oproti \v cten\'\i{} z~disku)
-\
+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)
-\
-\s {Def:} \bf (a,b) strom \rm pro parametry $a,b$, $a \geq 2$, $b\geq 2a - 1$ je zako\v ren\v en\'y strom s~uspo\v r\'adan\'ymi syny a~vn\v ej\v s\'\i{}mi vrcholy, pro kter\'y plat\'\i{}:
+\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í:
\par
-\> (pozn.: kdekoli~by mohl b\'yt syn a~nen\'\i{}, p\v ripoj\'\i{}me vrchol, kter\'emu \v r\'\i{}k\'ame vn\v ej\v s\'\i{} vrchol)
-\
+\> (pozn.: kdekoli~by mohl být syn a~není, pøipojíme vrchol, kterému øíkáme vnìj¹í vrchol)
-\
-\item{Ax 1)} data jsou ulo\v zena ve~vnit\v rn\'\i{}ch vrcholech a~ka\v zd\'y vrchol obsahuje o~1 m\'en\v e kl\'\i{}\v c\accent23u ne\v z m\'a syn\accent23u
-\item{Ax 2)} plat\'\i{} stromov\'e uspo\v r\'ad\'an\'\i{}
-\item{Ax 3)} ko\v ren m\'a $2$ a\v z~$b$ syn\accent23u, ostatn\'\i{} vnit\v rn\'\i{} vrcholy $a$ a\v z $b$ syn\accent23u
-\item{Ax 4)} v\v sechny vn\v ej\v s\'\i{} vrcholy jsou ve~stejn\'e hloubce (vn\v ej\v s\'\i{} vrchol$=$list)
+\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ù
+\item{Ax 2)} platí stromové uspoøádání
+\item{Ax 3)} koøen má $2$ a¾~$b$ synù, ostatní vnitøní vrcholy $a$ a¾ $b$ synù
+\item{Ax 4)} v¹echny vnìj¹í vrcholy jsou ve~stejné hloubce (vnìj¹í vrchol$=$list)
\vglue 2 in
-\centerline {Prosím vlo\v zit obrázek "ab strom11.gif"}
+\centerline {Prosím vlo¾it obrázek "ab strom11.gif"}
$$ A < x_1 < B < x_2 < C < x_3 < D $$
-\s {Lemma:} $(a,b)$ strom na~$n$~vrcholech m\'a hloubku~$O(\log_a n)$.
+\s {Lemma:} $(a,b)$ strom na~$n$~vrcholech má hloubku~$O(\log_a n)$.
\proof
-Zjist\'\i{}me jeho minim\'aln\'\i{} po\v cet list\accent23u (ozna\v cme jej $m$): ka\v zd\'y vrchol a\v z na~ko\v ren m\'a alespo\v n $a$ syn\accent23u $\rightarrow$\
+Zjistíme jeho minimální poèet listù (oznaème jej $m$): ka¾dý vrchol a¾ na~koøen má alespoò $a$ synù $\rightarrow$\
$$m\geq~a^{(hloubka -1)}$$
$$\log_a m \geq hloubka -1$$
$$hloubka \leq 1+ \log_a m$$
-\centerline{co\v z je \v r\'adov\v e $O(\log_a n)$, kde n je po\v cet vrchol\accent23u.}\
-\
+\centerline{co¾ je øádovì $O(\log_a n)$, kde n je poèet vrcholù.}\
\> \it Operace s (a,b) stromy:\
-\
\s {FIND}\rm
-\item{-}V\v zdy zjist\'\i{}me, mezi kter\'e 2 kl\'\i{}\v ce hledan\'y vrchol pat\v r\'\i{} a potom se zano\v r\'\i{}me hloub\v eji.\
+\item{-}V¾dy zjistíme, mezi které 2 klíèe hledaný vrchol patøí a potom se zanoøíme hloubìji.\
-\> \v Casov\'a slo\v zitost:
+\> Èasová slo¾itost:
$$O(\log b \cdot \log_a n)$$
-$\log b$ je \v cas str\'avený na~jednom vrcholu pro zji\v sten\'\i{}, mezi kter\'e 2 vrcholy hledaný pat\v r\'\i{}, $\log_a n$ je hloubka stromu.\
+$\log b$ je èas strávený na~jednom vrcholu pro zji¹tení, mezi které 2 vrcholy hledaný patøí, $\log_a n$ je hloubka stromu.\
-\
\s {INSERT}
-\> Jako Find, pøièem¾ jestli\v ze nena\v sel, skon\v c\'\i{} na~posledn\'\i{}m pat\v re a~p\v rid\'ame kl\'\i{}\v c
+\> Jako Find, pøièem¾ jestli¾e nena¹el, skonèí na~posledním patøe a~pøidáme klíè
\itemize\ibull
-\: pokud p\v rid\'an\'\i{}m nep\v res\'ahneme maxim\'aln\'\i{} po\v cet kl\'\i{}\v c\accent23u m\accent23u\v zeme skon\v cit
+\: pokud pøidáním nepøesáhneme maximální poèet klíèù mù¾eme skonèit
\vglue 2 in
-\centerline {Prosím vlo\v zit obrázek "insert1.gif"}
-\: pokud p\v rid\'an\'\i{}m p\v res\'ahneme maxim\'aln\'\i{} po\v cet kl\'\i{}\v c\accent23u
+\centerline {Prosím vlo¾it obrázek "insert1.gif"}
+\: pokud pøidáním pøesáhneme maximální poèet klíèù
\endlist
-\itemitem{*}rozd\v el\'\i{}me vrchol na~3 \v c\'asti: L,x,P
-\itemitem{*}L a P jsou nov\'e vrcholy
-\itemitem{*}x je hodnota mezi L a P, kterou vlo\v z\'\i{}me o patro v\'y\v s jako kl\'\i{}\v c odd\v eluj\'\i{}c\'\i{} nov\v e vznikl\'e vrcholy L a P
-\itemitem{*}t\'\i{}m jsme p\v revedli probl\'em o patro v\'y\v s a opakujeme algoritmus
+\itemitem{*}rozdìlíme vrchol na~3 èásti: L,x,P
+\itemitem{*}L a P jsou nové vrcholy
+\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
+\itemitem{*}tím jsme pøevedli problém o patro vý¹ a opakujeme algoritmus
\vglue 2 in
-\centerline{Prosím vlo\v zit obrázek "b klicu1.gif" a "b klicu2.gif"}
+\centerline{Prosím vlo¾it obrázek "b klicu1.gif" a "b klicu2.gif"}
-\> pozn.: jestli\v ze se dostaneme a\v z do ko\v rene, rozd\v el\'\i{} se ko\v ren na 2 \v c\'asti, vznikne n\'am nov\'y ko\v ren se 2ma syny (co\v z je povoleno) a cel\'emu stromu vzroste hloubka o 1
+\> 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
\par
\s {Korektnost:}
-Pot\v rebujeme, aby
+Potøebujeme, aby
$$|L|\geq a-1$$
$$|P|\geq a-1$$
-po se\v cten\'\i{} obou nerovnost\'\i{} a~pri\v cten\'\i{} 1 na~ob\v e strany rovnice:
+po seètení obou nerovností a~priètení 1 na~obì strany rovnice:
$$|L|+|P|+1\geq 2a-2+1=2a-1$$
-prav\'a strana je rovna $b$ a~to podle definice $\geq 2a-1$. \par
-\s {\v Casov\'a slo\v zitost:}
+pravá strana je rovna $b$ a~to podle definice $\geq 2a-1$. \par
+\s {Èasová slo¾itost:}
$$O(b\cdot \log_a n)$$
-\
\s {DELETE}
-\item{-} p\v revedeme na~delete z~listu (stejn\'y postup jako u~stromu: jestli\v ze to nen\'\i{} list, prohod\'\i{}me tuto hodnotu s~nejmen\v s\'\i{} hodnotou podstromu jeho prav\'eho syna) --- v tomto pøípadì na~klíè posledního vnitøního vrcholu, proto\v ze listy jsou vnìj\v sí vrcholy bez dat.
+\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.
\itemize\ibull
-\: pokud m\'a vrchol, ze~kter\'eho odeb\'\i{}r\'ame st\'ale $a-1$ kl\'\i\v c\accent23u, m\accent23u\v zeme skon\v cit
-\: pokud m\'a vrchol(V), ze~kter\'eho odeb\'\i{}r\'ame $a-2$ kl\'\i{}\v c\accent23u a~jeho lev\'y sousedn\'\i{} vrchol(L) alespo\v n $a$ kl\'\i{}\v c\accent23u (kl\'\i{}\v c otce odd\v eluj\'\i{}c\'\i{} tyto vrcholy ozna\v cme $x$):
+\: pokud má vrchol, ze~kterého odebíráme stále $a-1$ kl\'\ièù, mù¾eme skonèit
+\: 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$):
\endlist
\algo
-\: sma\v zeme nejvìt\v sí kl\'\i{}\v c lev\'eho sousedn\'\i{}ho vrvholu(L) a~nahrad\'\i{}me t\'\i{}m kl\'\i{}\v c otce obou vrchol\accent23u (nahrad\'\i{}me $x$ za~tuto hodnotu)
-\: p\accent23uvodn\'\i{} kl\'\i{}\v c otce($x$) p\v rid\'ame jako nejmen\v s\'\i{} kl\'\i{}\v c odeb\'\i{}ran\'emu vrcholu(V)
-\: t\'\i{}m maj\'\i{} oba tyto vrcholy $a-1$ kl\'\i{}\v c\accent23u a m\accent23u\v zeme skon\v cit
+\: 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)
+\: pùvodní klíè otce($x$) pøidáme jako nejmen¹í klíè odebíranému vrcholu(V)
+\: tím mají oba tyto vrcholy $a-1$ klíèù a mù¾eme skonèit
\endalgo
\vglue 2 in
-\centerline{Prosm vlo\v zit obrzek "delete21.gif" a "delete22.gif"}
+\centerline{Prosm vlo¾it obrzek "delete21.gif" a "delete22.gif"}
\itemize\ibull
-\: pokud m\'a vhchol, z kter\'eho odeb\'\i{}r\'ame(V) $a-2$ kl\'\i{}\v c\accent23u a jeho lev\'y sousedn\'\i{} vrchol(L) $a-1$ kl\'\i{}\v c\accent23u (kl\'\i{}\v c otce odd\v eluj\'\i{}c\'\i{} tyto vrcholy ozna\v cme $x$):
+\: 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$):
\endlist
\algo
-\: slou\v c\'\i{}me $V,x,L$ do jednoho vrcholu
-\: t\'\i{}m jsme probl\'em p\v revedli o patro v\'y\v s a opakujeme algoritmus \par
+\: slouèíme $V,x,L$ do jednoho vrcholu
+\: tím jsme problém pøevedli o patro vý¹ a opakujeme algoritmus \par
\endalgo
\vglue 2 in
-\centerline{Prosím vlo\v zit obrázek "delete31.gif" a "delete32.gif"}
+\centerline{Prosím vlo¾it obrázek "delete31.gif" a "delete32.gif"}
-\> pozn. Dojdeme-li takto a\v z do koøene, na místo klíèe odebraného z koøene lze pou\v zít nejmen\v sí nebo nejvìt\v sí klíè novì slouèeného podstromu. Ten odebrat lze, proto\v ze po slouèení (které bylo pøíèinou této situace), je v nejni\v z\v sím vrcholu $2a-2$ klíèù.
+\> 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íèù.
-\
+\> \bf Èasová slo¾itost: $$O(b\cdot \log_a n)$$
-\> \bf \v Casov\'a slo\v zitost: $$O(b\cdot \log_a n)$$
-\bye
\ No newline at end of file
+\bye
projects / ads1.git / blobdiff