From ca7b199dcc911ae3f8118f63e8b617a7160f2a7b Mon Sep 17 00:00:00 2001 From: Jan 'Moskyt' Matejka Date: Sun, 19 Jun 2011 17:42:19 +0200 Subject: [PATCH] =?utf8?q?Drobn=C3=A9=20=C3=BApravy=20abstrom=C5=AF?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- 9-stromy/9-stromy.tex | 28 +++++++++++++++++----------- 1 file changed, 17 insertions(+), 11 deletions(-) diff --git a/9-stromy/9-stromy.tex b/9-stromy/9-stromy.tex index a8c8fba..a304bc8 100644 --- a/9-stromy/9-stromy.tex +++ b/9-stromy/9-stromy.tex @@ -185,6 +185,9 @@ P 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.) +Hodilo by se nám tedy mít uzly velké tøeba tak, jako je velká jedna stránka +cache \dots + \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í následující axiomy: \numlist\nparen @@ -193,7 +196,7 @@ n \:Koøen má $2$ a¾~$b$ synù, ostatní vnitøní vrcholy $a$ a¾ $b$ synù. \: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) +\>{\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. \abpic{ab-strom11} @@ -209,7 +212,7 @@ $$d \leq 1+ \log_a m$$ \s{Operace s (a,b)-stromy:} \s{Find} -\item{-}V¾dy zjistíme, mezi které 2 klíèe hledaný vrchol patøí a potom se zanoøíme hloubìji.\ +\item{-}V¾dy zjistíme, mezi které 2 klíèe hledaný vrchol patøí, a potom se zanoøíme hloubìji.\ \>È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. @@ -230,7 +233,9 @@ $$d \leq 1+ \log_a m$$ \abpics{b-klicu1}{b-klicu2} -\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{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 právì kvùli tomuto +pøípadu) a celému stromu vzroste hloubka o jedna. \s{Korektnost:} Potøebujeme, aby @@ -238,24 +243,24 @@ $$\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: $$\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:} vkládání prvku do $(a,b)$-stromu je $O(b\cdot \log_a n)$. +pravá strana je rovna $b$ a~to podle definice $\geq 2a-1$. +\s{Èasová slo¾itost:} vkládání prvku do $(a,b)$-stromu je $O(b\cdot \log_a n)$. \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. +\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. \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 vrcholu ($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$) +\: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) +\: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 \abpics{delete21}{delete22} \itemize\ibull -\: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$): +\: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$): \endlist \algo \:slouèíme $V$,$x$,$L$ do jednoho vrcholu @@ -265,6 +270,7 @@ prav \>{\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íèù. + \>{\I Èasová slo¾itost:} $$O(b\cdot \log_a n)$$ \bye -- 2.39.2