A Practical Guide to Data Structures and Algorithms using Java

DigitizedOrderedCollection

Chapter 44

Patricia Trie Data Structure

package collection.ordered.digitized

AbstractCollection<E> implements Collection<E>

↑

Trie<E> implements DigitizedOrderedCollection<E>,Tracked<E>

↑

CompactTrie<E> implements DigitizedOrderedCollection<E>,Tracked<E>

↑

CompressedTrie<E> implements DigitizedOrderedCollection<E>,Tracked<E>

↑

PatriciaTrie<E> implements DigitizedOrderedCollection<E>,Tracked<E>

Uses: Java array and references

Used By: TaggedPatriciaTrie (Section 49.10.5)

Strengths: Reduces the space requirement of the compressed trie by letting each internal node

also serve as a leaf node, hence removing the need to allocate leaf