Created
July 26, 2018 18:24
Star
You must be signed in to star a gist
Ternary Search Trie
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class TST<Value> | |
{ | |
private int n; // size | |
private Node<Value> root; // root of TST | |
private static class Node<Value> | |
{ | |
private char c; // character | |
private Node<Value> left, mid, right; // left, middle, and right subtries | |
private Value val; // value associated with string | |
} | |
public TST() { } | |
public int size() { return n; } | |
public boolean contains( String key ) | |
{ | |
if ( key == null ) | |
{ | |
throw new IllegalArgumentException( "argument to contains() is null" ); | |
} | |
return get( key ) != null; | |
} | |
public Value get( String key ) | |
{ | |
if ( key == null ) | |
{ | |
throw new IllegalArgumentException( "calls get() with null argument" ); | |
} | |
if ( key.length() == 0 ) throw new IllegalArgumentException( "key must have length >= 1" ); | |
Node<Value> x = get( root, key, 0 ); | |
if ( x == null ) return null; | |
return x.val; | |
} | |
private Node<Value> get( Node<Value> x, String key, int d ) | |
{ | |
if ( x == null ) return null; | |
if ( key.length() == 0 ) throw new IllegalArgumentException( "key must have length >= 1" ); | |
char c = key.charAt( d ); | |
if ( c < x.c ) return get( x.left, key, d ); | |
else if ( c > x.c ) return get( x.right, key, d ); | |
else if ( d < key.length() - 1 ) return get( x.mid, key, d + 1 ); | |
else return x; | |
} | |
public void put( String key, Value val ) | |
{ | |
if ( key == null ) | |
{ | |
throw new IllegalArgumentException( "calls put() with null key" ); | |
} | |
if ( !contains( key ) ) n++; | |
root = put( root, key, val, 0 ); | |
} | |
private Node<Value> put( Node<Value> x, String key, Value val, int d ) | |
{ | |
char c = key.charAt( d ); | |
if ( x == null ) | |
{ | |
x = new Node<Value>(); | |
x.c = c; | |
} | |
if ( c < x.c ) x.left = put( x.left, key, val, d ); | |
else if ( c > x.c ) x.right = put( x.right, key, val, d ); | |
else if ( d < key.length() - 1 ) x.mid = put( x.mid, key, val, d + 1 ); | |
else x.val = val; | |
return x; | |
} | |
public String longestPrefixOf( String query ) | |
{ | |
if ( query == null ) | |
{ | |
throw new IllegalArgumentException( "calls longestPrefixOf() with null argument" ); | |
} | |
if ( query.length() == 0 ) return null; | |
int length = 0; | |
Node<Value> x = root; | |
int i = 0; | |
while ( x != null && i < query.length() ) | |
{ | |
char c = query.charAt( i ); | |
if ( c < x.c ) x = x.left; | |
else if ( c > x.c ) x = x.right; | |
else | |
{ | |
i++; | |
if ( x.val != null ) length = i; | |
x = x.mid; | |
} | |
} | |
return query.substring( 0, length ); | |
} | |
public Iterable<String> keys() | |
{ | |
Queue<String> queue = new Queue<String>(); | |
collect( root, new StringBuilder(), queue ); | |
return queue; | |
} | |
public Iterable<String> keysWithPrefix( String prefix ) | |
{ | |
if ( prefix == null ) | |
{ | |
throw new IllegalArgumentException( "calls keysWithPrefix() with null argument" ); | |
} | |
Queue<String> queue = new Queue<String>(); | |
Node<Value> x = get( root, prefix, 0 ); | |
if ( x == null ) return queue; | |
if ( x.val != null ) queue.enqueue( prefix ); | |
collect( x.mid, new StringBuilder( prefix ), queue ); | |
return queue; | |
} | |
private void collect( Node<Value> x, StringBuilder prefix, Queue<String> queue ) | |
{ | |
if ( x == null ) return; | |
collect( x.left, prefix, queue ); | |
if ( x.val != null ) queue.enqueue( prefix.toString() + x.c ); | |
collect( x.mid, prefix.append( x.c ), queue ); | |
prefix.deleteCharAt( prefix.length() - 1 ); | |
collect( x.right, prefix, queue ); | |
} | |
public Iterable<String> keysThatMatch( String pattern ) | |
{ | |
Queue<String> queue = new Queue<String>(); | |
collect( root, new StringBuilder(), 0, pattern, queue ); | |
return queue; | |
} | |
private void collect( Node<Value> x, StringBuilder prefix, int i, String pattern, Queue<String> queue ) | |
{ | |
if ( x == null) return; | |
char c = pattern.charAt( i ); | |
if ( c == '.' || c < x.c ) collect( x.left, prefix, i, pattern, queue ); | |
if ( c == '.' || c == x.c ) | |
{ | |
if ( i == pattern.length() - 1 && x.val != null ) queue.enqueue( prefix.toString() + x.c ); | |
if ( i < pattern.length() - 1) | |
{ | |
collect(x.mid, prefix.append( x.c ), i + 1, pattern, queue ); | |
prefix.deleteCharAt( prefix.length() - 1 ); | |
} | |
} | |
if ( c == '.' || c > x.c ) collect( x.right, prefix, i, pattern, queue ); | |
} | |
public static void main( String[] args ) | |
{ | |
TST<Integer> st = new TST<Integer>(); | |
for ( int i = 0; !StdIn.isEmpty(); i++ ) | |
{ | |
String key = StdIn.readString(); | |
st.put( key, i ); | |
} | |
if ( st.size() < 100 ) | |
{ | |
StdOut.println( "keys(\"\"):" ); | |
for ( String key : st.keys() ) | |
{ | |
StdOut.println( key + " " + st.get( key ) ); | |
} | |
StdOut.println(); | |
} | |
StdOut.println( "longestPrefixOf(\"shellsort\"):" ); | |
StdOut.println( st.longestPrefixOf("shellsort" ) ); | |
StdOut.println(); | |
StdOut.println( "longestPrefixOf(\"shell\"):" ); | |
StdOut.println( st.longestPrefixOf( "shell" ) ); | |
StdOut.println(); | |
StdOut.println( "keysWithPrefix(\"shor\"):" ); | |
for (String s : st.keysWithPrefix( "shor" ) ) | |
StdOut.println( s ); | |
StdOut.println(); | |
StdOut.println( "keysThatMatch(\".he.l.\"):" ); | |
for ( String s : st.keysThatMatch( ".he.l." ) ) | |
StdOut.println( s ); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment