ADS úlohy D - Min-strom

Strom mohu nakreslit tak, že jeho "projekcí" na jeden řádek bude vstupní posloupnost. Proto mně napadl tento postup (jako online algoritmus):

---

Vstupní řadu budu interpretovat jako neorientovaný graf; hrana vede vždy mezi předchozím a následujícím prvkem.

Každému prvku také přiřadím vlastnost "hladina".

Je-li předchozí prvek větší, pak nově přidaný prvek bude mít hladinu o 1 menší, v opačném případě o 1 větší.

Tímto postupem by vznikl jakýsi cik-cak graf, který strukturu stromu samozřejmě nepřipomíná. Proto je potřeba takovou konfiguraci upravit - a nejlépe při přidávání nového prvku.

---

(Poslední prvek je ten, který jsem do stromu přidal naposledy. Nový prvek je ten, který jsem si načetl a teď hledám, kam ho zařadit.)

Pokud je nový prvek větší než poslední, pak se nic neděje; poslední prvek nemohl mít žádného pravého syna, tak se prvek normálně přidá.

Pokud je však nový prvek menší než poslední, vzniknou mi dva kořeny (nebyl-li poslední prvek kořenem) a tak poslední prvek bude mít dva otce.

To se však snadno dá napravit: vezmu si otce posledního prvku a k němu připojím nový prvek. Zároveň tak (graficky) se posune poslední prvek o hladinu níže.

Zde však může opět dojít k situaci, že otec posledního prvku je také větší, než nově přidaný prvek. V takovém případě opět se posunu o hladinu výše.

V nejhorším případě tedy budu muset porovnávat s nejpravějšími prvky v každé hladině. Začnu-li například posloupností

$1...8$ a chci-li vložit

$0$, budu muset porovnat se všemi prvky (jelikož strom je skutečně pouze vpravo-dolů směřující cesta). Naštěstí po skutečném vložení nuly budu muset další prvek porovnávat pouze s nulou. Naopak, vložil-li bych

$4,5$(4 porovnání), vznikne "čistě pravá cesta"

$1-2-3-4-4,5$, takže pro další případ budu muset vykonat nejhůře 5 porovnání.

Složitost pro tak celkově měla vyjít

$O(n)$.

---

Algoritmus:

1. Přidej první vrchol do grafu a označ jej jako poslední (x).
2. Pro každý následující vrchol y:
   1. Porovnej s x.
   2. Je-li y>x:
      1. Označ x jako otce y.
   3. Je-li y<x:
      1. Dokud není y>x nebo x není kořen:
         1. x := otec x
      2. Je-li x kořen:
         1. Označ y jako otce x
         2. Označ y jako kořen
         3. Skonči
      3. Je-li y>x:
         1. Označ pravého syna x jako levého syna y
         2. Označ y jako pravého syna x.
3. Výstup: kořen minimového grafu.

Strom z řady

$7,5,2,4,6,1,8,3$

Správnost:

Kořen je globálním minimem: Jediný způsob, jak se může kořen změnit, je, že nový prvek je menší než kořen. To nastane vždy, když nový prvek vystoupá až do nejvyšší hladiny, tzn. je menší, než všichni následovnící kořene (a i kořen samotný).

Levý podstrom obsahuje starší prvky, pravý podstrom obsahuje novější prvky: První vrchol nemá levého syna a poslední vrchol nemá pravého syna. Prvky do posloupnosti přidávám v takovém pořadí jako v zadání, čili nový prvek se nikdy nemůže stát levým synem.

Složitost:

Přepojování synů je konstantní operace, potřebuji max. dvě.
Co se týče počtu porovnávání: pokud obsahuje "pravá cesta" (tzn. prvky, které musím potenciálně porovnávat)

$k$ prvků, pak

$2$ porovnání délku této cesty nezmění (tzn. další prvek bude muset podstoupit nejhůře

$k$ porovnání.) Vyšší či nižší počet porovnání zkrátí/prodlouží "pravou cestu" o tento rozdíl. Tím pádem průměrně budu potřebovat

$2$ porovnání.