Class TernaryIntervalSearchTree

All Implemented Interfaces:
PrefixMap<MutableString>, StringMap<MutableString>, Function<CharSequence,Long>, Object2LongFunction<CharSequence>, Size64, Serializable, Function<CharSequence,Long>, ToLongFunction<CharSequence>

public class TernaryIntervalSearchTree extends AbstractPrefixMap implements Serializable
Ternary interval search trees.

Ternary search trees are a data structure used to store words over an alphabet; they are a useful alternatives to tries when the alphabet is large.

Ternary interval search trees have the additional properties of being able to locate quickly intervals of words extending a given prefix (where “quickly” means that no more successful character comparisons than the prefix length are performed). They do so by storing at each node the number of words covered by that node.

This implementation exposes a number of interfaces: in particular, the set of words is seen as a lexicographically ordered ObjectList.

This class is mutable, but for the time it implements only add(CharSequence). Words cannot be removed.

Since:
2.0
See Also: