Komprimovaná trie

Komprimovaná trie^[1] 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 Donald R. Morrison.^[2]

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

Odkazy

Reference

V tomto článku byly použity překlady textů z článků Patricia-Trie na německé Wikipedii a Radix tree na anglické Wikipedii.

↑ MAREŠ, Martin; VALLA, Tomáš. Průvodce labyrintem algoritmů. Praha: CZ.NIC, 2017. Dostupné online. ISBN 978-80-88168-19-5. S. 93.
↑ MORRISON, Donald R. PATRICIA—Practical Algorithm To Retrieve Information Coded in Alphanumeric. Journal of the ACM [online]. Říjen 1968. Dostupné online. (anglicky)

Externí odkazy

Obrázky, zvuky či videa k tématu komprimovaná trie na Wikimedia Commons

[1] MAREŠ, Martin; VALLA, Tomáš. Průvodce labyrintem algoritmů. Praha: CZ.NIC, 2017. Dostupné online. ISBN 978-80-88168-19-5. S. 93.

[2] MORRISON, Donald R. PATRICIA—Practical Algorithm To Retrieve Information Coded in Alphanumeric. Journal of the ACM [online]. Říjen 1968. Dostupné online. (anglicky)

[1]

[2]

Stromové datové struktury

Vyhledávací stromy (dynamické množiny/ asociativní pole)	2–3 • 2–3–4 • AA • (a,b) • AVL • B • B+ • B* • B^x • (Optimální) Binární vyhledávací • Dancing • HTree • Intervalový • Stromy s pořadím (Order statistic) • (Doleva převážený) Červeno-černý • Scapegoat • Splay • T • Treap • UB • Váhově vyvážený (tj. BB[α])

Haldy	Binární • Binomiální • Brodal • Fibonacciho • Leftist • Pairing • Skew • Van Emde Boasův strom • Slabá

Trie	Ctrie • C-trie • Hašovací • Komprimovaná trie (tj. Patricia) • Sufixový (tj. PAT) • Ternální hledání • X-fast • Y-fast

Prostorové indexační stromy	Ball • BK • BSP • Kartézský • Hilbertův R • k-d (implicitní k-d) • M • Metrický • MVP • Oktálový (Octree) • PH • Prioritní R • Čtyřstrom (Quadtree) • R • R+ • R* • Segmentový • VP (vantage-point) • X

Jiné stromy	Strom pokrytí • Obousměrně provázaný (Doubly chained tree) • Exponenciální • Fenwickův • (Binární) Strom s prstem • Fraktálový indexový • Fúzní (Fusion tree) • Hašovací kalendář • iDistance • K-ární • Knuthův transformovaný (Left-child right-sibling binary tree) • Link/cut • Log-strukturovaný spojovací • Hašový Merkleův (TTH) • PQ • Rozsahový (Range) • SPQR • Top (Horní strom)

Kategorie:Stromy (dat. strukt.)