TST (Algorithms 4/e)

Object
- edu.princeton.cs.algs4.TST<Value>

```
public class TST<Value>
extends Object
```
The TST class represents a symbol table of key-value pairs, with string keys and generic values. It supports the usual put, get, contains, delete, size, and is-empty methods. It also provides character-based methods for finding the string in the symbol table that is the longest prefix of a given prefix, finding all strings in the symbol table that start with a given prefix, and finding all strings in the symbol table that match a given pattern. A symbol table implements the associative array abstraction: when associating a value with a key that is already in the symbol table, the convention is to replace the old value with the new value. Unlike Map, this class uses the convention that values cannot be null—setting the value associated with a key to null is equivalent to deleting the key from the symbol table.
This implementation uses a ternary search trie.
For additional documentation, see Section 5.2 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

Constructor Summary

Constructors
Constructor and Description

TST()
Initializes an empty string symbol table.

Constructors
Constructor and Description
`TST()` Initializes an empty string symbol table.

Method Summary

All Methods Static Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`boolean`	`contains(String key)` Does this symbol table contain the given key?
`Value`	`get(String key)` Returns the value associated with the given key.
`Iterable<String>`	`keys()` Returns all keys in the symbol table as an `Iterable`.
`Iterable<String>`	`keysThatMatch(String pattern)` Returns all of the keys in the symbol table that match `pattern`, where the character '.' is interpreted as a wildcard character.
`Iterable<String>`	`keysWithPrefix(String prefix)` Returns all of the keys in the set that start with `prefix`.
`String`	`longestPrefixOf(String query)` Returns the string in the symbol table that is the longest prefix of `query`, or `null`, if no such string.
`static void`	`main(String[] args)` Unit tests the `TST` data type.
`void`	`put(String key, Value val)` Inserts the key-value pair into the symbol table, overwriting the old value with the new value if the key is already in the symbol table.
`int`	`size()` Returns the number of key-value pairs in this symbol table.

Methods inherited from class Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Constructor Detail
  - TST
```
public TST()
```
    Initializes an empty string symbol table.
- Method Detail
  - size
```
public int size()
```
    Returns the number of key-value pairs in this symbol table.
    
    Returns:
    
    the number of key-value pairs in this symbol table
  - contains
```
public boolean contains(String key)
```
    Does this symbol table contain the given key?
    
    Parameters:
    
    key - the key
    
    Returns:
    
    true if this symbol table contains key and false otherwise
    
    Throws:
    
    IllegalArgumentException - if key is null
  - get
```
public Value get(String key)
```
    Returns the value associated with the given key.
    
    Parameters:
    
    key - the key
    
    Returns:
    
    the value associated with the given key if the key is in the symbol table and null if the key is not in the symbol table
    
    Throws:
    
    IllegalArgumentException - if key is null
  - put
```
public void put(String key,
                Value val)
```
    Inserts the key-value pair into the symbol table, overwriting the old value with the new value if the key is already in the symbol table. If the value is null, this effectively deletes the key from the symbol table.
    
    Parameters:
    
    key - the key
    
    val - the value
    
    Throws:
    
    IllegalArgumentException - if key is null
  - longestPrefixOf
```
public String longestPrefixOf(String query)
```
    Returns the string in the symbol table that is the longest prefix of query, or null, if no such string.
    
    Parameters:
    
    query - the query string
    
    Returns:
    
    the string in the symbol table that is the longest prefix of query, or null if no such string
    
    Throws:
    
    IllegalArgumentException - if query is null
  - keys
```
public Iterable<String> keys()
```
    Returns all keys in the symbol table as an Iterable. To iterate over all of the keys in the symbol table named st, use the foreach notation: for (Key key : st.keys()).
    
    Returns:
    
    all keys in the symbol table as an Iterable
  - keysWithPrefix
```
public Iterable<String> keysWithPrefix(String prefix)
```
    Returns all of the keys in the set that start with prefix.
    
    Parameters:
    
    prefix - the prefix
    
    Returns:
    
    all of the keys in the set that start with prefix, as an iterable
    
    Throws:
    
    IllegalArgumentException - if prefix is null
  - keysThatMatch
```
public Iterable<String> keysThatMatch(String pattern)
```
    Returns all of the keys in the symbol table that match pattern, where the character '.' is interpreted as a wildcard character.
    
    Parameters:
    
    pattern - the pattern
    
    Returns:
    
    all of the keys in the symbol table that match pattern, as an iterable, where . is treated as a wildcard character.
  - main
```
public static void main(String[] args)
```
    Unit tests the TST data type.
    
    Parameters:
    
    args - the command-line arguments

Class TST<Value>

Constructor Summary

Method Summary

Methods inherited from class Object

Constructor Detail

TST

Method Detail

size

contains

get

put

longestPrefixOf

keys

keysWithPrefix

keysThatMatch

main