Trie/字典树/前缀树原理及可视化

Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);
map.put("app", 2);
map.put("appl", 3);

// Trie 树的键类型固定为 String 类型，值类型可以是泛型
TrieMap<Integer> map = new TrieMap<>();
map.put("apple", 1);
map.put("app", 2);
map.put("appl", 3);

// Trie 树的键类型固定为 String 类型，值类型可以是泛型
TrieMap<Integer> map = new TrieMap<>();
map.put("that", 1);
map.put("the", 2);
map.put("them", 3);
map.put("apple", 4);

// "the" 是 "themxyz" 的最短前缀
System.out.println(map.shortestPrefixOf("themxyz")); // "the"

// "them" 是 "themxyz" 的最长前缀
System.out.println(map.longestPrefixOf("themxyz")); // "them"

// "tha" 是 "that" 的前缀
System.out.println(map.hasKeyWithPrefix("tha")); // true

// 没有以 "thz" 为前缀的键
System.out.println(map.hasKeyWithPrefix("thz")); // false

// "that", "the", "them" 都是 "th" 的前缀
System.out.println(map.keysWithPrefix("th")); // ["that", "the", "them"]

// Trie 树的键类型固定为 String 类型，值类型可以是泛型
// 支持通配符匹配，"." 可以匹配任意一个字符
TrieMap<Integer> map = new TrieMap<>();

map.put("that", 1);
map.put("the", 2);
map.put("team", 3);
map.put("zip", 4);

// 匹配 "t.a." 的键有 "team", "that"
System.out.println(map.keysWithPattern("t.a.")); // ["team", "that"]

// 匹配 ".ip" 的键有 "zip"
System.out.println(map.hasKeyWithPattern(".ip")); // true

// 没有匹配 "z.o" 的键
System.out.println(map.hasKeyWithPattern("z.o")); // false

// Trie 树的键类型固定为 String 类型，值类型可以是泛型
TrieMap<Integer> map = new TrieMap<>();

map.put("that", 1);
map.put("the", 2);
map.put("them", 3);
map.put("zip", 4);
map.put("apple", 5);

// 按照字典序遍历键
System.out.println(map.keys()); // ["apple", "that", "the", "them", "zip"]

// 基本的二叉树节点
type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}

// 基本的二叉树节点
class TreeNode {
    int val;
    TreeNode left, right;
}

// 基本的多叉树节点
type TreeNode struct {
    val int
    children []*TreeNode
}

// 基本的多叉树节点
class TreeNode {
    int val;
    TreeNode[] children;
}

// Trie 树节点实现
type TrieNode struct {
    val      interface{}
    children [256]*TrieNode
}

// Trie 树节点实现
class TrieNode<V> {
    V val = null;
    TrieNode<V>[] children = new TrieNode[256];
}

// 底层用 Trie 树实现的键值映射
// 键为 string 类型，值为类型 V
type TrieMap struct{}

// 在 Map 中添加 key
func (tm *TrieMap) put(key string, val interface{})

// 删除键 key 以及对应的值
func (tm *TrieMap) remove(key string)

// 搜索 key 对应的值，不存在则返回 nil
// get("the") -> 4
// get("tha") -> nil
func (tm *TrieMap) get(key string) interface{}

// 判断 key 是否存在在 Map 中
// containsKey("tea") -> false
// containsKey("team") -> true
func (tm *TrieMap) containsKey(key string) bool

// 在 Map 的所有键中搜索 query 的最短前缀
// shortestPrefixOf("themxyz") -> "the"
func (tm *TrieMap) shortestPrefixOf(query string) string

// 在 Map 的所有键中搜索 query 的最长前缀
// longestPrefixOf("themxyz") -> "them"
func (tm *TrieMap) longestPrefixOf(query string) string

// 搜索所有前缀为 prefix 的键
// keysWithPrefix("th") -> ["that", "the", "them"]
func (tm *TrieMap) keysWithPrefix(prefix string) []string

// 判断是和否存在前缀为 prefix 的键
// hasKeyWithPrefix("tha") -> true
// hasKeyWithPrefix("apple") -> false
func (tm *TrieMap) hasKeyWithPrefix(prefix string) bool

// 通配符 . 匹配任意字符，搜索所有匹配的键
// keysWithPattern("t.a.") -> ["team", "that"]
func (tm *TrieMap) keysWithPattern(pattern string) []string

// 通配符 . 匹配任意字符，判断是否存在匹配的键
// hasKeyWithPattern(".ip") -> true
// hasKeyWithPattern(".i") -> false
func (tm *TrieMap) hasKeyWithPattern(pattern string) bool

// 返回 Map 中键值对的数量
func (tm *TrieMap) size() int

// 底层用 Trie 树实现的键值映射
// 键为 String 类型，值为类型 V
class TrieMap<V> {

    // **** 增/改 ****

    // 在 Map 中添加 key
    public void put(String key, V val);

    // **** 删 ****

    // 删除键 key 以及对应的值
    public void remove(String key);

    // **** 查 ****

    // 搜索 key 对应的值，不存在则返回 null
    // get("the") -> 4
    // get("tha") -> null
    public V get(String key);

    // 判断 key 是否存在在 Map 中
    // containsKey("tea") -> false
    // containsKey("team") -> true
    public boolean containsKey(String key);

    // 在 Map 的所有键中搜索 query 的最短前缀
    // shortestPrefixOf("themxyz") -> "the"
    public String shortestPrefixOf(String query);

    // 在 Map 的所有键中搜索 query 的最长前缀
    // longestPrefixOf("themxyz") -> "them"
    public String longestPrefixOf(String query);

    // 搜索所有前缀为 prefix 的键
    // keysWithPrefix("th") -> ["that", "the", "them"]
    public List<String> keysWithPrefix(String prefix);

    // 判断是和否存在前缀为 prefix 的键
    // hasKeyWithPrefix("tha") -> true
    // hasKeyWithPrefix("apple") -> false
    public boolean hasKeyWithPrefix(String prefix);

    // 通配符 . 匹配任意字符，搜索所有匹配的键
    // keysWithPattern("t.a.") -> ["team", "that"]
    public List<String> keysWithPattern(String pattern);

    // 通配符 . 匹配任意字符，判断是否存在匹配的键
    // hasKeyWithPattern(".ip") -> true
    // hasKeyWithPattern(".i") -> false
    public boolean hasKeyWithPattern(String pattern);

    // 返回 Map 中键值对的数量
    public int size();
}