Abstrakt
Existuje velké množství algoritmů, které pracují se stromovými grafy. Různé algoritmy mohou pro své potřeby reprezentovat stejný strom prostřednictvím odlišných datových struktur.
Chceme-li provozovat více takových algoritmů současně nad jedním lesem, může se stát, že každý bude potřebovat svou vlastní reprezentaci lesa. Pokud se les navíc průběžně mění přidáváním a odebíráním hran, musí se tyto změny přenášet do datových struktur všech provozovaných algoritmů.
Takový postup však není efektivní. Bylo navrženo několik datových struktur, nad kterými lze současně provozovat různé stromové algoritmy.
Každá z těchto struktur vyniká některými vlastnostmi, ale má také své slabiny. Rozumný kompromis představují Top-stromy, které navrhl Alstrup a kol.
V této práci se budeme zabývat implementací Top-stromů. Tu stručně popsali Tarjan a Werneck.
Na tomto základu vybudujeme funkční implementaci datové struktury Top-stromy.