Komprimovaná trie

Příklad komprimované trie Komprimovaná trie je datová struktura, pojem z oboru matematické informatiky. Jedná se o strukturou podobou triím, ale zatímco u trie je na každé hraně jen jediný znak, u komprimované trie jich tam může být víc, pokud jsou společné všem potomkům daného vrcholu. Oproti běžným triím tak použití komprimované trie může šetřit počítačovou paměť.

Tento typ struktury má několik alternativních názvů, mj. Patricia-trie, přičemž s názvem PATRICIA coby zkratkou svého stejnojmenného článku je zavedl v roce 1968 +more_Morrison'>Donald R. Morrison.

Komprimované trie se používají mj. pro realizaci asociativních polí.

Odkazy

Reference

Externí odkazy

Kategorie:Stromy (datové struktury)