Nejlevější maximální podstrom s vyhledávací vlastností
Zadání
Nejprve zavedeme nezbytné pojmy.
Ve kořenovém stromu T je potomkem uzlu v každý uzel u různý od v, pro který platí, že v leží na cestě z kořene T do u. Uzel u je bezprostředním potomkem uzlu v pokud délka cesty z u do v je rovna 1. Pojmem strom budeme nadále v této úloze označovat vždy kořenový binární strom, tj. strom, v němž každý uzel má nejvýše jednoho bezprostředního levého a nejvýše jednoho pravého bezprostředního potomka.
Podstrom stromu T je množina uzlů A stromu T a množina H všech hran mezi uzly A s tou vlastností, že v T existuje uzel v, jehož množina všech potomků sjednocena s v je rovna množině A. Pravý, resp. levý podstrom uzlu u ve stromu T je takový podstrom S stromu T, že kořen S je levým, resp. pravým bezprostředním potomkem uzlu u.
Velikost podstromu je definována jako počet uzlů tohoto podstromu. V alespoň dvouprvkové možině podstromů je maximální každý podstrom, pro nějž platí, že jeho velikost je větší nebo rovna velikosti každého jiného podstromu v této množině. Strom v jednoprvkové množině stromů je vždy maximální.
Řekneme, že uzel u leží vlevo od uzlu v, pokud buď u leží levém podstromu v nebo v leží v pravém podstromu u nebo existuje uzel w, takový, že u leží v jeho levém podstromu a v leží v jeho pravém podstromu. Řekneme, že podstrom L leží vlevo od podstromu R, pokud kořen L leží vlevo od kořene R.
V této úloze předpokládáme, že každý uzel stromu obsahuje jeden nezáporný celočíselný klíč a že všechny klíče ve stromu jsou navzájem různé.
Označme levý podstrom uzlu v symbolem L(v) a pravý podstrom uzlu v symbolem R(v). Řekneme, že podstrom S stromu T má vyhledávací vlastnost, pokud pro každý uzel v podstromu S platí zároveň:
(1) když je L(v) neprázdný, pak hodnota klíče uzlu v je větší než hodnota všech klíčů v L(v) a
(2) když je R(v) neprázdný, pak hodnota klíče uzlu v je menší než hodnota všech klíčů v R(v).
Pro každé dva maximální podstromy s vyhledávací vlastností A, B ve stromu T platí, že buď leží A vlevo od B nebo B leží vlevo od A. Proto také (díky konečné velikosti T, tranzitivitě, antisymetrii a antireflrexivitě relace „leží vlevo od“) v množině všech maximálních podstromů s vyhledávací vlastností existuje jediný podstrom L takový, který leží vlevo ode všech ostatních maximálních podstromů s vyhledávací vlastností. Tento podstrom L nazveme nejlevějším maximálním podstromem s vyhledávací vlastností v daném stromu T. Prvek jednoprvkové množiny maximálních podstromů s vyhledávací vlastností je vždy nejlevější.
Úlohou je v daném stromu nalézt nejlevější maximální podstrom s vyhledávací vlastností.
Řádkový zápis stromu definujeme rekurzivně:
1. Řádkový zápis prázdného stromu T je prázdný řetězec.
2. Řádkový zápis neprázdného stromu T má tvar (<LST><K><RST>),
kde <LST> je řádkový zápis levého podstromu kořene T, <K> je zápis hodnoty klíče v kořenu T, <RST> je řádkový zápis pravého podstromu kořene T.
Ukázka
Strom T je znázorněn na schématu, uzly nejlevějšího maximálního podstromu s vyhledávací vlastností jsou zvýrazněny symbolem #.
Podstrom s kořenem s klíčem 10 je rovněž maximální vyhledávací v T.
___[20]___________________
_________[30] _______________[13]____________
____[111]____ #40#_______ _____[10]
[110] [112] ___#50#___ __[5]__
#45# #55# [3] [7]Řádkový zápis stromu T má tvar
((110)111(11230)2040((45)50(55)13(3)5(710))).
Vstup
Strom na vstupu je vždy neprázdný a může být zadán dvěma způsoby. Při prvním způsobu vstup obsahuje jediný řádek s řádkovým zápisem stromu bez úvodních nebo koncových mezer. Při druhém způsobu vstup obsahuje dva řádky. První řádek obsahuje seznam klíčů stromu vypsaných v pořadí inorder a druhý řádek obsahuje seznam klíčů stromu vypsaných v pořadí preorder. Každé dva sousední klíče v každém seznamu jsou odděleny jedinou mezerou, žádné další mezery vstup neobsahuje. Hloubka stromu na vstupu je nejvýše 30.
Výstup
Na výstupu je jediný řádek s pěti celými čísly charakterizujícími nalezený podstrom. Čísla jsou oddělena jednou mezerou a řádek neobsahuje úvodní mezery.
V zadaném stromu T označme V nejlevější maximální podstrom s vyhledávací vlastností. Čísla na výstupu pak jsou následující v uvedeném pořadí:
1. Hodnota klíče v kořeni V,
2. počet uzlů V,
3. hloubka kořene V (hloubka kořene T je 0),
4. výšku stromu V, to jest počet hran na cestě mezi kořenem V a nejhlouběji položeným listem V,
5. levé pořadí kořene V, to jest počet uzlů stromu T které leží vlevo od kořene V.
Vstupní data jsou zapsána v souboru stdin (na konzolovém vstupu), výstup se zapíše do souboru stdout (na konzolový výstup).