ADS úlohy E - AddMin

Datovou strukturou, která by data mohla uchovávat, může být úplný binární strom, kde všechny prvky budou na spodní hladině. Pro zjednodušení budu předpokládat, že počet těchto prvků je mocnina dvojky (strom pak mohu doplnit listy s hodnotami

$+\mathrm{\infty }$, velikost stromu se nejvýše zdvojnásobí).

Zároveň mám také možnost přímého přístupu k listům (stále lineární prostor), a při pohybu ve stromu směrem nahoru vím, zdali se posouvám doleva nebo doprava. Nakonec také potřebuju možnost procházet jednotlivé hladiny postupně, zleva doprava (čili přeskakovat). K implementaci tak bude dobré použít pole, nikoli pointery.

Operace jsou založeny na tom, že všechny vnitřní vrcholy uchovávají minimum ze svých synů, a také interval

$[l,r]$, ve kterém se nacházejí listy.

Algoritmus:

Přičtení pak vypadá následovně:

1. Vezmi levý/pravý prvek z intervalu a přičti k němu
   $\delta$.
2. Označ otce jako "první/poslední prvek změny".
3. Přičti
   $\delta$ ke všem ostatním prvkům z intervalu.
4. Pro všechny hladiny (s výjimkou poslední):
   1. Pro všechny prvky na dané hladině, od prvního označeného do posledního:
      1. Změň hodnotu na
         $min$(levý syn, pravý syn)
   2. Označ otce prvního vrcholu a posledního vrcholu.

Hledání minima (v intervalu a,b) vypadá pak následovně (závorky odpovídají tečkám v prog. jazycích):

1. Označ
   $p=a$ (p značí poslední prvek na cestě) a
   $k$ jako vrchol na pozici
   $a$.
2. Minimum
   $M=+\mathrm{\infty }$
3. Dokud
   $p\ne b$:
   1. Pokud
      $k(otec(r))>b$ nebo
      $k(otec(l))\ne p$:
      1. $M=min(M,k(hodnota))$ (toto ještě zopakuj na konci algoritmu)
      2. $p=k(r)+1$
      3. $k$ = vrchol na pozici
         $p$
   2. Jinak
      $k=k(otec)$

Původní záměr byl začít u kořene a dělit vyhledávací cesty tak, abych pokryl celý interval co nejmenším množství kořenů, ale myslím, že i tento postup odspoda by měl fungovat.

Slovní popis algoritmu: Mám-li nakreslený strom, pak jdu nahoru doprava, čímž postupně pokrývám celý interval. Pokud již interval přesáhnu nebo pokračuju nahoru doleva (tzn. interval přesáhnu směrem doleva), skočím na první nepokrytý prvek.

Jelikož předchozí vrchol již nebudu potřebovat, můžu jej rovnou porovnat s momentálním minimem a zahodit.

Složitost:

Jenom bych chtěl podotknout, že pole umí obě operace v lineárním čase (což je pro první operaci optimální) a také nespotřebovává žádnou paměť navíc.

Přičtení:

V nejhorším případě na každém vrcholu provedu dvě porovnání, takže mám stále lineární čas -

$O(n)$.

Hledání minima:

V nejlepším případě mám vyhledat minimum z intervalu jako

$[0,7],[0,15]\dots$, což zabírá logaritmický čas. Nyní mohu takový strom rozdělit na dva (vynecháním posledního vrcholu, jehož hodnotu jsem četl), což znamená, že musím číst 2 vrcholy v hladině o 1 nižší.

Nyní tímto způsobem rozdělím celý strom tak, abych osamostatnil poslední vrchol na okraji a tento vrchol odeberu - pro příklad uvedu strom, kde má poslední hladina 16 listů: algoritmus vyhledávání v intervalu

$[0-15]$ bude porovnávat vrcholy v této hloubce(odspoda):

$4(0-7),3(8-11),2(12-13),1(14)$.
Podobným způsobem mohu vyhledávání deformovat i z levé strany; v intervalu

$[1-14]$ budu porovnávat vrcholy v hloubkách odspoda

$1,2,3,3,2,1$.

Modře označené vrcholy jsou ty, které porovnávám s minimem.

Odebíráním dalších vrcholů se situace nemůže již zkomplikovat, neboť je odebírám zkraje (a tak by mi nejprve zmizel osamostatněný vrchol, poté by z dvojice ubyl jeden vrchol…). Kolik tak bude celková složitost?

Budu brát, že posun nahoru má stejnou složitost, jako porovnání jednotlivých vrcholů; tedy pro vyhledávání

$[1-14]$ na

$16$ prvcích se jedná o

$6+(2\ast (1+2+3))=18$.

Jelikož

$\log 16=4$, dala by se složitost vyjádřit následovně:

$2\ast \log n+(\log (n)-1)(\log n)\in O(\log (n{)}^2)$

Oproti poli je složitost přičtení (jen) o násobek složitější a složitost čtení je řádově rychlejší.