? Trie 也叫做字典樹(shù)舶治、前綴樹(shù)（Prefix Tree）亿鲜、單詞查找樹(shù)
? Trie 搜索字符串的效率主要跟字符串的長(zhǎng)度有關(guān)
? 假設(shè)使用 Trie 存儲(chǔ) cat、dog、doggy齿穗、does、cast饺律、add 六個(gè)單詞
接口設(shè)計(jì)
int size();
boolean isEmpty();
void clear();
boolean contains(String str);
void add(String st );
void remove(String str);
boolean starsWith(String prefix);
int size();
boolean isEmpty();
void clear();
boolean contains(String str);
V add(String str, V value);
V remove(String str);
boolean starsWith(String prefix);
代碼
package com.njf;
import java.util.HashMap;
public class Trie<V> {
/*
* size代表單詞的數(shù)量
*/
private int size;
private Node<V> root;
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void clear() {
size = 0;
root = null;
}
/*
* 獲取字符串最后一個(gè)字符對(duì)應(yīng)的節(jié)點(diǎn)窃页，如果節(jié)點(diǎn)不為空且是單詞，就返回該節(jié)點(diǎn)的value
*/
public V get(String key) {
Node<V> node = node(key);
return node != null && node.word ? node.value : null;
}
public boolean contains(String key) {
Node<V> node = node(key);
return node != null && node.word;
}
public V add(String key, V value) {
//檢測(cè)key是否為空
keyCheck(key);
// 創(chuàng)建根節(jié)點(diǎn)
if (root == null) {
root = new Node<>(null);
}
Node<V> node = root;
int len = key.length();
//遍歷字符串key
for (int i = 0; i < len; i++) {
//獲取字符串的每個(gè)字符
char c = key.charAt(i);
//判斷子節(jié)點(diǎn)的哈希map是否為空复濒，也就是子節(jié)點(diǎn)是否為空
boolean emptyChildren = node.children == null;
Node<V> childNode = emptyChildren ? null : node.children.get(c);
if (childNode == null) {
//子節(jié)點(diǎn)為空就創(chuàng)建該節(jié)點(diǎn)
childNode = new Node<>(node);
childNode.character = c;
node.children = emptyChildren ? new HashMap<>() : node.children;
//子節(jié)點(diǎn)賦值到父節(jié)點(diǎn)的hashMap中
node.children.put(c, childNode);
}
node = childNode;
}
//獲取到字符串的最后一個(gè)字符對(duì)應(yīng)的節(jié)點(diǎn)
if (node.word) {// 已經(jīng)存在這個(gè)單詞
V oldValue = node.value;
node.value = value;
return oldValue;
}
//新增一個(gè)單詞
node.word = true;
node.value = value;
size ++;
return null;
}
public V remove(String key) {
// 找到最后一個(gè)節(jié)點(diǎn)
Node<V> node = node(key);
// 如果不是單詞結(jié)尾脖卖，不用作任何處理
if (node == null || !node.word) return null;
size --;
V oldValue = node.value;
// 如果還有子節(jié)點(diǎn)，就把紅色的子節(jié)點(diǎn)改變成藍(lán)色
if (node.children != null && !node.children.isEmpty()) {
node.word = false;
node.value = null;
return oldValue;
}
// 如果沒(méi)有子節(jié)點(diǎn)
Node<V> parent = null;
//一直往父節(jié)點(diǎn)尋找巧颈，直到父節(jié)點(diǎn)有其他子節(jié)點(diǎn)或者父節(jié)點(diǎn)是紅色畦木，停止刪除字符
while ((parent = node.parent) != null) {
parent.children.remove(node.character);
if (parent.word || !node.parent.children.isEmpty()) break;
node = parent;
}
return oldValue;
}
public boolean startsWith(String prefix) {
return node(prefix) != null;
}
private Node<V> node(String key){
keyCheck(key);
Node<V> node = root;
int len = key.length();
for (int i = 0; i < len; i++) {
if (node == null || node.children == null || node.children.isEmpty()) return null;
char c = key.charAt(i);
//子節(jié)點(diǎn) = 父節(jié)點(diǎn)的hashMap.get(c)
node = node.children.get(c);
}
return node;
}
private void keyCheck(String key) {
if (key == null || key.length() == 0) {
throw new IllegalArgumentException("key must not be empty");
}
}
private static class Node<V>{
//刪除的的時(shí)候使用
Node<V> parent;
//存儲(chǔ)字符和字符對(duì)應(yīng)的子節(jié)點(diǎn)
HashMap<Character, Node<V>> children;
//value只存儲(chǔ)在紅色節(jié)點(diǎn)中
V value;
//刪除使用，根據(jù)節(jié)點(diǎn)的字符砸泛，在父節(jié)點(diǎn)的hashMap中刪除子節(jié)點(diǎn)
//只有要?jiǎng)h除的單詞的對(duì)應(yīng)的最后一個(gè)節(jié)點(diǎn)是葉子節(jié)點(diǎn)的時(shí)候十籍，而且是紅色（紅色代表是單詞）
//根節(jié)點(diǎn)沒(méi)有character，只有子節(jié)點(diǎn)有
Character character;
boolean word;//是否為單詞的結(jié)尾（是否為一個(gè)完整的單詞）
public Node(Node<V> parent) {
this.parent = parent;
}
}
}
驗(yàn)證
package com.njf;
public class Main {
static void test1() {
Trie<Integer> trie = new Trie<>();
trie.add("cat", 1);
trie.add("dog", 2);
trie.add("catalog", 3);
trie.add("cast", 4);
trie.add("呵呵", 5);
Asserts.test(trie.size() == 5);
Asserts.test(trie.startsWith("do"));
Asserts.test(trie.startsWith("c"));
Asserts.test(trie.startsWith("ca"));
Asserts.test(trie.startsWith("cat"));
Asserts.test(trie.startsWith("cata"));
Asserts.test(!trie.startsWith("hehe"));
Asserts.test(trie.get("呵呵") == 5);
Asserts.test(trie.contains("cat"));
Asserts.test(trie.remove("cat") == 1);
Asserts.test(trie.remove("catalog") == 3);
Asserts.test(trie.remove("cast") == 4);
Asserts.test(trie.size() == 2);
Asserts.test(trie.startsWith("小"));
Asserts.test(trie.startsWith("do"));
Asserts.test(!trie.startsWith("c"));
}
public static void main(String[] args) {
test1();
}
}
總結(jié)
? Trie 的優(yōu)點(diǎn)：搜索前綴的效率主要跟前綴的長(zhǎng)度有關(guān)
? Trie 的缺點(diǎn)：需要耗費(fèi)大量的內(nèi)存唇礁，因此還有待改進(jìn)
? 更多Trie 相關(guān)的數(shù)據(jù)結(jié)構(gòu)和算法
Double-array Trie勾栗、Suffix Tree、Patricia Tree盏筐、Crit-bit Tree围俘、AC自動(dòng)機(jī)
