From 198b46590ec2c07ea91b1cd11c9d8dfd24c38e7f Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Mon, 12 Nov 2007 12:07:17 +0100 Subject: [PATCH] Nova verze od Barbory. --- 7-stromy/7-stromy.tex | 245 +++++++++++++++++++++++------------------- 1 file changed, 135 insertions(+), 110 deletions(-) diff --git a/7-stromy/7-stromy.tex b/7-stromy/7-stromy.tex index d5e737b..30173fa 100644 --- a/7-stromy/7-stromy.tex +++ b/7-stromy/7-stromy.tex @@ -8,7 +8,7 @@ \medskip } -\prednaska{7}{Stromy}{zapsali Miroslav Øezáè, ©tìpán Masojídek, Barbora Urbancová} +\prednaska{7}{Vyhledávací stromy}{zapsali M. Øezáè, ©. Masojídek, B. Urbancová} \h{Pár obrázkù, které by stály za pøesun do~pøedchozí kapitoly:} @@ -18,84 +18,120 @@ \h{Binární} -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 +V minulé kapitole jsme se zabývali problematikou pøidávání a ubírání prvkù binárního vyhledávací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 je následující definice: +\s{Definice:} {\I Dokonalé vyvá¾ení} je takové vyvá¾ení, kde platí $ \forall v: \left\vert \vert L(v)\vert - \vert P(v)\vert \right \vert \leq 1 $ + +Toto nám jistì zaji¹»uje logaritmickou hloubku, ale je velmi pracné na udr¾ování. + \h{AVL stromy} -tedy stromy, hloubka jejich¾ pravého a levého podstromu se~li¹í maximálnì o~jednotku -\par +\s{Definice:} {\I Hloubkové vyvá¾ení} je takové vyvá¾ení, kde platí $ \forall v: \left \vert h(L(v)) - h(P(v)) \right \vert \leq 1 $ + +\>Jsou to tedy stromy, hloubka jejich\v z prav\'eho a lev\'eho podstromu se~li\v s\'\i{} maxim\'aln\v e o~jednotku + +\>Stromùm s hloubkovým vyvá¾ením se øíká AVL stromy. A o nich si doká¾eme následující lemma. + +\s{Lemma: } AVL strom o $n$ vrcholech má hloubku $ \O(\log{n}) $. + +\proof +Uva¾me $a_k = $ minimální poèet vrcholù stromu o~hloubce $k$. + +Lehce spoèteme: + +% FIXME neni spravne a chova se divne +\itemize\ibull +\next $ a_0 = 0 $ + +\next $ a_1 = 1 $ + +\next $ a_2 = 2 $ -\> {\I Operace s AVL stromy:} +\next $ \vdots $ +\next $ a_k = 1 + a_{k - 1} + a_{k - 2} $ -\s {FIND} +\endlist + +Rekurentní vzorec jsme dostali rekurzivním stavìním stromu hloubky $k$: nový koøen a dva podstromy o hloubce $k - 1$ a $k - 2$. + +Indukcí doká¾eme, ¾e $ a_k \geq 2^{k \over 2} $. +První indukèní krok jsme si u¾ ukázali, teï pro $ k \geq 2 $ platí: +$ 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} $ -\> se~neli¹í od~operace find v~binárních stromech.\ +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})$ +\qed -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ù.. +\>{\I Operace s AVL stromy:} -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$. +\s{Find} -\>Tím dostáváme tøi typy vrcholù, které se mohou v~AVL~stromu vyskytnout: +\>se~neli¹í od~operace find v~binárních stromech.\ -\item{$\bullet$}\it Vrchol se~znaménkem~$\oplus$ \rm -\item{$\bullet$}\it Vrchol se~znaménkem~$\ominus$ \rm a +Dùraz klademe na operace {\I Insert} a \, proto¾e pøi~nich musíme o¹etøit udr¾ení struktury AVL~stromù.. -\item{$\bullet$}\it Vrchol se~znaménkem~$\odot$ (nulou), \rm který má oba syny schodné hloubky. +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ù. + +Umluvíme~se napø. na~tomto oznaèení: + +\>Dostaneme tøi typy vrcholù, které se mohou v~AVL~stromu vyskytnout: +\itemize\ibull +\:{\I Vrchol typu~$\oplus$}, pokud je pravý podstrom hlub¹í +\:{\I Vrchol typu~$\ominus$}, pokud je levý podstrom hlub¹í a +\:{\I Vrchol typu~$\odot$ (nulou)}, který má oba syny schodné hloubky. +\endlist -\s {SESTAVENÍ} \rm AVL stromu: +\s {Sestavení} \rm AVL stromu: 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} - \treepic{4} \treepic{5} 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¾ení vrcholu do~AVL~stromu. +\s {Insert} \rm - vlo¾ení vrcholu do~AVL~stromu. -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: +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: \itemize\ibull -\: \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ì. +\:{\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. +\:{\I mìl~$\oplus$ (mìl pravého syna, který je listem) $\rightarrow$ teï má~$\odot$}, hloubka podstromu se~nemìní +\:{\I mìl $\ominus$} --- nenastane, proto¾e v binární struktuøe nemohou být dva leví synové \endlist +\>Pøipadne-li pøidaný list napravo, øe¹íme zrcadlovì. \treepic{6} \treepic{7} -\>\bf Prohloubil-li se strom \rm vlo¾ením nového listu, musíme pracovat s vyvá¾ením: -\algo -\: 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 +\>{\I Prohloubil-li se strom} vlo¾ením nového listu, musíme pracovat s vyvá¾ením: +\itemize\ibull +\: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ý¹. +\: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. +\:Informace o~prohloubení pøi¹la zleva {\I do vrcholu s~$\ominus$} $\rightarrow$ -\> $\rightarrow$ rozebereme na~tøi pøípady podle znaménka vrcholu, ze~kterého pøi¹la informace o~prohloubení. +\>rozebereme na~tøi pøípady podle znaménka vrcholu, ze~kterého pøi¹la informace o~prohloubení: \itemize\ibull -\: 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í +\: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í. \treepic{8} {\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$ - +\:Informace pøi¹la {\I z~vrcholu typu~$\oplus$} +\itemize\ibull +\: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$ +\: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$ ) +\:provedeme dvojrotaci tak, ¾e novým koøenem se~stane vrchol~$z$ +\endlist \treepic{9} {\I Pozorování 1:} znaménko vrcholu~$z$ bude~$\odot$\ @@ -105,159 +141,148 @@ Vlo {\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ø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í +\:informace pøi¹la {\I z~vrcholu typu~$\odot$} --- to nemù¾e nastat, proto¾e v~tom pøípadì by ne¹lo o~prohloubení +\endlist \endlist - -\s {DELETE} \rm - odebrání vrcholu z~AVL~stromu - - +\s {Delete} - odebrání vrcholu z~AVL~stromu \> Buï ma¾eme list nebo ma¾eme vrchol, který mìl nìjaké syny. \itemize\ibull -\: pokud ma¾eme 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~typ 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á ¾ádné syny) -\: mìl znaménko $\odot$ (mìl oba syny) $\rightarrow$ zmìní~se na~$\oplus$ +\:byl typu $\ominus$ (nemìl pravého syna) $\rightarrow$ zmìní~se na~$\odot$ (vrchol teï nemá ¾ádné syny) +\:byl typu $\odot$ (mìl oba syny) $\rightarrow$ zmìní~se na~$\oplus$ \endlist (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$\ +\: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$\ -\> 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¹í prvek levého podstromu (nebo nejmen¹í prvek pravého podstromu) a od~odebraného (nahrazujícího) listu kontrolujeme vyvá¾ení podstromu. +\>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¹í prvek levého podstromu (nebo nejmen¹í prvek pravého podstromu) a od~odebraného (nahrazujícího) listu kontrolujeme vyvá¾ení podstromu. \endlist -\bf Úprava vyvá¾ení \rm stromu po~odebrání listu z~podstromu -\algo -\: 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í +\>{\I Úprava vyvá¾ení} stromu po~odebrání listu z~podstromu +\itemize\ibull +\: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í -\: informace pøi¹la 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. \treepic{10} \treepic{11} -\: 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á¾eného vrcholu +\:problémová situace nastává, kdy¾ informace o~zmìnì pøi¹la zleva do~vrcholu se~znaménkem~$\oplus$ +\endlist +\>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 +\:{\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 \treepic{12} -\: 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.. +\:{\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.. \treepic{12y} -\: pravý syn má znaménko $\ominus$ -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. +\:{\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. \treepic{13} \endlist \h{Obecné stromy} - (Stromy s více vìtvemi) -\>\it Proè se tímto zabývat? \rm -\par -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øenìný strom s~uspoøádanými syny a~vnìj¹ími vrcholy, pro který platí: -\par -\> (pozn.: kdekoli~by mohl být syn a~není, pøipojíme vrchol, kterému øíkáme vnìj¹í vrchol) +\>{\I Proè se tímto zabývat?} +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) -\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) +\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í: +\itemize\ibull +\:{Ax 1)}data jsou ulo¾ena ve~vnitøních vrcholech a~ka¾dý vrchol obsahuje o~1 ménì klíèù ne¾ má synù +\:{Ax 2)}platí stromové uspoøádání, tedy ¾e $ A < x_1 < B < x_2 < C < x_3 < D $ +\:{Ax 3)}koøen má $2$ a¾~$b$ synù, ostatní vnitøní vrcholy $a$ a¾ $b$ synù +\:{Ax 4)}v¹echny vnìj¹í vrcholy jsou ve~stejné hloubce (vnìj¹í vrchol$=$list) +\endlist +\>{\I Poznámka:} kdekoli~by mohl být syn a~není, pøipojíme vrchol, kterému øíkáme vnìj¹í vrchol) \vglue 2 in \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á hloubku~$O(\log_a n)$. +\s{Lemma:} $(a,b)$-strom na~$n$~vrcholech má hloubku~$O(\log_a n)$. \proof 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¾ je øádovì $O(\log_a n)$, kde n je poèet vrcholù.}\ +\centerline{co¾ je øádovì $O(\log_a n)$, kde $n$ je poèet vrcholù.}\ -\> \it Operace s (a,b) stromy:\ +\s{Operace s (a,b) stromy:} - -\s {FIND}\rm +\s{Find} \item{-}V¾dy zjistíme, mezi které 2 klíèe hledaný vrchol patøí a potom se zanoøíme hloubìji.\ -\> Èasová slo¾itost: -$$O(\log b \cdot \log_a n)$$ -$\log b$ je èas strávený na~jednom vrcholu pro zji¹tení, mezi které 2 vrcholy hledaný patøí, $\log_a n$ je hloubka stromu.\ - +\>È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. -\s {INSERT} +\s{Insert} -\> Jako Find, pøièem¾ jestli¾e nena¹el, skonèí na~posledním patøe a~pøidáme klíè +\>Jako Find, pøièem¾ jestli¾e nena¹el, skonèí na~posledním patøe a~pøidáme klíè \itemize\ibull -\: pokud pøidáním nepøesáhneme maximální poèet klíèù mù¾eme skonèit +\:pokud pøidáním nepøesáhneme maximální poèet klíèù mù¾eme skonèit \vglue 2 in \centerline {Prosím vlo¾it obrázek "insert1.gif"} -\: pokud pøidáním pøesáhneme maximální poèet klíèù +\:pokud pøidáním pøesáhneme maximální poèet klíèù \endlist -\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 +\algo +\:rozdìlíme vrchol na~3 èásti: $L$,$x$,$P$ +\:$L$ a $P$ jsou nové vrcholy +\:$x$ je hodnota mezi $L$ a $P$, kterou vlo¾íme o patro vý¹ jako klíè oddìlující novì vzniklé vrcholy $L$ a $P$ +\:tím jsme pøevedli problém o patro vý¹ a opakujeme algoritmus +\endalgo \vglue 2 in \centerline{Prosím vlo¾it obrázek "b klicu1.gif" a "b klicu2.gif"} -\> 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:} +\s{Poznámka:} Jestli¾e se dostaneme a¾ do koøene, rozdìlí se koøen na dvì èásti, vznikne nám nový koøen se dvìma syny (co¾ je povoleno) a celému stromu vzroste hloubka o jedna. + +\s{Korektnost:} Potøebujeme, aby -$$|L|\geq a-1$$ -$$|P|\geq a-1$$ +$$\vert L\vert \geq a-1$$ +$$\vert P\vert \geq a-1$$ po seètení obou nerovností a~priètení 1 na~obì strany rovnice: -$$|L|+|P|+1\geq 2a-2+1=2a-1$$ +$$\vert L\vert +\vert P\vert +1\geq 2a-2+1=2a-1$$ pravá strana je rovna $b$ a~to podle definice $\geq 2a-1$. \par -\s {Èasová slo¾itost:} -$$O(b\cdot \log_a n)$$ +\s{Èasová slo¾itost:} vkládání prvku do $(a,b)$-stromu je $O(b\cdot \log_a n)$. -\s {DELETE} +\s{Delete} \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á vrchol, ze~kterého odebíráme stále $a-1$ klíèù, 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$): +\:pokud má vrchol, ze~kterého odebíráme stále $a-1$ klíèù, 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¾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 +\: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¾it obrzek "delete21.gif" a "delete22.gif"} +\centerline{Prosím vlo¾it obrázek "delete21.gif" a "delete22.gif"} \itemize\ibull -\: 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$): +\:pokud má vrchol, 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èíme $V,x,L$ do jednoho vrcholu -\: tím jsme problém pøevedli o patro vý¹ 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¾it obrázek "delete31.gif" a "delete32.gif"} -\> 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íèù. +\>{\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íèù. -\> \bf Èasová slo¾itost: $$O(b\cdot \log_a n)$$ +\>{\I Èasová slo¾itost:} $$O(b\cdot \log_a n)$$ \bye -- 2.39.2