(a,b)-stromy Dals dulezitou datovou strukturou vhodnou pro resen slovnkoveho problemu (reprezentace mnoziny, ktera pripoust operace MEMBER, INSERT a DELETE), kterou lze pouzt jak pro intern tak extern pamet, jsou (a; b)-stromy. Je to struktura zalozena na stromech. Nejobecnejs grafova de nice (a; b)-stromu je: Necht a b jsou kladna prirozena csla. Pak korenovy strom (T; t) se nazyva (a; b)-strom, kdyz (1) kdyz v je vnitrn vrchol stromu T ruzny od korene t, pak ma alespon a a nejvyse b synu; (2) vsechny cesty z korene do libovolneho listu maj stejnou delku. Tato de nice je prlis obecna a pro datove struktury se nehod. Proto pouzvame jej specialn prpad. Pro nas (a; b)- stromy jsou takto de novane: Necht a a b jsou prirozena csla takova, ze 2 a a 2a 1 b. Pak korenovy strom (T; t) se nazyva (a; b)-strom, kdyz (1) kdyz v je vnitrn vrchol stromu T ruzny od korene t, pak ma alespon a a nejvyse b synu; (2) koren je bud list nebo ma alespon dva syny a nejvyse b synu; (3) vsechny cesty z korene do libovolneho listu maj stejnou delku. Vyhody nasich (a; b)-stromu: Kdyz ma (a; b)-strom vysku h > 0 (tj. delka kazde cesty z korene do libovolneho listu ma delku h), pak strom ma alespon 2ah 1 listu a nejvyse bh listu. Tvrzen. Mejme prirozena csla a a b takova, ze a 2 a b 2a 1. Pak pro kazde kladne prirozene cslo n existuje (a; b)-strom, ktery ma presne n listu. Kdyz (a; b)-strom ma presne n listu, pak vyska stromu je nejvyse 1 + loga( n2 ) a je alespon logb n. Tedy vyska stromu je O(log n). Mejme korenovy strom (T; t) takovy, ze pro kazdy vnitrn vrchol v plat: kdyz ma (v) synu, pak jsou ocslovany od 0 do (v) 1. R ekneme, ze vrchol v je v hloubce h, kdyz cesta z korene t do v ma delku h. Mnozina vsech vrcholu v hloubce h se nazyva h-ta hladina. Lexikogra cke usporadan na h-te hladine je de novano rekurzivne: v w, prave kdyz bud otec(v) < otec(w), nebo otec(v) = otec(w) a kdyz v je i-ty syn otec(v) a w je j -ty syn otec(v); pak i j . Predpokladame, ze v (a; b)-stromu synove kazdeho vnitrnho vrcholu jsou usporadany. Listy tvor hladinu h, kde h je hloubka (a; b)-stromu, a na nich je de novano lexikogra cke usporadan. Mejme linearne usporadane universum U a mnozinu S U . (a; b)-strom (T; t) reprezentuje mnozinu S , kdyz ma presne jS j listu a je dana bijekce prvku z mnoziny listu T na S zachovavajc a re ektujc usporadan (tj. bijekce : list(T ) ! S pro s; t 2 S splnuje s t v U , prave kdyz 1 (s) 1(t) v lexikogra ckem usporadan na mnozine listu stromu T ). Struktura vnitrnch vrcholu (a; b)-stromu (T; t) reprezentujcho mnozinu S U : (v) { pocet synu vrcholu v, Sv (0::(v) 1) { pole ukazatelu na syny vrcholu v takove, ze Sv (i) je i-ty syn vrcholu v pro Typeset by
AMS-TEX
2
i = 0; 1; : : : ; (v) 1, Hv (0::(v) 2) { pole prvku z U takove, ze Hv (i) je nejvets prvek z S reprezentovany v podstromu i-teho syna vrcholu v (alternativa: Hv (i) je prvek z U takovy, ze nejvets prvek reprezentovany v podstromu i-teho syna vrcholu v je mens nebo roven Hv (i) a to je mens nez nejmens prvek reprezentovany v podstromu (i + 1)-nho syna vrcholu v). Struktura listu: listu v je prirazen prvek (v) 2 S . Nekdy je ve strukture kazdeho vrcholu v (a; b)-stromu ruzneho od korene jeste ukazatel otec(v) na otce vrcholu v. Kdyz Hv (i) jsou prvky z reprezentovane mnoziny, pak pro kazdy prvek s 2 S krome nejvetsho existuje prave jeden vnitrn vrchol v (a; b)-stromu a jedno i, ze Hv (i) = s, a nejvets prvek v S nen prvek Hv pro zadny vrchol v. Tento fakt se pouzva pri implementaci, kde se vynechavaj listy. Prvky z S jsou reprezentovany v polch Hv , v je vnitrn vrchol stromu, a nejvets prvek je ulozen vedle. Je to prostorove efektivnejs reprezentace mnoziny S , ale je technicky neprehledna. Proto pri praci s (a; b)-stromy budeme pouzvat popis s listy. Nyn uvedeme algoritmy pro (a; b)-stromy. Nejprve pomocny algoritmus
Vyhledej(x) t :=koren stromu T , while t nen list do i := 1 while Ht (i) < x & i < (t) do i := i + 1 if Ht (i) = x then w := t endif enddo t := St(i) enddo Vystup: t a w. MEMBER(x) Vyhledej(x) if (t) = x then x 2 S else x 2= S endif INSERT(x) Vyhledej(x) if (t) 6= x then 0 0 vytvor novy list t , (t ) = x, u := otec(t) if (t) < x then (komentar: x > max S ) Su((u) + 1) := t0 , Hu((u)) := (t), (u) := (u) + 1 else najdi i, ze Su(i) = t Su((u) + 1) := S ((u)), j := (u) 1 while j i do Su(j + 1) := Su(j ), Hu(j + 1) := Hu (j ), j := j 1 enddo 0 Su(i) := t , Hu (i) := x, (u) := (u) + 1 endif t := u while (t) > b do Stepen(t) enddo endif Stepen(t) if t je koren stromu then
3
vytvor novy koren u s jedinym synem t endif u := otec(t), najdi i, ze Su(i) = t, vytvor novy vnitrn vrchol t0 , j := 1 while j < b b+1 c do 2 e), Ht0 (j ) := Ht (j + d b+1 e), j := j + 1 St0 (j ) := St(j + d b+1 2 2
enddob
St0 (b +1 c) := St(b + 1), (t) := d b+1 e, (t0 ) := b b+1 c, 2 2 2 Su((u) + 1) := Su((u)), j := (u) 1, (u) := (u) + 1, while j > i do Su(j + 1) := Su(j ), Hu(j + 1) := Hu (j ), j := j 1
enddo
Su(i + 1) := t0, Hu(i + 1) := Hu (i), Hu (i) = Ht ((t)), t := u DELETE(x) Vyhledej(x) if (t) = x then u := otec(t), najdi i, ze Su(i) = t, a j , ze Hw (j ) = x, Hw (j ) := Hu(i 1), k := i while k < (u) 1 do Hu(k) := Hu(k 1), Su(k) := Su(k 1), k := k 1
enddo
Su((u) 1) := Su((u)), (u) := (u) 1, odstran t, t := otec(t) while (t) < a a t nen koren do y je bezprostredn bratr t if (y) = a then Spojen(t; y) else Presun(t; y) endif
enddo Spojen(t; y) u := otec(t), najdi i, ze Su(i) = t if Su(i 1) = y then vymen t a y, i := i 1 endif j := 1 while j < (y) do St((t) + j ) = Sy (j ), Ht ((t) + j ) := Hy (j ), j := j + 1 enddo Ht ((t)) = Hu(i), (t) := (t) + (y), odstran y while i (u) do Su(i + 1) := Su(i + 2), Hu (i) := Hu(i + 1), i := i + 1 enddo (u) := (u) 1, if u je koren a (u) = 1 then odstran u else t := u endif
4
Presun(t; y) u := otec(t), najdi i takove, ze Su(i) = t if Su(i + 1) = y then St((t) + 1) := Sy (1), Ht ((t)) := Hu (i), Hu(i) := Hy (1), j := 1 while j < (y) 1 do Sy (j ) := Sy (j + 1), Hy (j ) := Hy (j + 1), j := j + 1
enddo Sy ((y) 1) := Sy ((y)), (t) := (t) + 1, (y) := (y) 1 else St((t) + 1) := St((t)), j := (t) 1 while j > 0 do St(j + 1) := St(j ), Ht (j + 1) := Ht (j ), j := j 1 enddo (t) := (t) + 1, St (1) := Hy ((y)), Ht (1) := Hu(i 1), Hu(i 1) := Hy ((y) 1), (y) := (y) 1 endif Odkaz na otce vrcholu: bud je v kazdem vrcholu v stromu T prmo odkaz na otec(v), nebo se v procedure Vyhledej vkladaj vrcholy do zasobnku a otec(v) je vrchol v zasobnku pred vrcholem v. Veta. Algoritmy MEMBER, INSERT a DELETE pro (a; b)-stromy vyzaduj v nejhorsm prpade cas O(loga jS j), kde S je reprezentovana mnozina. Nyn popseme algoritmy pro dals operace. Jedna z uzitecnych operac je nalezen k-teho nejmensho prvku v mnozine S . Tato operace se nazyva vyhledan k-te poradkove statistiky. Tato operace nen podporovana navrzenou strukturou, pro jej efektivn implementaci musme rozsrit strukturu vnitrnho vrcholu v o pole Pv (1::(v) 1), kde Pv (i) je pocet prvku S reprezentovanych v podstromu i-teho syna vrcholu v. Udrzovat pole Pv v aktualnm stavu znamena pri uspesnem proveden aktualizacn operace projt cestu z vrcholu do korene a aktualizovat pole P . Nyn uvedeme algoritmus pro nalezen k-te poradkove statistiky.
k-STATISTICS if k > jS j then neexistuje k-ty nejmens prvek, konec endif t :=koren stromu while t nen list do i := 1 while k > Pt(i) & i < (t) do i := i + 1, k := k Pt(i) enddo t := St(i) enddo (t) je hledany k-ty nejmens prvek Invariant algoritmu: V kazdem okamziku plat, ze puvodn k se rovna k+pocet prvku z S , ktere jsou v podstromu vrcholu stromu, ktery v lexikogra ckem usporadan predchaz i-teho syna vrcholu t. Korektnost algoritmu plyne z tohoto invariantu. Veta. Implementace operac MEMBER, INSERT, DELETE a k-STATISTICS v rozsrene strukture (a; b)-stromu vyzaduje v nejhorsm prpade cas O(log jS j), kde S je reprezentovana mnozina.
5
Dals vysetrovane operace jsou JOIN a SPLIT. Mejme dva (a; b)-stromy T1 a T2 reprezentujc mnoziny S1 a S2 takove, ze max S1 < min S2 (to znamena, ze plat silnejs podmnka, nez ze S1 a S2 jsou disjunktn). Operace JOIN(T1 ; T2) vytvor (a; b)-strom T reprezentujc mnozinu S = S1 [ S2. Operace SPLIT(T; x), kde T je (a; b)-strom reprezentujc mnozinu S a x je prvek z U , vytvor (a; b)-stromy T1 a T2 reprezentujc mnoziny S1 = fs 2 S j s < xg a S2 = fs 2 S j s > xg a oznam, zda x patrilo do S .
JOIN(T ; T ) if vyska T je vets nebo rovna vysce T then t :=koren T , k :=vyska T - vyska T while k > 0 do t := St((t)), k := k 1 endo Spojen(t;koren T ), t := otec(t) while (t) > b do Stepen(t) enddo else t :=koren T , k :=vyska T - vyska T while k > 0 do t := St(1), k := k 1 enddo Spojen(t;koren T ), t := otec(t) while (t) > b do Stepen(t) enddo endif Operace JOIN navstv pocet vrcholu rovny rozdlu vysek stromu. Protoze kazdy vr1
2
1
2
1
1
2
2
2
2
1
1
chol zpracuje v case O(1), vyzaduje cas O(log(jS1j + jS2j)), kde S1 je mnozina reprezentovana (a; b)-stromem T1 a S2 je mnozina reprezentovana (a; b)-stromem T2 . Nelze dat koren mensho stromu jako syna vhodneho vrcholu vetsho stromu, protoze koren nesplnuje podmnky kladene na vnitrn vrcholy (a; b)-stromu. Proto je vhodne pouzt operaci Spojen. V nasledujcm algoritmu vyuzijeme fakt, ze operace JOIN vyzaduje jen cas O(jvyska(T1 ) vyska(T2)j).
6
SPLIT(T; x) Z1, Z2 prazdne zasobnky, t :=koren T while t nen list do i := 1 while Ht (i) < x & i < (t) do i := i + 1 enddo t := St(i) if i = 2 then vloz podstom vrcholu St(1) do Z1 endif if i > 2 then vytvor novy vrchol t1, (t1) = i 1, for every j = 1; 2; : : : ; i 2 do St1 (j ) := St(j ), Ht1 (j ) := Ht (j ) enddo St1 (i 1) := St (i 1), vloz podstrom vrcholu t1 do Z1
endif if i := (t) 1 then vloz podstrom St ((t)) do Z endif if i < (t) 1 then vytvor novy vrchol t , (t ) := (t) i for every j = 1; 2; : : : ; (t) i 1 do St2 (j ) := St(i + j ), Ht2 (j ) := Ht (i + j ) enddo St2 ((t) i) := St((t)), vloz podstrom t do Z endif enddo if (t) = x then x patrilo do S else x nepatrilo do S if (t) < x then vloz podstrom vrcholu t do Z else vloz podstrom vrcholu t do Z endif endif T :=vrchol Z , odstran T ze Z while Z 6=0 ; do T 0 :=vrchol Z 0, odstran T ze Z , T :=JOIN(T ; T ) enddo T :=vrchol Z , odstran T ze Z while Z 6=0 ; do T 0 :=vrchol Z , 0 odstran T ze Z , T :=JOIN(T ; T ) enddo 2
2
2
2
2
1
2
1
1
1
1
1
2
1
1
1
2
1
2
2
2
2
2
2
2
7
Rozdelen T do zasobnku Z1 a Z2 v algoritmu SPLIT vyzaduje cas O(log jS j). Po skoncen teto faze algoritmu je posloupnost vysek stromu, jak jsou v zasobnku Z1 nebo Z2, neklesajc a mens nebo rovna vysce T . Proto cas algoritmu na vytvoren T1 a T2 je O(vyska T ). Shrnme tato fakta. Veta. Implementace algoritmu pro operace JOIN a SPLIT v (a; b)-stromech v nejhorsm prpade vyzaduje cas O(log jS j). (a; b)-stromy se pouzvaj jak v intern tak v extern pameti. Jake hodnoty a a b je vhodne pouzvat? Pro intern pamet jsou doporucene hodnoty a = 2, b = 4 nebo a = 3 a b = 6. Pro extern pamet jsou doporucene hodnoty a 100, b = 2a. Kdyz je mnozina reprezentovana (a; b)-stromem ulozena na serveru a ma k n prstup vce uzivatelu, vznika problem s aktualizacnmi operacemi. Tyto operace men strukturu (a; b)stromu a ve svych dusledcch se v nem jiny uzivatel muze ztratit. Tento problem se muze resit tak, ze pri aktualizacnch operacch se uzavre cely strom. Nevyhoda: ostatn uzivatele do neho nemaj prstup a nemohou pracovat. Tzv. paraleln implementace operac INSERT a DELETE nabz jine, efektivnejs resen. Predpoklad: b 2a. Pri operaci INSERT jsou ve vyhledavac fazi vzdy uzavreny vrcholy t, otec(t) a synove vrcholu t, algoritmus zjist, v kterem synu vrcholu t ma pokracovat, a pak, kdyz (t) = b, provede Stepen (proto nutne je b 2a, abychom po teto operaci meli zase (a; b)-strom). V algoritmu pak odpadne vyvazujc cast (tj. Stepen pri ceste vzhuru ke koreni). Pri operaci DELETE jsou ve vyhledavac fazi uzavreny vrcholy t, otec(t) a bezprostredn bratr y vrcholu t. Kdyz (t) = a, pak po nalezen vrcholu, kde se bude pokracovat, se provede bud Presun (kdyz (y) > a) nebo Spojen (kdyz (y) = a) a vynecha se vyvazovac cast uzavrajc puvodn algoritmus. Tato uprava vyzaduje sice vce Stepen, Spojen a Presun u, ale asymptoticky vychaz cas stejny (je jen vets multiplikativn konstanta). Doporucene hodnoty a a b jsou a 100 a b = 2a + 2 pri ulozen na serveru v extern pameti, kdyby to bylo ve vnitrn pameti, pak se doporucuje a = 2, b = 6. (a; b)-stromy davaj take zajmave aplikace pro trdic algoritmy. Pouzit (a; b)-stromu pro setrden nahodne posloupnosti nen vhodne, rezie na udrzovan struktury (a; b)-stromu vede k tomu, ze multiplikativn konstanta by byla o hodne vets nez u klasickych trdicch algoritmu, take ulozen (a; b)-stromu vyzaduje vce pameti nez je potreba pro klasicke algoritmy. Situace se podstatne zmen, kdyz vstupn posloupnost je predtrdena a je ji treba jen dotrdit. Klasicke algoritmy vetsinou nejsou schopne vyuzt faktu, ze posloupnost je predtrdena, a jejich casova narocnost je prakticky stejna (nekdy i hors) jako u nahodne posloupnosti. Na rozdl od nich algoritmus A-sort zalozeny na (a; b)-stromech je schopen predtrdenost vyuzt a ma na predtrdenych posloupnostech leps vysledky nez klasicke algoritmy. Modi kace (a; b)-stromu pro algoritmus A-sort. Mame (a; b)-strom reprezentujc vstupn posloupnost, je dan ukazatel Prv na prvn list, listy (a; b)-stromu jsou propojeny do seznamu v rostoucm lexikogra ckem porad (ukazatel na nasledujc prvek je Nasl) a je dana cesta z prvnho listu do korene (to znamena, ze na ceste z prvnho listu do korene zname pro kazdy vrchol v jeho otce). Nyn uvedeme algoritmus A-sort.
8
A-sort(x1; x2 ; : : : ; xn) i := n while i 1 do A-Insert(xi ), i := i 1 enddo i := 1, t := Prv, y1 := (t) while i n do yi := (t), i := i + 1, t := Nasl(t) enddo A-Insert(x) t := Prv while t 6=koren T & Ht (1) < x do t := otec(t) enddo while t 6=list do i := 1 while Ht (1) < x & i < (t) do i := i + 1 enddo t := St(i) if i > 1 then v := St(i 1) else if v je de novano then v := Su((u))
endif endif enddo if (t) 6= x then 0 0 vytvor novy list t , (t ) = x, u := otec(t) if (t) < x then 0(komentar: x > max S )
Su((u) + 1) := t , Hu((u)) := (t), (u) := (u) + 1, Nasl(t) := t0 , Nasl(t0 ) := NIL else najdi i, ze Su(i) = t, 0Su((u) 0+ 1) := S ((u)), j := (u) 1, Nasl(v) := t , Nasl(t ) := t while j i do Su(j + 1) := Su(j ), Hu(j + 1) := Hu (j ), j := j 1
enddo 0 Su(i) := t , Hu (i) := x, (u) := (u) + 1, if t = Prv then Prv := t0 endif endif t := u while (t) > b do Stepen(t) enddo endif
(y1 ; y2 ; : : : ; yn) je setrdena posloupnost (x1 ; x2 ; : : : ; xn )
Korektnost algoritmu plyne z faktu, ze je izomor smus usporadan a seznam listu je v rostoucm porad. Protoze v je vzdy bezprostredn predchudce t, je seznam korektne de novan. Ukazatel otec(v) je resen na ceste z vrcholu Prv do korene, pro ostatn vrcholy se res stejnym zpusobem jako pro (a; b)-stromy. Slozitost algoritmu: Zrejme algoritmus A-sort v nejhorsm prpade vyzaduje cas, ktery potrebuje A-Insert, plus O(n). Algoritmus A-Insert(x) vyzaduje cas potrebny na nalezen msta, kam vlozit x, plus O(pocet volan Stepen). Protoze kazdy beh procedury Stepen vytvoril jeden vnitrn list (a; b)-stromu a protoze a 2 a (a; b)-strom po skoncen volan A-Insert ma n listu, je vnitrnch vrcholu (a; b)-stromu < n. Proto vsechny behy procedury A-Insert vyzadovaly cas na nalezen mst jednotlivych prvku plus O(n). Kdyz procedura A-Insert(x) pri hledan msta pro prvek x skoncila ve vysce h (tj. prvn cyklus se h-krat opakoval), pak nalezen msta pro prvek x vyzadovalo cas O(h). Vsechny prvky reprezentovane (a; b)-stromem pod prvnm vrcholem ve vysce h 1 jsou mens nez x a je jich alespon ah 2 . Kdyz x = xi , pak pocet prvku reprezentovanych (a; b)-stromem pri behu procedury A-Insert(x), ktere jsou mens nez x, je jfj = i + 1; i + 2; : : : ; n j xj < xi gj. Oznacme
9
fi = jfj = i + 1; i + 2; : : : ; n j xj < xi gj. Pak plat ah 2 fi =) h 2 loga fi =) h 2 O(log fi ): Odtud cas v P nejhor sm prpade potrebny pro nalezen pozice xi je O(log fi ). C as algoritmu n A-sort je O( i=1 log fi + n). Vyuzijeme toho, ze aritmeticky prumer nen nikdy mens nez geometricky, a dostaneme Pn n n n Y X Y fi = n log F ; 1 n log fi = log fi = n log( fi ) n log i=1 n n i=1 i=1 i=1
kde F = ni=1 fi = jf(i; j ) j i < j; xi > xj gj. Kdyz posloupnost (x1 ;x2 ; : : : ; xn ) je rostouc, pak F = 0, kdyz posloupnost (x1 ; x2 ; : : : ; xn ) je klesajc, pak F = n2 . Obecne 0 F n2 . Proto velicinu F lze povazovat za mru setrdenosti posloupnosti (x1 ; x2 ; : : : ; xn ). Veta. Algoritmus A-sort na setrden n-clenne posloupnosti vyzaduje v nejhorsm prpade F cas O(n + n log n ), kde F je mra setrdenosti vstupn posloupnosti. P
Zhodnocen: Protoze A-sort nepouzva operaci DELETE, doporucuje se pouzt (2; 3)stromy. Kdyz se budou trdit posloupnosti s mrou F n log n, pak algoritmus A-sort bude potrebovat v nejhorsm prpade cas O(n log log n). Mehlhorn a Tsakalidis dokazali, ze kdyz F 0:02n1:57, pak algoritmus A-sort je rychlejs nez algoritmus Quicksort.
Propojene (a,b)-stromy s prstem Propojeny (a; b)-strom s prstem je (a; b)-strom, kde struktura vnitrnho vrcholu ruzneho od korene nebo listu je rozsrena (proti klasickemu (a; b)-stromu) o ukazatele: otec(v), levy(v), pravy(v), kde ukazatel levy(v) ukazuje na nejvets vrchol (v lexikogra ckem usporadan) ve stejne hladine jako v, ktery je mens nez v (kdyz neexistuje, tak je to NIL), a ukazatel pravy(v) ukazuje na nejmens vrchol (v lexikogra ckem usporadan) ve stejne hladine jako v, ktery je vets nez v (kdyz neexistuje, tak je to NIL). Navc je dan ukazatel Prst na nektery list. Zde se lis hlavne vyhledavan, ktere je zobecnenm prstupu v A-sortu. Zacna od listu, na ktery ukazuje Prst. Kdyz x je mens nez prvek reprezentovany tmto listem, pak se pokracuje v otci, a kdyz puvodn vrchol byl i-ty syn, tak se pomoc pole H zjistuje, zda x nema byt reprezentovan v podstromu j -teho syna pro j < i, a kdyz nen, tak se pokracuje s ukazatelem levy dal. Kdyz x nen reprezentovan ani v tomto podstromu, tak se cely postup opakuje (zkouma se otec vrcholu). Kdyz x je vets nez prvek reprezentovany listem, na ktery ukazuje Prst, je postup obraceny. Kdyz se nalezne vrchol, v jehoz podstromu ma x lezet, pak se aplikuje od tohoto vrcholu msto od korene procedura Vyhledej. Tato struktura krome operac MEMBER, INSERT a DELETE jeste pouzva operaci PRST(x), ktera nastav ukazatel Prst na list, ktery reprezentuje nejmens prvek vets nebo rovny x (pokud x > max S , tak ukazatel Prst bude ukazovat na nejvets list). Operace provedou vyhledan a pak pokracuj klasickym zpusobem. Pouzit: Tato struktura je velmi vyhodna pro ulohy, kde operace jsou rozdeleny do segmentu, ktere pracuj v blzkem okol nejakeho x 2 U . Pak vyhledan prvku je rychlejs nez v klasickem (a; b)-stromu, viz A-sort.
10
Vyvazovac operace: Stepen, Spojovan, Presun. Vme, ze jedna operace INSERT muze provest nejvyse log(jS j) operac Stepen a jedna operace DELETE muze provest nejvyse log(jS j) operac Spojen a nejvyse jednu operaci Presun. Je videt, ze tyto odhady nejdou zlepsit. Pro vhodny typ (a; b)-stromu vsak amortizovany pocet vyvazovacch operac z puvodne prazdneho stromu je konstantn. Pro pevne a a b oznacme
c = minfminf2a 1; d b +2 1 eg a; b maxf2a 1; b b +2 1 cgg: Vyska vrcholu v korenovem strome je maximaln delka cesty z neho do nektereho listu. Veta. Necht b 2a a a 2. Necht P je posloupnost n operac INSERT a DELETE, aplikujme ji na prazdny (a; b)-strom. Oznacme P Sth { pocet Stepen ve vysce h pri aplikaci P a St = Ph Sth; Sph{ pocet Spojen ve vysce h pri aplikaci P a Sp = Ph Sph; Ph { pocet Presunu ve vysce h pri aplikaci P a P = h Ph . Pak plat (1) P n a (2c 1)St + cSp n + c + ca(+nc 2)1 ; +2)n (2) Sth + Sph + Ph 2((cc+1) h . Z de nice plyne, ze c 1, a tedy z 2) dostaneme St + Sp nc + 1 + na 2 2n + 1. Tedy amortizovany pocet vyvazovacch operac je lim P + Stn + Sp 52 :
n7!1
Dukaz je zalozen na bankovnm principu { navrhneme kvantitativn ohodnocen (a; b)stromu, nalezneme horn odhad tohoto ohodnocen a popseme, jak toto ohodnocen men vyvazovac operace. Srovnan techto odhadu da pozadovany vysledek. Mejme (a; b)-strom T , pak pro vnitrn vrchol v 6=koren de nujme
b(v) = minf(v) a; b (v); cg a pro koren r de nujme
b(r) = minf(r) 2; b (r); cg:
Pozorovan. Pro vnitrn vrchol stromu v ruzny od korene plat (1) (2) (3) (4)
b(v) c; kdyz (v) = a nebo (v) = b, pak b(v) = 0; kdyz (v) = a 1 nebo (v) = b + 1, pak b(v) = 1; kdyz (v) = 2a 1, pak b(v) = c.
11
ea Kdyz v0 a v00 jsou dva ruzne vrcholy stromu ruzne od korene takove, ze (v0 ) = d b+1 2 b +1 00 0 00 (v ) = b 2 c, pak b(v ) + b(v ) 2c 1. b(korene) c. Strom (T; r) ohodnotme
b h (T ) =
X
fb(v) j v 6= r vnitrn vrchol stromu T ve vysce hg; b(T ) =
1 X h=1
bh (T ) + b(r):
R ekneme, ze (T; r; v) je parcialn (a; b)-strom, kdyz r je koren stromu, v je vnitrn vrchol T ruzny od r a plat: a 1 (v) b + 1 a 2 (r) b; kdyz t je vnitrn vrchol T ruzny od v a r, pak a (t) b; vsechny cesty z korene r do nejakeho listu maj stejnou delku. Nyn rozdelme operace INSERT a DELETE do jednotlivych akc se stromem a vysetrme vliv techto akc na ohodnocen stromu. Dukazy lemmat jsou zalozene na nasledujcm pozorovan Pozorovan. Kdyz v a v0 jsou vnitrn vrcholy stromu T a T 0 ruzne od jejich korenu, pak plat: (1) kdyz (v) = (v0 ), pak bT 0 (v0 ) = bT (v); (2) kdyz j(v) (v0 )j = 1, pak bT 0 (v0 ) bT (v) 1.
Lemma 1. Kdyz (T; r) je (a; b)-strom a kdyz strom T 0 vznikne z T pridanm/ubr anm 0
jednoho syna vrcholu v ve vysce 1 (pak pridavany/ubrany syn je list), pak (T ; r; v) je parcialn (a; b)-strom a plat b1(T 0 ) b1 (T ) 1 a bh (T 0 ) = bh (T ) pro h > 1; b(T 0 ) b(T ) 1:
Lemma 2. Necht (T; r; v) je parcialn (a; b)-strom, (v) = b +1 a v je ve vysce l 1. Kdyz 0 0 T vznikne z T operac Stepen(v), pak (T ; r; otec(v)) je parcialn (a; b)-strom a plat: bl (T 0 ) bl (T ) + 2c; bl+1 (T 0 ) bl+1(T ) 1; bh (T 0 ) = bh (T ) pro h 6= l; l + 1; b(T 0 ) b(T ) + 2c 1:
Lemma 3. Necht (T; r; v) je parci aln (a; b)-strom, (v) = a 1, v je ve vysce l 1 a y 0 je bezprostredn bratr v. Kdyz T vznikne z T operac Spojen(v; y) (tedy (y) = a), pak 0 (T ; r; otec(v)) je parcialn (a; b)-strom a plat: bl (T 0 ) bl (T )+c+1; bl+1(T 0 ) bl+1(T ) 1; bh (T 0 ) = bh (T ) pro h 6= l; l+1; b(T 0 ) b(T )+c:
Lemma 4. Necht (T; r; v) je parci aln (a; b)-strom, (v) = a 1, v je vysce l 1 a y je bezprostredn bratr v. Kdyz T 0 vznikne z T operac Presun(v; y) (tedy (y) > a), pak 0
(T ; r) je (a; b)-strom a plat: bl(T 0 ) bl(T ) a bh (T 0 ) = bh (T ) pro h 6= l; b(T 0 ) b(T ):
Oznacme Tk (a; b)-strom vznikly provedenm posloupnosti P na prazdny (a; b)-strom. Sectenm predchozch vysledku dostavame
12
Dusledek 5. Kdyz polozme St0 + Sp0 = pocet listu v Tk n; pak bh (Tk ) 2cSth + (c + 1)Sph Sth 1 Sph 1 pro h 1: Dale b(Tk ) (2c 1)St + cSp n. Prvn vyraz upravme (vyuzvame, ze c 1): Sph 1 bh (Tk ) + bh 1 (Tk ) + Sth 2 + Sph Sth + Sph bch (+Tk1) + Sth 1c + +1 c + 1 (c + 1)2 (c + 1)2 hX1 b (T ) h l X n ( c + 1) h i k + n bl (Tk ) (c + 1)h+1 : i+1 (c + 1)h = (c + 1)h + i=0 (c + 1) l=1
2
Nyn odhadneme shora b(Tk ). Lemma 6. Kdyz T je (a; b)-strom s m listy, pak 0 b(T ) c + (m 2) a+cc 1 . Dukaz. Pro 0 j < c oznacme mj pocet vnitrnch vrcholu ruznych od korene, ktere maj presne a + j synu, a mc oznacme pocet vnitrnch vrcholu ruznych od korene, ktere maj alespon a + c synu. Kdyz vrchol v m u, pak bT (v) j a pro kazdy vnitrn vrchol Paca + j syn v plat bT (v) c. Tedy b(T ) c + j=0 jmj . Z vlastnost stromu plyne 2+
c X
(a + j )mj
X
f(v) j v je vnitrn vrchol T g = m +
c X
mj :
j =0 j =0 P Odtud plyne cj=0(a + j 1)mj m 2: Protoze a+jj 1 a+cc 1 pro kazde j takove, ze 0 j c, dostavame c c X X b(T ) c + jmj = c + a + jj 1 (a + j 1)mj c + a + cc 1 (m j =0 j =0
2)
a lemma je dokazano. Nyn dokazeme tvrzen (1) Vety. Protoze kazda operace DELETE pouzije nejvyse jednu operaci Presun (a operace INSERT operaci Presun nepouzva) dostavame, ze
P pocet operac DELETE n a prvn nerovnost plat. Abychom dokazali druhou nerovnost, spojme druhe tvrzen v Dusledku 5 a Lemma 6 (Tk ma nejvyse n listu) (2c 1)St + cSp n b(Tk ) c + (n 2) a + cc 1 Odtud plyne pozadovana nerovnost a (1) je dokazano. Dukaz (2) vyuzije nasledujc odhad.
13
Lemma 7. Pro kazde h 1 a pro kazdy (a; b)-strom T s m listy plat h X l=1
bl(T )(c + 1)l (c + 1)m:
Dukaz. Pro 0 j < c a pro libovolne h oznacme mj (h) pocet vrcholu ve vysce h ruznych od
korene, ktere maj presne a + j synu, a mc(h) pocet vrcholu ve vysce h ruznych od korene, ktere maj alespon a + c synu. Pak mame
b h (T )
c X j =0
kde dode novavame Plat
jmj (h) a Pc
c X j =0
(a + j )mj (h)
j =0 mj (0) =
c X j =0
mj (h 1) pro kazde h 1;
m. Tyto vztahy pouzijeme v nasledujcm odhadu.
h X
h c X X l l jmj (l) bl (T )(c + 1) (c + 1) j =0 l=1 l=1 c h c X X X l mj (l 1) a mj (l) = (c + 1) j =0 j =0 l=1 c c X X (c + 1) mj (0) (c + 1)h a mj (h)+ j =0 j =0 hX1 c c X X mj (l) c +a 1 mj (l) (c + 1)m; (c + 1)l+1 j =0 j =0 l=1 P kde rovnost jsme zskali prerovnanm sctancu tak, aby vyrazy cj=0 mj (l) byly u sebe, a a 1, a tedy druhy sctanec v predchozm vyrazu je posledn nerovnost plyne z toho, ze c+1
nekladny. Kombinujeme odhad Sth + Sph s Lemmatem 7 a dostaneme h l X n (c + 1) = 2n : Sth + Sph (c + 1)h + bl (Tk ) (c(c++1)1)h+1 (c +n1)h + (cn+ 1)h+1 (c + 1)h l=1 2n Protoze Ph Sph 1 Sph Sth 1 + Sph 1 (c+1) avame, ze h 1 dost Sth + Sph + Ph (c +2n1)h + (c +21)n h 1 = 2n +(c 2+n(1)c h+ 1) = 2(nc(+c +1)2) h a dukaz (2) ve Vete je hotov. Veta vysvetluje, proc jsou doporucene hodnoty b 2a { pak je pocet vyvazovacch operac behem posloupnosti operac INSERT a DELETE linearn vzhledem k delce posloupnosti. Kdyz b = 2a 1, pak lze lehce nalezt posloupnost operac INSERT a DELETE o delce n takovou, ze jej aplikace na prazdny (a; b)-strom vyzaduje pocet vyvazovacch operac umerny n log n (pro kazde dostatecne velke n). Podobna veta plat i pro paraleln implementaci (a; b)-stromu, ale plat za predpokladu b 2a + 2. Pro b = 2a nebo b = 2a + 1 lze nalezt posloupnost, ktera je protiprkladem. Proto se doporucuje hodnota b = 2a + 2 pro paraleln implementaci (a; b)-stromu. Pro propojovane (a; b)-stromy plat silnejs verze.
14
Veta. Predpokladejme, ze b 2a a a 2. Mejme propojovany (a; b)-strom s prstem T , ktery reprezentuje n-prvkovou mnozinu. Pak posloupnost P operac MEMBER, INSERT, DELETE a PRST aplikovana na T vyzaduje cas O(log(n) + cas na vyhledan prvku): Vysvetlen: Zacname v libovolnem propojovanem (a; b)-strome T , proto jeho struktura muze byt nevyhodna pro posloupnost operac P . Abychom se dostali do vhodneho rezimu, muze byt potreba az log(n) vyvazovacch operac. C as na vyhledavan nemuzeme ovlivnit, ten mus ovlivnit uzivatel. Vyvazovan pri operaci INSERT lze provadet tak, ze operace Stepen(t) se provede, jen kdyz oba bratri vrcholu t maj b synu. Jinak se provad operace Presun. Nevm o zadnem serioznm pokusu tyto alternativy porovnat.
Vyhledavan v usporadanem poli Zadan ulohy: Mame podmnozinu S linearne usporadaneho univerza a S je ulozena v poli A[1::jS j] tak, ze pro i < j je A(i) < A(j ). Pro dane x 2 U mame zjistit, zda x 2 S (operace MEMBER(x)). R esen: Pokud x < A(1) nebo A(jS j) < x, pak x nen prvkem S . V opacnem prpade mame dve hodnoty d a h takove, ze 1 d < d + 1 < h jS j a A(d) < x < A(h). Pak zskame hodnotu n takovou, ze d < n < h, a dotazem zjistme, zda x = A(n) (pak koncme a x 2 S ), nebo x < A(n) (polozme h = n) nebo x > A(n) (pak polozme d = n) a proces opakujeme. Koncme, kdyz d h, pak x 2= S . Na zacatku polozme d = 1 a h = jS j. Formaln zapis algoritmu:
MEMBER(x) if x = A(1) then x 2 S stop else if x < A(1) then x 2= S stop else d = 1 endif, endif if x = A(jS j) then x 2 S stop else if x > A(jS j) then x 2= S stop else h = jS j endif, endif while d + 1 < h do n := next(d; h) if x = A(n) then x 2 S stop else if x < A(n) then h := n else d := n endif, endif enddo x 2= S stop
V tomto metaalgoritmu je next(d; h) funkce, ktera nalezne hodnotu n takovou, ze d < n < h. Korektnost plyne z pozorovan, ze kdyz d + 1 = h, pak A(d) < x < A(h) implikuje, ze neexistuje i takove, ze x = A(i), a tedy x 2= S . Efektivita algoritmu zalez na fukci next. Zpracovan dotazu vyzaduje cas O(1) a pocet dotazu je pocet volan funkce next. Unarn vyhledavan: next(d; h) = d + 1, pak kazdy dotaz zvets d o 1, a tedy nejvets pocet dotazu je jS j. Algoritmus v nejhorsm prpade vyzaduje cas O(jS j) a ocekavany pocet dotazu pri rovnomernem rozlozen mnoziny S a prvku x je jS2 j (tedy ocekavany cas je O(jS j)). Poznamka: Dualn prstup je, kdyz next(d; h) = h 1, vysledky se nezmen. Pri aplikacch je nekdy vyhodne pouzt funkci next(d; h) = minfd + c; h 1g, kde c je nejaka konstanta
15
(pak krok nen 1, ale c). Jak uvidme pozdeji, jsou situace, kdy je vyhodne pouzt takoveto unarn vyhledavan. Binarn vyhledavan: next(d; h) = d d+2 h e, pak kazdy dotaz zmens rozdl h d priblizne na polovinu. Pocet dotazu je nejvyse 3 + log(jS j 2), algoritmus tedy v nejhorsm prpade vyzaduje cas O(log jS j) a ocekavany cas pri rovnomernem rozlozen mnoziny S a x 2 U je take O(log jS j). Interpolacn vyhledavan: next(d; h) = d + d A(xh)A(Ad()d) (h d)e. V nejhorsm prpade musme polozit vce nez jS2 j dotazu, a proto cas v nejhorsm prpade je O(jS j), ale pri rovnomernem rozlozen mnoziny S a x 2 U je ocekavany cas O(log log jS j). Toto je zalozeno na faktu, ze hodnota next zavis i na velikosti x. Kdyz x je velke, tak hodnota next je posunuta do vetsch hodnot, kdyz x je male, pak je posunuta do mensch hodnot. Poznamka: Kdyz rozlozen prvku nen rovnomerne, ale je zname, pak podle toho musme upravit funkci next a ocekavany cas algoritmu se nezmen. Pro nasledujc de nici funkce next bude jednoduss spoctat ocekavany pocet dotazu nez u interpolacnho vyhledavan, ale vysledek je asymptoticky stejny.
16
Zobecnene kvadraticke vyhledavan. Funkce next je zde de novana slozitejs procedurou, jejz vysledek zavis i na predchozch situacch a na vysledku dotazu. Procedura zadava dotazy v blocch. Prvn dotaz v bloku je interpolacn a procedura pritom zjist velikost kroku a zda x je pod prvnm dotazem v bloku nebo nad nm. Pak strda unarn a binarn vyhledavan. Blok konc, kdyz rozdl mezi h a d je nejvyse velikost kroku. Krok v nasledujcm bloku klesne priblizne na odmocninu velikosti kroku v tomto bloku. Procedura pouzva boolske promenne blok, typ, smer. Promenna blok je inicializovana hodnotou false a urcuje, zda se dotaz zadava v ramci bloku nebo nikoliv. Promenna typ urcuje, zda prst dotaz je unarn (kdyz typ = true) nebo binarn. Promenna smer urcuje, zda dotazy jsou pod prvnm dotazen v bloku (smer = true) nebo nad nm. Dale procedura pouzva promennou krok typu integer, ktera obsahuje velikost kroku v ramci bloku. Hodnoty techto promennych se predavaj z jednoho volan procedury do dalsho volan (tj. jsou to globaln promenne, ktere se neinicializuj volanm procedury next).
next(d; h) if blok then if typ then if smer then next(d; h) := h krok if A(next(d; h)) > x then blok := false endif else next(d; h) := d + krok if A(next(d; h)) < x then blok := false endif typ := false endif else next(d; h)p:= d d+2 h e, typ := true endif else krok := b h dc, next(d; h) := d + d A(xh)A(Ad()d) (h d)e, if A(next(d; h)) > x then smer := true else smer := false endif blok := true endif
p Po dvou dotazech klesne h d bud pod h d nebo pod h+2 d . Proto procedura v nejhorsm prpade pouzije nejvyse 5 + 2 log jS j dotazu, a tedy v nejhorsm prpade vyzaduje cas O(log jS j). Nyn spoctame ocekavany pocet dotazu behem jednoho bloku. Necht pi je pravdepodobnost, ze v ramci bloku se poloz alespon i dotazu. Pak ocekavany pocet dotazu v ramci bloku je C=
X
i1
i(pi pi+1) =
X
i1
pi:
Nyn odhadneme pi . Oznacme n + d argument prvnho dotazu (interpolacn vyhledavan) v ramci bloku a necht krok = k v ramci bloku. Oznacme X = jfi j i > d; A(i) xgj na zacatku bloku, pak X je nahodna promenna zavisla na argumentu operace a bloku. Kdyz se v bloku poloz alespon i dotazu pro i > 2, pak jX nj b i 22 kc, protoze za kazdy unarn dotaz, po jehoz polozen se nezmenil blok, mus byt v rozdlu jX nj prave k hodnot i. Tedy pi Prob(jX nj b i 2 2 kc): Nyn pouzijeme C ebysevovu nerovnost pro nahodnou promennou X . Kdyz Y je nahodna promenna s ocekavanou (stredn) hodnotou a rozptylem 2, pak C ebysevova nerovnost
17
rka, ze
j t) t2
2
Prob(jY
pro kazde t > 0:
Uvazujme okamzik, kdy jsme na zacatku nejakeho bloku. Protoze S je vybrana s rovnomernym rozdelenm, je pravdepodobnost, ze A(i) < x pro d < i < h, rovna p = A(xh)A(Ad()d) , a pak pravdepodobnost, ze X = j , je h j d pj (1 p)h d j . To znamena, ze X je nahodna velicina s binomickym rozdelenm, a tedy jej ocekavana hodnota je
=
hXd h j =0
d pj (1 p)h d j = p(h d) j
a jej rozptyl ma hodnotu hXd
h d = (j ) j pj (1 p)h d j = p(1 p)(h d): j =0 2
2
p
Kdyz si uvedomme, ze k = b h dc a n = p(h d), pak dostavame
pi ; pi+1 Prob(jX nj b i 2 2 kc) 4p(1(i p2))(2hk2 d) 4(pi(1 2)p2) (i 1 2)2 ; protoze p(1 p) 41 . Kdyz shrneme tato pozorovan, dostavame, ze
C=
X
i1
pi 2 + 2
X 1 2 = 2 + 2 3:6 = 2 + 2 = 2 + 2 2 2 6 6 i3 (i 2) i1 i
X
1
Zaver: ocekavany pocet dotazu v bloku je mens nez 4. Kdyz T (n) je ocekavany pocet dotazu pro operaci MEMBER a kdyz jS j = n, pak plat
p
T (n) C + T ( n): Protoze T (1) = 1 a T (2) 2, dostavame z rekurentnho vzorce, ze
T (n) 2 + C log log n
pro n 2:
Veta. Ocekavany cas operace MEMBER v usporadanem poli delky n pri implementaci
zobecneneho kvadratickeho vyhledavan je O(log log n) za predpokladu rovnomerneho rozlozen vstupnch dat. Nevyhoda datove struktury usporadaneho pole je nemoznost efektivn implementace aktualizacnch operac. Tento problem res binarn vyhledavac stromy. Binarn vyhledavac strom je binarn vyhledavan v usporadanem poli roztazene do roviny a vyhledavan odpovda ceste ve strome. Formaln de nice:
18
Binarn vyhledavac stromy Predpokladame, ze U je linearne usporadane univerzum a S U . Binarn vyhledavac strom T reprezentujc mnozinu S je uplny binarn strom (tj. kazdy vrchol je bud listem nebo ma dva syny, leveho a praveho) a existuje bijekce mezi mnozinou S a vnitrnmi vrcholy stromu takova, ze kdyz v je vnitrn vrchol stromu T , kteremu je prirazen prvek s 2 S , pak kazdemu vnitrnmu vrcholu u v podstromu leveho syna vrcholu v je prirazen prvek z S mens nez s a kazdemu vnitrnmu vrcholu w v podstromu praveho syna vrcholu v je prirazen prvek z S vets nez s. Struktura vnitrnho vrcholu v: ukazatel otec(v) na otce vrcholu v, ukazatel levy(v) na leveho syna vrcholu v, ukazatel pravy(v) na praveho syna vrcholu v, atribut key(v) { prvek z S prirazeny vrcholu v. Kdyz v je koren stromu, pak hodnota ukazatele otec(v) je NIL. List ma ukazatele pouze na otce. Kazdy list reprezentuje interval mezi dvema sousednmi prvky z S { presne, kdyz u je list a je levym synem vrcholu v, nalezneme vrchol na ceste z u do korene nejblze u takovy, ze je pravym synem vrcholu w, pak u reprezentuje interval (key(w); key(v)) a kdyz takovy vrchol neexistuje, pak u reprezentuje interval ( 1; key(v)) a prvek key(v) je nejmens prvek v S . Kdyz u je list a je pravym synem vrcholu v, nalezneme vrchol na ceste z u do korene nejblze u takovy, ze je levym synem vrcholu w, pak u reprezentuje interval (key(v); key(w)) a kdyz takovy vrchol neexistuje, pak u reprezentuje interval (key(v); +1) a prvek key(v) je nejvets prvek v S . Pri implementaci binarnch vyhledavacch stromu je vyhodne vynechat listy (pak bude ukazatel NIL). Pri navrhu algoritmu je vsak vyhodne pracovat s listy (je to logictejs). Proto pri navrhu algoritmu budeme predpokladat, ze stromy maj listy reprezentujc intervaly. Navrh algoritmu:
Vyhledej(x) t :=koren stromu while t nen list a key(t) 6= x do if key(t) > x then t := levy(t) else t := pravy(t) endif enddo MEMBER(x) Vyhledej(x) if t nen list then x 2 S else x 2= S endif
19
INSERT(x) Vyhledej(x) if t je list then t se zmen na vnitrn vrchol
key(t) := x, levy(t) a pravy(t) jsou nove listy, jejichz otcem je t
endif DELETE(x) Vyhledej(x) if t nen list then if levy(t) je list then odstranme vrchol levy(t), otec(pravy(t)) := otec(t) if t = levy(otec(t)) then levy(otec(t)) := pravy(t) else pravy(otec(t)) := pravy(t) endif odstranme vrchol t else u := levy(t) while pravy(u) nen list do u := pravy(u) enddo key(t) := key(u), odstranme vrchol pravy(u), otec(levy(u)) := otec(u) if u = levy(otec(u)) then levy(otec(u)) := levy(u) else pravy(otec(u)) := levy(u) endif odstranme vrchol u endif endif Hlavn problem je korektnost algoritmu Vyhledej a zde se jedna o modi kaci vyhledavan
v usporadanych poli. Nejprve dokazeme Lemma. Kazdy podstrom reprezentuje interval v mnozine S . Dukaz. Tvrzen plat pro koren. Predpokladejme, ze pro vnitrn vrchol v plat, ze jeho podstrom reprezentuje interval v mnozine S . Z vlastnost binarnch vyhledavacch stromu plyne, ze toto tvrzen plat i pro syny vrcholu v. Nyn uz snadnou indukc dostavame pozadovane lemma. Dokazeme nasledujc invariant: Kdyz vysetrujeme vrchol stromu v, jehoz podstrom reprezentuje interval < s1; s2 > v S , a kdyz s01 je predchudce s1 v S a s02 je naslednk s2 v S , pak s01 < x < s02 . Prvn dva testy zarucuj, ze plat min(S ) < x < max(S ). Kdyz tvrzen plat pro vrchol v, podstrom vrcholu v reprezentuje interval < s1 ; s2 > v S a key(v) = s, pak podstrom leveho syna vrcholu v reprezentuje interval < s1 ; s0 >, kde s0 je predchudce s v S , a podstrom praveho syna reprezentuje interval < s00 ; s2 >, kde s00 je naslednk s v S . Protoze dals vysetrovany vrchol je levy(v), prave kdyz x < s, a dals vysetrovany vrchol je pravy(v), prave kdyz s < x, dostavame, ze invariant plat i v nasledujcm kroku. Proto operace Vyhledej(x) 0bu00d nalezne vrchol v takovy, ze key(v) = x, nebo skonc v listu, ktery reprezentuje interval (t ; t ) a plat t0 < x < t00 a (t0 ; t00 ) \ S = ;. Tedy operace Vyhledej je korektn. Korektnost ostatnch operac je ted zrejma. Zpracovan jednoho vrcholu vyzaduje cas O(1) a algoritmus se pohybuje po jedne ceste z korene do nejakeho listu. Oznacme hloubka(T ) delku nejdels cesty z korene do nejakeho listu. Pak dostavame
20
Veta. Operace MEMBER, INSERT a DELETE v binarnm vyhledavacm strome T vyzaduj cas O(hloubka(T )). Tento vysledek motivuje pouzvan binarnch vyhledavacch stromu, ktere splnuj dals podmnku, ktera ma zajistit, ze hloubka(T ) = O(log jS j). Pak mluvme o vyvazenych binarnch vyhledavacch stromech. Je vsak nutne pridat k operacm INSERT a DELETE dals kroky, ktere zaruc, ze po jejich proveden strom zase splnuje pozadovane podmnky. To vede k pozadavku, aby vyvazovac operace byly rychle a provadelo se jich malo. Pri nahodne posloupnosti operac INSERT a DELETE je velka pravdepodobnost, ze dostaneme nahodny binarn vyhledavac strom. Je znamo, ze ocekavana hodnota promenne hloubka(T ) je O(log jS j). Protoze se nepouzvaj vyvazovac operace, muzeme dostat leps vysledek nez pro vyvazene binarn vyhledavac stromy. Tento problem se ted intenzivne studuje. Velka pozornost je venovana pravdepodobnostnm datovym strukturam. Hledaj se vsak i dals moznosti. Studuj se tzv. samoupravujc struktury. Zde se pracuje s datovou strukturou bez dodatecnych informac, ale operace nad datovou strukturou provad vyvazovan v zavislosti na argumentu operace. Dokazalo se, ze existuje strategie vyvazovan, ktera zajistuje dobre chovan bez ohledu na vstupn data. Dals strategie je, ze se jen zjistuje, zda datova struktura nema vyrazne spatne chovan, a pokud ho ma nebo po dlouhe rade uspesnych aktualizacnch operac, se vybuduje nova datova struktura (s optimalnm chovanm). Tret, pomerne stara, strategie je zalozena na znalosti rozdelenvstupnch dat. Zde se datova struktura predem upravuje pro toto rozdelen. Ukazuje se, ze tyto strategie maj uspech. Dals podrobnosti v letnm semestru. Nyn si ukazme operace se stromy, na nichz jsou zalozeny vyvazovac operace pro binarn vyhledavac stromy. Mejme vrchol v binarnho vyhledavacho stromu T a jeho syna u, ktery je vnitrn vrchol. Pak Rotace(v; u) je znazornena na obrazku a provad ji nasledujc algoritmus. o u
o v v
u
C
A B
A
C Obr. 1
B
21
Rotace(v; u) otec(u) := otec(v), if v = levy(otec(v) then levy(otec(v)) := u else pravy(otec(v)) := u endif otec(v) := u if u = levy(v) then otec(pravy(u) := v, levy(v) := pravy(u), pravy(u) := v else otec(levy(u)) := v, pravy(v) := levy(u), levy(u) := v endif Mejme vrchol w stromu T , jeho syna v a jeho syna u takoveho, ze u nen list a v je pravy syn vrcholu w, prave kdyz u je levy syn vrcholu v. Pak Dvojita-rotace(w; v; u) je znazornena na obrazku a provad ji nasledujc algoritmus. o o t w v v w t D A B
C
A
B
C
D
Obr. 2
Dvojita-rotace(w; v; u) otec(u) := otec(w) if w = levy(otec(w) then levy(otec(w)) := u else pravy(otec(w)) := u endif otec(v) := u, otec(w) := u if v = levy(w) then levy(w) := pravy(u), otec(pravy(u)) := w, pravy(v) := levy(u), otec(levy(u)) := v, levy(u) := v, pravy(u) := w else pravy(w) := levy(u), otec(levy(u)) := w, levy(v) := pravy(u), otec(pravy(u)) := v, levy(u) := w, pravy(u) := v endif
AVL-stromy Binarn vyhledavac strom je AVL-strom, kdyz pro kazdy vnitrn vrchol v se delka nejdels cesty z jeho leveho syna do listu a delka nejdels cesty z jeho praveho syna do listu lis nejvyse o 1. Pro vnitrn vrchol v stromu T oznacme (v) delku nejdels cesty z vrcholu v do listu.
22
Struktura vnitrnch vrcholu v AVL-stromech je rozsrena o hodnotu !: !(v) = 1 kdyz
(leveho syna vrcholu v) = (praveho syna vrcholu v) + 1; !(v) = 0 kdyz (leveho syna vrcholu v) = (praveho syna vrcholu v); !(v) = +1 kdyz (leveho syna vrcholu v) + 1 = (praveho syna vrcholu v): Vsimneme si, ze hodnota (v) pro vnitrn vrcholy v stromu T nen nikde ulozena. Hodnoty jsme schopni spoctat z hodnot !, ale nen to treba. Stac, kdyz po aktualizacnch operacch budeme umet aktualizovat hodnoty ! a umet upravit binarn vyhledavac strom tak, aby byl opet AVL-strom. Odhadneme velikost (koren T ) v zavislosti na velikosti reprezentovane mnoziny S . Kdyz T je AVL-strom a v je vnitrn vrchol T , pak podstrom T urceny vrcholem v je opet AVL-strom. Oznacme mn(i) velikost nejmens mnoziny reprezentovane AVL-stromem T s korenem t, ze (t) = i, mx(i) velikost nejvets mnoziny reprezentovane AVL-stromem T s korenem t, ze (t) = i. Z de nice AVL-stromu plynou rekurze
mn(i) = mn(i 1) + mn(i 2) + 1; mx(i) = 2mx(i 1) + 1; a mn(1) = mx(1) = 1; mn(2) = 2; mx(2) = 3: Nejprve spoctame mx. Dokazeme, ze mx(i) = 2i 1. Tento vzorec je splnen pro i = 1; 2. Dale
mx(i + 1) = 2mx(i) + 1 = 2(2i 1) + 1 = 2i+1 1: Tm je vzorec dokazan. Abychom spoctali mn, pripomeneme si de nici Fibonacciho csel. Fibonacciho cslo Fi je de novano rekurenc
F1 = F2 = 1 a Fi+2 = Fi + Fi+1 pro vsechna i 3:
p i+1 1+p5 i 1 p5 i a Fi = 2 p5 2 pro vsechna i 1.
Pak plat Fi Dokazeme, ze mn(i) = Fi+2 1. Tvrzen je zrejme splneno pro i = 1; 2. Dale mn(i + 2) = mn(i + 1) + mn(i) + 1 = Fi+3 1 + Fi+2 1 + 1 = Fi+3 + Fi+2 1 = Fi+4 1. Z toho plyne, ze kdyz AVL-strom T reprezentuje mnozinu S , pak (koren T ) = (log n) a tedy hloubka(T ) c(log jS j) pro konstantu c nezavislou na mnozine S a stromu T . Operace MEMBER(x) pro AVL-stromy je stejna jako operace MEMBER(x) pro nevyvazene binarn vyhledavac stromy. Aktualizacn operace pro AVL-stromy nejprve provedou 1+ 5 2
23
pozadovanou operaci pro nevyvazene binarn vyhledavac stromy a pak nasleduje jejich vyvazovac cast. Pri uspesne provedene operaci INSERT(x) v nevyvazenych binarnch stromech zmenme vhodny list t na vnitrn vrchol stromu reprezentujc x a pridame k t dva syny, kter budou listy. Dusledkem je, ze de nujeme !(t) = 0. Protoze se vsak zvetsila hodnota (t) (bylo (t) = 0 a ted je (t) = 1), zavolame proceduru Kontrola-INSERT(t), ktera zajist spravnou hodnotu funkce ! pro otce t. Navc, kdyz zjist, ze se zvetsila hodnota vrcholu otce t, pak zavola sama sebe na vrchol otec t. Popseme algoritmus pro KontrolaINSERT(t).
Kontrola-INSERT(t) v := otec(t) if t = levy(v) then if !(v) = 1 then !(v) := 0 else if !(v) = 0 then !(v) := 1, t := v Kontrola-INSERT(t) else if !(t) = 1 then Rotace(v; t), !(v) := 0, !(t) := 0 else w := pravy(t), Dvojita-rotace(v; t; w), if !(w) = 0 then !(t) := 0, !(v) := 0 else if !(w) = 1 then !(v) := 0, !(t) := 1 else !(v) := 1, !(t) := 0 endif endif !(w) := 0 endif endif endif else if !(v) = 1 then !(v) := 0 else if !(v) = 0 then !(v) := 1, t := v Kontrola-INSERT(t) else if !(t) = 1 then Rotace(v; t), !(v) := 0, !(t) := 0 else w := levy(t), Dvojita-rotace(v; t; w), if !(w) = 0 then !(t) := 0, !(v) := 0 else if !(w) = 1 then !(v) := 0, !(t) := 1 else !(v) := 1, !(t) := 0 endif endif !(w) := 0 endif endif endif endif Vsimneme si, ze po proveden Rotace nebo Dvojita-rotace vyvazovan v operaci INSERT konc. Tedy operace INSERT provad nejvyse jednu proceduru Rotace nebo Dvojitarotace. Korektnost vyvazovac operace je zalozena na faktu, ze kdyz se zvets hodnota (t), pak nemuze byt !(t) = 0. Tento fakt se vyuzva v if-prkazu na 5-tem a 6-tem radku a na
13-tem a 14-tem radku programu. Popseme vyvazovac operaci pro operaci DELETE. Predpokladejme, ze t je vrchol, jehoz otec se odstranil (tj. bratr t byl list) a hodnota (t) je mens nez byla hodnota (otec(t)). Proto zavolame proceduru Kontrola-DELETE(t). Tato procedura zajist spravnou hodnotu funkce ! pro otce t. Navc, kdyz zjist, ze se zmensila hodnota vrcholu otce t, pak zavola sama sebe na vrchol otec t. Popseme algoritmus pro Kontrola-DELETE(t).
Kontrola-DELETE(t) v := otec(t) if t = levy(v) then if !(v) = 1 then u := pravy(v) if !(u) = 0 then Rotace(v; u), !(v) := 1, !(u) := 1
24
else if !(u) = 1 then Rotace(v; u) !(v) := 0, !(u) = 1, t := u, Kontrola-DELETE(t) else w := levy(u), Dvojita-rotace(v; u; w) if !(w) = 0 then !(u) := 0, !(v) := 0, !(w) := 0 else if !(w) := 1 then !(u) := 0, !(v) := 1, !(w) = 0 else !(u) := 1, !(v) := 0, !(w) := 0 endif endif t := w Kontrola-Delete(t) endif endif else if !(v) = 0 then !(v) := 1 else !(v) := 0, t := v, Kontrola-DELETE(t) endif endif else if !(v) = 1 then u := levy(v) if !(u) = 0 then Rotace(v; u), !(v) := 1, !(u) := 1 else if !(u) = 1 then Rotace(v; u) !(v) := 0, !(u) = 1, t := u, Kontrola-DELETE(t) else w := pravy(u), Dvojita-rotace(v; u; w) if !(w) = 0 then !(u) := 0, !(v) := 0, !(w) := 0 else if !(w) := 1 then !(v) := 0, !(u) := 1, !(w) = 0 else !(u) := 1, !(v) := 0, !(w) := 0 endif endif t := w Kontrola-Delete(t) endif endif else if !(v) = 0 then !(v) := 1 else !(v) := 0, t := v, Kontrola-DELETE(t)
endif endif endif V operaci DELETE se muze stat, ze procedury Rotace nebo Dvojita-rotace jsou volany az log(jS j)-krat. To je vyrazny rozdl proti operaci INSERT. Proto operace DELETE je pomalejs nez operace INSERT, i kdyz asymptoticky jsou stejne rychle. Korektnost se over prmo. Veta. Implementace operac MEMBER, INSERT a DELETE pro datovou strukturu AVL-stromu vyzaduje v nejhorsm prpade cas O(log(jS j)) (kde S je reprezentovana mnozina). Operace INSERT zavola nejvyse jednu proceduru Rotace nebo Dvojita-rotace.
C erveno-cerne stromy Binarn vyhledavac strom T reprezentujc mnozinu S , jehoz vrcholy jsou obarveny cervene nebo cerne (kazdy vrchol ma prave jednu barvu) tak, ze jsou splneny podmnky: listy jsou obarveny cerne, kdyz v je vrchol obarveny cervene, pak je bud koren stromu nebo jeho otec je obarven cerne; vsechny cesty z korene do listu maj stejny pocet cernych vrcholu; se nazyva cerveno-cerny strom. Nejprve ukazeme, ze hloubka(T ) = O(log(jS j). Odtud plyne, ze cerveno-cerne stromy patr mezi vyvazene binarn vyhledavacstromy. Predpokladejme, ze T je cerveno-cerny strom, ktery ma na ceste z korene do listu prave k cernych vrcholu. Pak pro pocet vrcholu #T stromu T plat 2k 1 #T 22k 1:
25
Nejmens takovy strom ma vsechny vrcholy cerne obarvene a je to uplny pravidelny binarn strom o hloubce k 1, coz dava doln odhad. Nejvets takovy strom ma vsechny vrcholy v sudych hladinach obarveny cervene a v lichych hladinach cerne, je to uplny pravidelny binarn strom o hloubce 2k 1 a tm je dan horn odhad. Tedy k 1 + log #T . Protoze velikost S je pocet vnitrnch vrcholu, dostavame, ze #T = 2jS j + 1. Z vlastnost cervenocernych stromu plyne, ze k hloubka(T ) 2k: Tedy Tvrzen. Kdyz cerveno-cerny strom T reprezentuje mnozinu S , pak hloubka(T ) 4 + 2 log jS j. Operace MEMBER pro cerveno-cerne stromy je stejna jako pro nevyvazene binarn vyhledavac stromy. Avsak operace INSERT a DELETE maj dve casti: nejprve se provede operace INSERT nebo DELETE pro nevyvazene binarn vyhledavac stromy a pak nasleduj vyvazovac operace, ktere zajist, ze vysledny strom splnuje podmnky pro cerveno-cerne stromy (stejne schema jako pro AVL-stromy). Nejprve popseme vyvazovac operace pro INSERT. Dvojice (T; v) se nazyva 2-parcialn cerveno-cerny strom, kdyz T je binarn vyhledavac strom, kde kazdy vrchol je obarven prave jednou z dvojice barev cervena { cerna, v je vnitrn vrchol stromu T obarveny cervene a plat: listy jsou obarveny cerne, kdyz t je vrchol obarveny cervene, pak je bud koren stromu nebo t = v nebo jeho otec je obarven cerne; vsechny cesty z korene do listu maj stejny pocet cernych vrcholu. Predpokladejme, ze T je cerveno-cerny strom reprezentujc mnozinu S a provadme operaci INSERT(x) pro x 2= S . Kdyz operace INSERT(x) pro nevyvazene binarn vyhledavac stromy vytvor strom T 0 , kde vrchol v reprezentuje x, pak v obarvme cervene a syny v (jsou to listy) obarvme cerne. Dostavame, ze (T 0 ; v) je 2-parcialn cerveno-cerny strom. Na 2-parcialn cerveno-cerny strom (T 0 ; v) zavolame proceduru Vyvaz-INSERT(v). Po jejm proveden bud dostaneme cerveno-cerny strom nebo znovu zavolame proceduru Vyvaz-INSERT(v0 ) na vrchol v0 takovy, ze (T 0 ; v0 ) je 2-parcialn cerveno-cerny strom a v0 je ded v (tj. je o dve hladiny blz ke koreni nez vrchol v). Struktura vrcholu v bude rozsrena o boolskou promennou b(v), kde b(v) = 0 znamena, ze v je obarven cervene a b(v) = 1 znamena, ze v je obarven cerne. Popseme proceduru (predpokladame, ze v je obarven cervene). Pro jednoduchost, s(v) = levy, kdyz v = levy(otec(v)) a s(v) = pravy, kdyz v = pravy(otec(v)).
Vyvaz-INSERT (v). 0 if v nen koren T a b(otec(v)) = 0 then if otec(v) je koren then b(otec(v)) := 1 else w := otec(v), u := bratr(w) if b(u) = 0 then v := otec(w), b(w) := 0, b(u) := 0 b(v) := 1 Vyvaz-INSERT(v) (Viz Obr. 1) else if s(w) = s(v) then
26
Rotace(otec(w); w), b(otec(w)) := 0, b(w) := 1 (Viz Obr. 2) else Dvojita-rotace(otec(w); w; v), b(otec(w)) := 0 b(w) := 0, b(v) := 1 (Viz Obr. 3) endif endif endif endif Na obrazku b znac cernou barvu a r znac cervenou barvu. Otec vrcholu w je oznacen t.
t,b
u,r
t,r
w,r
u,b v,r
A B
w,b v,r
A
C
B
C
Obr. 1
t,b
w,b
w,r
u,b
v,r
A B
v,r
t,r u,b
C
C A
B
Obr. 2
t,b
w,r v,r
u,b D
v,b
w,r
t,r u,b
A B
A
C Obr. 3
B
C
D
27
Operace INSERT v cerveno-cernych stromech vola nejvyse 2 + log(jS j)-krat proceduru Vyvaz-INSERT a provede nejvyse jednu rotaci nebo dvojitou rotaci. Operace DELETE je resena stejnym zpusobem jako operace INSERT, ale pri operaci DELETE je porusena tret podmnka v de nici cerveno-cernych stromu a vyvazovan je
technicky narocnejs. Nejprve budeme de novat 3-parcialn cerveno-cerny strom. Tato de nice ukaze, jakym zpusobem se porus struktura cerveno-cernych stromu pri operaci DELETE. R ekneme, ze dvojice (T; v) je 3-parcialn cerveno-cerny strom, kdyz T je binarn vyhledavac strom reprezentujc mnozinu S , kazdemu vrcholu je prirazena prave jedna z dvojice barev cervena { cerna, v je vrchol ve stromu T a plat nasledujc podmnky: listy a vrchol v jsou obarveny cerne, kdyz t je vrchol obarveny cervene, pak je bud koren stromu nebo jeho otec je obarven cerne; existuje cslo k takove, ze vsechny cesty z korene do listu, ktere neobsahuj vrchol v, obsahuj prave k cernych vrcholu a vsechny cesty z korene do listu prochazejc vrcholem v obsahuj k 1 cernych vrcholu. Predpokladejme, ze jsme provedli operaci DELETE(x) a pri provaden jej prvn casti jsme odstranili vrchol u a jeho syna w, ktery je list. Na msto vrcholu u se dostal jeho druhy syn v. Pri teto akci obarvme vrchol v cerne. Pak jsou splneny prvn dve podmnky v de nici cerveno-cernych stromu a pokud vrchol u nebo vrchol v byl puvodne obarven cervene, pak je splnena i tret podmnka. Pokud vrchol u i vrchol v byly obarveny cerne, pak kazda cesta z korene do listu obsahujc vrchol v ma o jeden cerny vrchol mene nez cesta z korene do listu neobsahujc vrchol v (chyb cerny vrchol u). Kdyz T je strom vznikly provedenm operace DELETE(x) pro nevyvazene binarn vyhledavac stromy, pak (T; v) je 3-parcialn cerveno-cerny strom. Predchoz analyza dava rychly test na to, zda vznikne cerveno-cerny strom nebo 3-parcialn cerveno-cerny strom (pak v je list). Popseme proceduru Vyvaz-DELETE(v). Predpokladame, ze v tomto prpade (T; v) je 3-parcialn cerveno-cerny strom a v nen jeho koren. Vysledkem procedury bude bud cerveno-cerny strom nebo zavolan procedury VyvazDELETE(v0), kde v0 je otcem vrcholu v. Korektnost plyne z faktu, ze kdyz (T; v) je 3-parcialn cerveno-cerny strom a v je jeho koren, pak T je cerveno-cerny strom.
28
Vyvaz-DELETE(v) u := bratr(v), t := otec(v) if b(u) = 0 then Rotace(t; u) b(u) := 1, b(t) := 0, u := bratr(v) endif (Viz Obr. 4, Komentar: nyn b(u) = 1) w1 :=syn u takovy, ze s(v) = s(w1 ), w2 := bratr(w1) if b(w1 ) = b(w2) = 1 then b(u) := 0 if b(t) := 0 then b(t) := 1 else if t nen koren stromu then v := t Vyvaz-DELETE(v) endif endif (Viz Obr. 5) else if b(w1 ) = 1 then (Komentar: b(w2) = 0) Rotace(t; u), b(w2 ) := 1, b(u) := b(t), b(t) := 1 (Viz Obr. 6) else Dvojita-rotace(t; u; w1 ) b(w1 ) := b(t), b(t) := 1 (Viz Obr. 7)endif endif V nasledujcch obrazcch jsou vrcholy, ktere nemaj speci kovanou barvu (mohou byt jak cervene tak cerne). Tyto barvy budeme oznacovat a, a0 . Duvod je, ze se tato barva muze prenest do cloveho stromu, ale i na jiny vrchol. V tomto smyslu jsou tyto barvy urceny vstupnm stromem a speci kuj tyto barvy v clovem strome. V Obr. 5 se barva a v clovem strome neobjevuje. t,b v,b
u,b
u,r
t,r v,b
A B
C A
C
B
Obr. 4
t,a v,b
t,b v,b
u,b A
w1,b
w2,b B
A
w1,b
w2,b B
C Obr. 5
u,r
C
29
u,a
t,a v,b
u,b
w2,r
w1,b
A
B
t,b
w2,b
v,b
w1,b A
C
C
B
Obr. 6
t,a u,b
w1,r
w2,a' A B
w1,a
v,b D
u,b
t,b
w2,a'
C
v,b A
B
C
D
Obr. 7
Korektnost algoritmu je videt z obrazku. Vsimneme si, ze kdyz u je obarven cervene, pak po proveden Rotace(t; u) bude (T; v) opet 3-parcialn cerveno-cerny strom a vrchol t bude obarven cervene. Pak z Obr. 5 je videt, ze dostaneme cerveno-cerny strom. Tedy muzeme shrnout: Veta. Implementace operac MEMBER, INSERT a DELETE pro cerveno-cerne stromy vyzaduje v nejhorsm prpade cas O(log(jS j), kde S je reprezentovana mnozina. Operace INSERT zavola nejvyse jednou bud Rotace nebo Dvojita-rotace a operace DELETE zavola nejvyse dvakrat Rotace nebo Rotace a Dvojita-rotace. Vznika otazka, proc se tolik pozornosti venuje proceduram Rotace a Dvojita-rotace. Sice vyzaduj cas O(1), ale jsou nejslozitejs akce vyzadujc nejvce casu. V mnoha aplikacch (pouzvaj se hlavne ve vypocetn geometrii), tvar stromu spolu s parametry nesou jeste dals zakodovane informace. Pri zmene tvaru stromu je treba je prepoctat. Rotace a Dvojita-rotace men tvar stromu, kdezto posun smerem ke koreni pouze men obarven. V tomto prpade pak Rotace nebo Dvojita-rotace vyzaduje cas O(jS j) (obvykle je treba prohlednout cely strom) a nikoliv O(1).
Vahove vyvazene stromy
30
V osmdesatych letech se ve vypocetn geometrii hodne pouzvaly BB( )-stromy, pproto se o nich alespon orientacne zmnme. Mejme realne cslo takove, ze 41 < 22 . Pro strom T oznacme (T ) pocet listu ve stromu T . Binarn vyhledavac strom T reprezentujc mnozinu S se nazyva BB( )-strom, kdyz pro kazdy vnitrn vrchol v plat:
((TTl)) = 1 ((TTr )) 1 v v kde Tv je podstrom T urceny vrcholem v, Tl je podstrom T urceny levym synem vrcholu v, Tr je podstrom T urceny pravym synem vrcholu v. Plat Tvrzen. Kdyz T je BB( )-strom reprezentujc n-prvkovou mnozinu, pak 1: hloubka(T ) 1 + log(n + 1) 1 log 1 Dusledek je, ze BB( )-stromy patr do skupiny vyvazenych binarnch vyhledavacch stromu. Vyvazovan se provad opet pomoc Rotace a Dvojita-rotace a popisuje ho nasledujc technicke tvrzen. Tvrzen. Pro kazde existuje konstanta d takova, ze < d < 1 a ze pro kazdy binarn vyhledavac strom T s korenem t splnujc podmnky: (1) kdyz Tl a Tr jsou podstromy T urcene levym a pravym synem t, pak Tl a Tr jsou BB( )-stromy; )+1 1 , (2) ((TTl)) < , ale (T(T)l)1 1 nebo ((TTl)+1 plat: kdyz d, pak provedeme Rotace(t; pravy(t)), kdyz > d paka provedeme Dvojitarotace(t; levy(pravy(t))), v obou prpadech dostaneme BB( )-strom, kde = ((TTr0)) a T 0 je urcen levym synem praveho syna korene t. Toto tvrzen a jeho symetricke verze jednoznacne ukazuj, jak vyvazovat BB( )-stromy pri aktualizacnch operacch. Pak dostavame: Veta. Implementace operac MEMBER, INSERT a DELETE v BB( )-stromech vyzaduje v nejhorsm prpade cas O(log(jS j)), kde S je reprezentovana mnozina. Obliba BB( )-stromu byla zaprcinena nasledujc vetou, ktera je analogi vety o vyvazovacch operacch pro (a; b)-stromy. p Veta. Kdyz je realne cslo takove, ze 14 < < 1 22 , pak existuje konstanta c > 0 zavisla jen na takova, ze kazda posloupnost operac INSERT a DELETE o delce m aplikovana na prazdny BB( )-strom vola nejvyse cm procedur Rotace a Dvojita-rotace.
31
Historicky prehled: (a; b)-stromy zavedli Bayer a McGreght (1972), vety o poctu vyvazovacch operac pro (a; b)-stromy dokazali Huddleston a Mehlhorn (1982) , A-sort analyzovali Guibas, McGreight, Plass a Roberts (1977). Analyza interpolacnho vyhledavan pochaz od Perla, Itai a Avniho (1978), kvadraticke vyhledavan analyzovali Perl a Reingold (1977). Adelson-Velskij a Landis (1962) de novali AVL-stromy , cerveno-cerne stromy de novali Guibas a Sedgewick (1978), BB( )-stromy zavedli Nievergeltem a Reingoldem (1973), vety o jejich vyvazovan dokazali Blum a Mehlhorn (1980). Priorita AVL-stromu se odraz v jejim hojnem pouzvan, i kdyz cerveno-cerne stromy jsou efektivnejs.
