From aef44db91803b19b69a48257834afea659b80fd3 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Mon, 1 Jun 2009 20:45:16 +0200 Subject: [PATCH] Aktualizace stromu. --- 11-stromy/11-stromy.tex | 43 ++++++++++++++++++++++------------------- 1 file changed, 23 insertions(+), 20 deletions(-) diff --git a/11-stromy/11-stromy.tex b/11-stromy/11-stromy.tex index 5251fad..173c36c 100644 --- a/11-stromy/11-stromy.tex +++ b/11-stromy/11-stromy.tex @@ -10,18 +10,18 @@ \prednaska{11}{Vyhledávací stromy}{} -Pøedstavme si následující problém: cheme si udr¾ovat urèitá setøídìná data, napøíklad slovník. Polo¾kami jsou uspoøádané dvojice (klíè, hodnota). Klíèe jsou unikátní a jsou to prvky nìjakého lineárnì uspoøádaného universa. +Pøedstavme si následující problém: potøebujeme si udr¾ovat urèitá setøídìná data, napøíklad slovník. Polo¾kami jsou uspoøádané dvojice (klíè, hodnota). Klíèe jsou unikátní a jsou to prvky nìjakého lineárnì uspoøádaného universa. Hodnoty mohou být libovolné. Na na¹ich datech budeme chtít provádìt následující operace: \itemize\ibull -\:{\it Insert} vlo¾it novou polo¾ku -\:{\it Delete} smazat polo¾ku -\:{\it Find} najít polo¾ku -\:{\it Max $\&$ Min} vybrat polo¾ku s~nejvìt¹ím, resp. nejmen¹ím klíèem -\:{\it Pred $\&$ Succ} vybrat polo¾ku s~klíèem o~jedna men¹ím, resp. vìt¹ím +\:{\it Insert} -- vlo¾it novou polo¾ku +\:{\it Delete} -- smazat polo¾ku +\:{\it Find} -- najít polo¾ku +\:{\it Max $\&$ Min} -- vybrat polo¾ku s~nejvìt¹ím, resp. nejmen¹ím klíèem +\:{\it Pred $\&$ Succ} -- vybrat polo¾ku s~klíèem nejbli¾¹ím men¹ím, resp. vìt¹ím \endlist -Jak by vypadalo nejjednodu¹¹í øe¹ení? Staticky bychom data mohli udr¾ovat v~setøídìném poli. Takové pole se vyrobí v~èase $\Theta(n \cdot log{n})$. Operace {\it Find} by trvala $\Theta(log{n})$ (vyhladávali bychom samozøejmì binárnì). Ale problém by nastal s~operacemi {\it Insert} a {\it Delete}, které by se takto implementovat nedaly, nebo by trvaly hodnì dlouho (napø. v~pøípadì {\it Insert} bychom museli celé pole pøestavìt). +Jak by vypadalo nejjednodu¹¹í øe¹ení? Staticky bychom data mohli udr¾ovat v~setøídìném poli. Takové pole se vyrobí v~èase $\Theta(n \cdot \log{n})$. Operace {\it Find} by trvala $\Theta(\log{n})$ (vyhledávali bychom samozøejmì binárnì). Ale problém by nastal s~operacemi {\it Insert} a {\it Delete}, které by se takto implementovat nedaly, nebo by trvaly hodnì dlouho (napø. v~pøípadì {\it Insertu} bychom museli celé pole pøestavìt). \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. @@ -29,13 +29,13 @@ Jak by vypadalo nejjednodu \s{Definice:} Pro vrchol $v$ znaèíme: \itemize\ibull -\:$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 +\:$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 \endlist -\s{Definice:} {\I Binární vyhledávací strom} (BVS): Binární strom je vyhledávací, pokud v~ka¾dém vrcholu je ulo¾ena dvojice (klíè, hodnota) [ztoto¾níme vrchol s~klíèem] a pro v¹echny vrcholy platí: $\forall u \in L(v) : u < v $ $\&$ $ \forall u \in P(v) : u > v$. +\s{Definice:} {\I Binární vyhledávací strom} (BVS): Binární strom je vyhledávací, pokud v~ka¾dém vrcholu je ulo¾ena dvojice (klíè, hodnota) [ztoto¾níme vrchol s~klíèem] a pro v¹echny vrcholy platí: $\left ( \forall u \in L(v) : u < v \right ) $ $ \&$ $ \left ( \forall u \in P(v) : u > v \right )$. \s{Pøíklady binárních vyhledávacích stromù:} @@ -49,8 +49,8 @@ Jak budou tedy vypadat operace {\it Find}, {\it Insert} a {\it Delete} na~bin \algo \:Pokud $v = \emptyset \Rightarrow$ vrátíme $\emptyset$. \:Pokud $v = x \Rightarrow$ vrátíme $v$. -\:Pokud $v < x \Rightarrow$ vrátíme $Find(p(v),x)$. -\:Pokud $v > x \Rightarrow$ vrátíme $Find(l(v),x)$. +\:Pokud $v < x \Rightarrow$ vrátíme $\(p(v),x)$. +\:Pokud $v > x \Rightarrow$ vrátíme $\(l(v),x)$. \endalgo {\bo Insert$(v,x)$:} @@ -62,7 +62,7 @@ Jak budou tedy vypadat operace {\it Find}, {\it Insert} a {\it Delete} na~bin \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)$, co¾ bude list, a ten utrhneme. \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)$. @@ -72,21 +72,21 @@ Jak budou tedy vypadat operace {\it Find}, {\it Insert} a {\it Delete} na~bin \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, 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 \h{Vyvá¾ené binární vyhledávací stromy} \s{Definice:} {\I Dokonalá vyvá¾enost:} Strom je dokonale vyvá¾ený, pokud pro v¹echny jeho vrcholy platí: $\left \vert \vert L(v)\vert - \vert P(v)\vert \right \vert \leq 1 $. -Takto definovaný binární strom bude mít urèitì logaritmickou hloubku. Jak takový strom ale konstruovat? To se nám podaøí buï staticky a nebo na~nìm budou operace dra¾¹í ne¾ $\Theta(\log{n})$. +Takto definovaný binární strom bude mít urèitì logaritmickou hloubku. Jak takový strom ale konstruovat? To se nám podaøí buï staticky, nebo na~nìm budou operace dra¾¹í ne¾ $\Theta(\log{n})$. -\s{Statická konstrukce dokonale vyvá¾eného BVS:} Vybereme medián posloupnosti a dáme ho do~koøene stromu. Jeho syny pak vystavíme rekurzivnì z~levé a pravé pùlky pole. +\s{Statická konstrukce dokonale vyvá¾eného BVS:} Vybereme prostøední prvek ze 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)$. 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: \s{Definice:} {\I Hloubková vyvá¾enost:} Strom je hloubkovì vyvá¾ený, pokud pro 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} a platí o~nich následující lemma: +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 platí o~nich následující lemma: \s{Lemma:} AVL strom na~$n$ vrcholech má hloubku $ \Theta(\log{n}) $. @@ -101,7 +101,10 @@ A_3 &= 7 \cr A_k &= 1 + A_{k - 1} + A_{k - 2}. \cr }$$ -Rekurentní vzorec jsme dostali rekurzivním stavìním stromu hloubky $k$: nový koøen a 2 podstromy o~hloubce $k - 1$ a $k - 2$. +Rekurentní vzorec jsme dostali rekurzivním stavìním stromu hloubky $k$: nový koøen a 2 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: 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í: -- 2.39.2