From 220d1afc5bf37605fdd23a3cc862ce21e0873d42 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Mon, 23 May 2011 21:06:33 +0200 Subject: [PATCH] DS: Korektury od Karla --- 8-ds/8-ds.tex | 91 ++++++++++++++++++++++++++++++++------------------- 1 file changed, 57 insertions(+), 34 deletions(-) diff --git a/8-ds/8-ds.tex b/8-ds/8-ds.tex index b486008..07154e1 100644 --- a/8-ds/8-ds.tex +++ b/8-ds/8-ds.tex @@ -10,9 +10,14 @@ \prednaska{8}{Datové struktury}{} -Co si mù¾eme pøedstavit pod pojmem datová struktura? Mù¾eme tøeba chtít udr¾ovat -mno¾inu $X$ prvkù z nìjakého universa $X\subseteq U$ (kde universum mohou být -napøíklad pøirozená èísla). +Co si mù¾eme pøedstavit pod pojmem datová struktura? V na¹ich programech èasto chceme +nìkteré vìci abstrahovat (pou¾itím funkcí, objektù\dots). Proè tedy nezkusit +abstrahovat i operace s daty? Napøed si urèíme, co s na¹imi daty budeme provádìt a pak +vymyslíme jejich co nejrychlej¹í reprezentaci. + +Mù¾eme tøeba chtít udr¾ovat koneènou mno¾inu $X$ prvkù z nìjakého universa $X\subseteq +U$. Kde universum mohou být napøíklad pøirozená èísla, tedy universum mù¾e být +nekoneèné narozdíl od $X$. Na na¹ich datech budeme chtít provádìt následující operace: \itemize\ibull @@ -21,22 +26,32 @@ Na na \:{\it Find} -- najít polo¾ku \endlist -Èasovou slo¾itost jednotlivých operací poèítejme vzhledem k poètu prvkù obsa¾ených v -datové struktuøe. +Jak mìøit èasovou slo¾itost? Urèitì nechceme mìøit vùèi délce vstupu, proto¾e ho +nemusíme mít celý najednou ve struktuøe. Èasovou slo¾itost jednotlivých operací +poèítejme vzhledem k poètu prvkù obsa¾ených v datové struktuøe. Také mù¾eme chtít udr¾ovat slovník, tedy mno¾inu dvojic $(k, v)$ kde $k\in U$ se -nazývá klíè a $v$ hodnota. Dále pøedpokládejme, ¾e $U$ je lineárnì uspoøádaná a prvky -porovnáme v konstantním èase. +nazývá klíè a $v$ hodnota. Dále pøedpokládejme, ¾e $U$ je lineárnì uspoøádaná a s prvky +pracujeme v konstantním èase. + +Dále budeme zkoumat jen slovník, proto¾e mno¾ina je jen jeho speciálním pøípadem. + +Po slovníku budeme chtít: +\itemize\ibull +\:{\it Insert($k$, $v$)} -- vlo¾it novou hodnotu spolu s klíèem +\:{\it Delete($k$)} -- smazat polo¾ku podle klíèe +\:{\it Find($k$)} -- najít polo¾ku podle klíèe +\endlist V následující tabulce jsou nìkteré mo¾né zpùsoby reprezentace na¹í datové struktury. \settabs 4 \columns \+ & Insert & Delete & Find \cr -\+ pole & $\Theta (1)$ & $\Theta (n)$ & $\Theta (n)$ \cr -\+ setøídìné pole & $\Theta (n)$ & $\Theta (n)$ & $\Theta (\log n)$ \cr -\+ spojový seznam & $\Theta (1)$ & $\Theta (n)$ & $\Theta (n)$ \cr -\+ setøídìný seznam & $\Theta (n)$ & $\Theta (n)$ & $\Theta (n)$ \cr -\+ vyhledávací stromy & $\Theta (\log n)$ & $\Theta (\log n)$ & $\Theta (\log n)$ \cr +\+ pole & $\Theta (1)$ & $\Theta (n)$ & $\Theta (n)$ \cr +\+ setøídìné pole & $\Theta (n)$ & $\Theta (n)$ & $\Theta (\log n)$ \cr +\+ spojový seznam & $\Theta (1)$ & $\Theta (n)$ & $\Theta (n)$ \cr +\+ setøídìný seznam & $\Theta (n)$ & $\Theta (n)$ & $\Theta (n)$ \cr +\+ vyhledávací stromy & $\Theta (\log n)$ & $\Theta (\log n)$ & $\Theta (\log n)$ \cr \s{Pozorování:} Proces binárního vyhledávání v~setøídìném poli se dá reprezentovat binárním vyhledávacím stromem. @@ -49,7 +64,7 @@ m \:$l(v)$ a $p(v)$ -- levý a pravý syn vrcholu $v$ \:$L(v)$ a $P(v)$ -- levý a pravý podstrom vrcholu $v$ \:$S(v)$ -- pøíslu¹ný podstrom s~koøenem $v$ -\:$h(v)$ -- hloubka stromu $S(v)$, neboli délka nejdel¹í cesty z koøene do listu +\:$h(v)$ -- hloubka stromu $S(v)$ -- délka nejdel¹í cesty z koøene do listu \endlist \s{Definice:} {\I Binární vyhledávací strom} (BVS): Binární strom je vyhledávací, @@ -61,8 +76,6 @@ a pro v \treepic{2} -\break - Jak budou tedy vypadat operace {\it Find}, {\it Insert} a {\it Delete} na~binárním vyhledávacím stromu? @@ -83,22 +96,26 @@ vyhled \algo \:Pokud $v$ je list $\Rightarrow$ jednodu¹e list utrhneme. \:Pokud $v$ má jednoho syna $\Rightarrow$ vrchol \uv{vyøízneme}. -\:Jinak má $v$ oba syny $\Rightarrow$ do vrcholu vlo¾íme minimum z $P(v)$, co¾ bude list, a ten utrhneme. +\:Jinak má $v$ oba syny $\Rightarrow$ do vrcholu vlo¾íme minimum z $P(v)$, minimum u¾ +umíme smazat proto¾e je to buï list nebo má jen pravého syna. \endalgo \s{Poznámka:} Pokud má vrchol $v$ pøi operaci {\it Delete} oba syny, je vlo¾ení minima z $P(v)$ ekvivalentní s~vlo¾ením maxima z $L(v)$. +\break + \s{Pøíklady operací {\it Insert} a {\it Delete} na~BVS:} \treepic{1} \treepic{3} -\break Èasová slo¾itost v¹ech tøí operací je $\Theta(\)$, co¾ mù¾e být -$\Theta(n)$, kdy¾ budeme mít smùlu a strom bude (témìø) lineární spojový seznam, nebo -$\Theta(\log{n})$ kdy¾ bude strom pìknì vyvá¾enì vystavìný. Vidíme tedy, ¾e slo¾itost -operací stojí a padá s~hloubkou stromu. Proto by se nám líbilo, aby mìl ná¹ strom v¾dy -hloubku $\Theta(\log{n})$. Podívejme se tedy, jak se dá navrhnout binární vyhledávací -strom, aby tuto podmínku splòoval \dots +Èasová slo¾itost v¹ech tøí operací je $\Theta(\)$, co¾ mù¾e být +$\Theta(n)$, kdy¾ budeme mít smùlu a strom bude (témìø) lineární spojový seznam. +Takovéto degenerované stromy vzniknou snadno, napøíklad pøidáváním setøídìné +posloupnosti. Naopak kdy¾ bude strom pìknì vyvá¾enì vystavìný dostaneme slo¾itost +$\Theta(\log{n})$. Vidíme tedy, ¾e slo¾itost operací stojí a padá s~hloubkou stromu. +Proto by se nám líbilo, aby mìl ná¹ strom v¾dy hloubku $\Theta(\log{n})$. Podívejme se +tedy, jak se dá navrhnout binární vyhledávací strom, aby tuto podmínku splòoval \dots \h{Vyvá¾ené binární vyhledávací stromy} @@ -114,16 +131,16 @@ $\Theta(\log{n})$. setøídìného pole (tedy medián posloupnosti) a dáme ho do~koøene stromu. Jeho syny pak vystavíme rekurzivnì z~levé a pravé pùlky pole. Celá konstrukce tedy trvá $\O(n)$. -\s{Lemma} buï Insert nebo Delete v dokonale vyvá¾eném BVS trvají $\Omega(n)$ (ve +\s{Lemma:} buï {\it Insert} nebo {\it Delete} v dokonale vyvá¾eném BVS trvají $\Omega(n)$ (ve skuteènosti oba, ale dùkaz je mnohem obtí¾nìj¹í). -\proof Nech» $n:=2^k-1$ pak má dokonale vyvá¾ený BVS urèený tvar a je jednoznaèné, co -je v koøeni. Bez újmy na obecnosti mù¾eme pøedpokládat, ¾e nejmen¹í èíslo ve stromì je -$x$ a nejvìt¹í je $x+n-1$. +\proof Nech» $n=2^k-1$. Pak má dokonale vyvá¾ený BVS urèený tvar a je jednoznaèné, co +je v koøeni. Nech» nejmen¹í èíslo ve stromì je $x$ a nejvìt¹í je $x+n-1$. -Proveïme posloupnost operací $$Insert(x+n), Delete(x), Insert(x+n+1), Delete(x+1) +Proveïme posloupnost operací $$\(x+n), \(x), \(x+n+1), +\(x+1) \dots$$ v¾dy se aspoò polovina listù posune o patro vý¹. Víme ¾e listù v na¹em stromì -je $(n+1)/2$. Tedy aspoò jedna z operací Insert nebo Delete trvá $\Theta (n)$. +je $(n+1)/2$. Tedy aspoò jedna z operací {\it Insert} nebo {\it Delete} trvá $\Omega (n)$. Vidíme tedy, ¾e to ná¹ problém pøíli¹ neøe¹í. Potøebovali bychom, aby se strom dal také efektivnì udr¾ovat. Zkusíme proto slab¹í podmínku: @@ -132,13 +149,20 @@ tak v¹echny jeho vrcholy platí: $\left \vert h(L(v)) - h(P(v)) \right \vert \leq 1 $. Stromùm s~hloubkovým vyvá¾ením se øíká {\I AVL stromy} (objeviteli je ru¹tí -matematikové G. M. Adelson-Velsky a E. M. Landis, podle nich jsou také pojmenovány) a +matematikové G. M. Adìµson-Veµskij a E. M. Landis, podle nich jsou také pojmenovány) a platí o~nich následující lemma: \s{Lemma:} AVL strom na~$n$ vrcholech má hloubku $ \Theta(\log{n}) $. \proof Uva¾me posloupnost $A_k = $ minimální poèet vrcholù AVL stromù hloubky $k$. -Staèí ukázat, ¾e $A_k$ roste exponenciálnì. Podívejme se na minimální AVL stromy: +Staèí ukázat, ¾e $A_k$ roste exponenciálnì. + +Jak bude vypadat minimální AVL strom o $k$ hladinách? S poètem hladin urèitì poroste +poèet vrcholù, proto pro ka¾dý vrchol budeme chtít, aby se hloubky jeho synù li¹ily. +Tedy koøen bude mít syna hloubky $k-1$ a syna hloubky $k-2$, takové ¾e jeho synové +jsou minimální AVL stromy o daném poètu hladin. + +Podívejme se na minimální AVL stromy: $$\eqalign{ A_0 &= 1 \cr A_1 &= 2 \cr @@ -152,9 +176,7 @@ Rekurentn podstromy o~hloubkách $k - 1$ a $k - 2$. Vidíme tedy, ¾e $A_n = F_{n + 2} - 1$. (Mù¾eme dokázat napø. indukcí.) Teï nám ji¾ -staèí dokázat, ¾e posloupnost $A_k$ roste exponenciálnì S výhodou mù¾eme vyu¾ít toho, -¾e na první pøedná¹ce jsme si ji¾ dokázali, ¾e Fibonacciho èísla rostou exponenciálnì. -Nicménì pro zapomnìtlivé mù¾eme dùkaz ve struènosti zopakovat: +staèí dokázat, ¾e posloupnost $A_k$ roste aspoò exponenciálnì. 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} @@ -162,7 +184,8 @@ uk 2^{k \over 2} \cdot 1.21 > 2^{k \over 2}.$ Tímto jsme dokázali, ¾e na~ka¾dé hladinì je minimálnì exponenciálnì vrcholù, co¾ nám -zaruèuje hloubku $ \Theta(\log{n})$. +zaruèuje hloubku $\O(\log{n})$. Druhou nerovnost nahlédneme zkoumáním $B_k$ +maximálního poètu vrcholù AVL stromu hloubky $k$. \qed \bye -- 2.39.2