goldman.collection.ordered.digitized
Class TernarySearchTrie<E>
java.lang.Object
goldman.collection.AbstractCollection<E>
goldman.collection.ordered.digitized.Trie<E>
goldman.collection.ordered.digitized.CompactTrie<E>
goldman.collection.ordered.digitized.TernarySearchTrie<E>
- All Implemented Interfaces:
- Collection<E>, DigitizedOrderedCollection<E>, OrderedCollection<E>, Tracked<E>, Iterable<E>
public class TernarySearchTrie<E>
- extends CompactTrie<E>
- implements DigitizedOrderedCollection<E>, Tracked<E>
The ternary search trie (often referred to as
a TST) is a hybrid between a trie and
a binary search tree that
combines the time efficiency of a trie with the space efficiency of
a binary search tree.
In a ternary search trie, each node has three children. The branch to take
during search is determined by both a branch position and the digit in that position
for a distinguished descendant leaf node. Elements with a smaller
digit use the left branch, elements with a equal digit use the middle branch,
and elements with a larger digit use the right branch.
Constructor Summary |
TernarySearchTrie(Digitizer<? super E> digitizer)
Creates an empty ternary search trie that uses
the given digitizer. |
Methods inherited from class goldman.collection.ordered.digitized.Trie |
add, addTracked, completions, contains, get, getEquivalentElement, getLocator, insert, iterator, iteratorAtEnd, longestCommonPrefix, max, min, moveToPred, predecessor, remove, removeImpl, successor |
Methods inherited from class goldman.collection.AbstractCollection |
accept, addAll, checkRep, clear, compare, ensureCapacity, equivalent, getCapacity, getComparator, getElementAtRank, getElementAtRank, getSize, isEmpty, retainAll, toArray, toArray, toString, traverseForVisitor, trimToSize, writeElements |
Methods inherited from interface goldman.collection.Collection |
accept, add, addAll, checkRep, clear, contains, ensureCapacity, getCapacity, getComparator, getLocator, getSize, isEmpty, iterator, remove, retainAll, toArray, toArray, toString, trimToSize |
TernarySearchTrie
public TernarySearchTrie(Digitizer<? super E> digitizer)
- Creates an empty ternary search trie that uses
the given digitizer.
- Parameters:
digitizer
- the digitizer to extract digits
from elements
createSearchData
protected Trie.SearchData createSearchData()
- Overrides:
createSearchData
in class Trie<E>
- Returns:
- a newly created and
initialized ternary search trie search data instance
newLeafNode
protected TrieLeafNode<E> newLeafNode(E element,
int level)
- Parameters:
element
- the data element
- Returns:
- a newly created ternary search trie leaf node holding the given element.
newInternalNode
protected TrieNode<E> newInternalNode(Object o)
- Overrides:
newInternalNode
in class CompactTrie<E>
- Parameters:
o
- an object to initialize the data value for the new node
- Returns:
- a new ternary search trie node holding
o
moveToLowestCommonAncestor
protected void moveToLowestCommonAncestor(E prefix,
Trie.SearchData sd,
Trie.FindResult found)
- This method has the side affect of
moving
sd
so that it is at the lowest common ancestor
for which the associated data is an extension of prefix
.
- Overrides:
moveToLowestCommonAncestor
in class Trie<E>
- Parameters:
prefix
- a digitized elementsd
- a SearchData
instance that has been set by a search for prefix
found
- the FindResult value returned by the search that was used to
set sd