Trie樹，也被稱為前綴樹，是一種用于處理字符串的數據結構。它可以高效地進行字符串的插入、刪除和搜索操作，并且能夠快速找到具有相同前綴的字符串。本篇博客將詳細介紹Trie樹的實現原理和應用場景，并給出Java代碼示例。
Trie樹的基本結構
Trie樹的基本結構由節點和邊組成，每個節點表示一個字符，每條邊表示一個字符的連接。從根節點到葉子節點的路徑表示一個完整的字符串。
在Java代碼示例中，我們定義了兩種Trie樹的實現方式。 Trie1 使用數組作為節點的存儲結構， Trie2 使用哈希表作為節點的存儲結構。兩種實現方式在時間復雜度上沒有本質的差異，只是在空間復雜度上有所不同。
Trie樹的基本操作
Trie樹的基本操作包括插入、刪除、搜索和前綴匹配。
插入操作
插入操作用于將一個字符串插入到Trie樹中。具體步驟如下：
- 從根節點開始，遍歷字符串的每個字符。
- 對于每個字符，判斷是否存在與之對應的子節點。
- 如果不存在，則創建一個新的節點，并將其作為當前節點的子節點。
- 如果存在，則將當前節點指向該子節點。
- 在遍歷完所有字符后，將當前節點的
end計數加一，表示該字符串的插入次數。
刪除操作
刪除操作用于從Trie樹中刪除一個字符串。具體步驟如下：
- 首先通過搜索操作判斷該字符串是否存在于Trie樹中。
- 如果存在，則從根節點開始，遍歷字符串的每個字符。
- 對于每個字符，判斷是否存在與之對應的子節點。
- 如果存在，則將當前節點指向該子節點。
- 如果不存在，則返回，表示該字符串不存在于Trie樹中。
- 在遍歷完所有字符后，將當前節點的
end計數減一。 - 如果當前節點的
pass計數為0，表示該節點沒有其他字符串經過，可以將其刪除。
搜索操作
搜索操作用于判斷一個字符串在Trie樹中出現的次數。具體步驟如下：
- 從根節點開始，遍歷字符串的每個字符。
- 對于每個字符，判斷是否存在與之對應的子節點。
- 如果存在，則將當前節點指向該子節點。
- 如果不存在，則返回0，表示該字符串不存在于Trie樹中。
- 在遍歷完所有字符后，返回當前節點的
end計數，即表示該字符串在Trie樹中出現的次數。
前綴匹配操作
前綴匹配操作用于統計所有以給定前綴開頭的字符串的出現次數。具體步驟如下：
- 從根節點開始，遍歷前綴字符串的每個字符。
- 對于每個字符，判斷是否存在與之對應的子節點。
- 如果存在，則將當前節點指向該子節點。
- 如果不存在，則返回0，表示沒有以該前綴開頭的字符串。
- 在遍歷完所有字符后，返回當前節點的
pass計數，即表示所有以該前綴開頭的字符串的出現次數。
示例與測試
在代碼示例中，我們通過隨機生成字符串數組的方式進行了多次測試，分別使用 Trie1 、 Trie2 和 Right （正確的實現方式）進行插入、刪除、搜索和前綴匹配操作，并對結果進行了比較驗證。
// 示例代碼
package class08;import java.util.HashMap;// 該程序完全正確
public class Code01_TrieTree {public static class Node1 {public int pass;//記錄字符經過的個數public int end;//記錄字符結束的個數public Node1[] nexts;//節點數組// char tmp = 'b' (tmp - 'a')public Node1() {pass = 0;end = 0;nexts = new Node1[26];}}public static class Trie1 {private Node1 root;public Trie1() {root = new Node1();}public void insert(String word) {if (word == null) {return;}char[] str = word.toCharArray();Node1 node = root;//頭節點node.pass++;//有字符經過時int path = 0;for (int i = 0; i < str.length; i++) { // 從左往右遍歷字符path = str[i] - 'a'; // 由字符，對應成走向哪條路if (node.nexts[path] == null) {node.nexts[path] = new Node1();}node = node.nexts[path];node.pass++;}node.end++;}public void delete(String word) {if (search(word) != 0) {char[] chs = word.toCharArray();Node1 node = root;node.pass--;int path = 0;for (int i = 0; i < chs.length; i++) {path = chs[i] - 'a';if (--node.nexts[path].pass == 0) {node.nexts[path] = null;return;}node = node.nexts[path];}node.end--;}}// word這個單詞之前加入過幾次public int search(String word) {if (word == null) {return 0;}char[] chs = word.toCharArray();Node1 node = root;int index = 0;for (int i = 0; i < chs.length; i++) {index = chs[i] - 'a';if (node.nexts[index] == null) {return 0;}node = node.nexts[index];}return node.end;}// 所有加入的字符串中，有幾個是以pre這個字符串作為前綴的public int prefixNumber(String pre) {if (pre == null) {return 0;}char[] chs = pre.toCharArray();Node1 node = root;int index = 0;for (int i = 0; i < chs.length; i++) {index = chs[i] - 'a';if (node.nexts[index] == null) {return 0;}node = node.nexts[index];}return node.pass;}}public static class Node2 {public int pass;public int end;public HashMap<Integer, Node2> nexts;public Node2() {pass = 0;end = 0;nexts = new HashMap<>();}}public static class Trie2 {private Node2 root;public Trie2() {root = new Node2();}public void insert(String word) {if (word == null) {return;}char[] chs = word.toCharArray();Node2 node = root;node.pass++;int index = 0;for (int i = 0; i < chs.length; i++) {index = (int) chs[i];if (!node.nexts.containsKey(index)) {node.nexts.put(index, new Node2());}node = node.nexts.get(index);node.pass++;}node.end++;}public void delete(String word) {if (search(word) != 0) {char[] chs = word.toCharArray();Node2 node = root;node.pass--;int index = 0;for (int i = 0; i < chs.length; i++) {index = (int) chs[i];if (--node.nexts.get(index).pass == 0) {node.nexts.remove(index);return;}node = node.nexts.get(index);}node.end--;}}// word這個單詞之前加入過幾次public int search(String word) {if (word == null) {return 0;}char[] chs = word.toCharArray();Node2 node = root;int index = 0;for (int i = 0; i < chs.length; i++) {index = (int) chs[i];if (!node.nexts.containsKey(index)) {return 0;}node = node.nexts.get(index);}return node.end;}// 所有加入的字符串中，有幾個是以pre這個字符串作為前綴的public int prefixNumber(String pre) {if (pre == null) {return 0;}char[] chs = pre.toCharArray();Node2 node = root;int index = 0;for (int i = 0; i < chs.length; i++) {index = (int) chs[i];if (!node.nexts.containsKey(index)) {return 0;}node = node.nexts.get(index);}return node.pass;}}public static class Right {private HashMap<String, Integer> box;public Right() {box = new HashMap<>();}public void insert(String word) {if (!box.containsKey(word)) {box.put(word, 1);} else {box.put(word, box.get(word) + 1);}}public void delete(String word) {if (box.containsKey(word)) {if (box.get(word) == 1) {box.remove(word);} else {box.put(word, box.get(word) - 1);}}}public int search(String word) {if (!box.containsKey(word)) {return 0;} else {return box.get(word);}}public int prefixNumber(String pre) {int count = 0;for (String cur : box.keySet()) {if (cur.startsWith(pre)) {count += box.get(cur);}}return count;}}// for testpublic static String generateRandomString(int strLen) {char[] ans = new char[(int) (Math.random() * strLen) + 1];for (int i = 0; i < ans.length; i++) {int value = (int) (Math.random() * 6);ans[i] = (char) (97 + value);}return String.valueOf(ans);}// for testpublic static String[] generateRandomStringArray(int arrLen, int strLen) {String[] ans = new String[(int) (Math.random() * arrLen) + 1];for (int i = 0; i < ans.length; i++) {ans[i] = generateRandomString(strLen);}return ans;}public static void main(String[] args) {int arrLen = 100;int strLen = 20;int testTimes = 100000;for (int i = 0; i < testTimes; i++) {String[] arr = generateRandomStringArray(arrLen, strLen);Trie1 trie1 = new Trie1();Trie2 trie2 = new Trie2();Right right = new Right();for (int j = 0; j < arr.length; j++) {double decide = Math.random();if (decide < 0.25) {trie1.insert(arr[j]);trie2.insert(arr[j]);right.insert(arr[j]);} else if (decide < 0.5) {trie1.delete(arr[j]);trie2.delete(arr[j]);right.delete(arr[j]);} else if (decide < 0.75) {int ans1 = trie1.search(arr[j]);int ans2 = trie2.search(arr[j]);int ans3 = right.search(arr[j]);if (ans1 != ans2 || ans2 != ans3) {System.out.println("Oops!");}} else {int ans1 = trie1.prefixNumber(arr[j]);int ans2 = trie2.prefixNumber(arr[j]);int ans3 = right.prefixNumber(arr[j]);if (ans1 != ans2 || ans2 != ans3) {System.out.println("Oops!");}}}}System.out.println("finish!");}}
總結
Trie樹是一種高效的字符串處理數據結構，適用于各種需要快速搜索、插入和刪除字符串的場景。本篇博客介紹了Trie樹的原理和實現方式，并給出了Java代碼示例。希望本篇博客能夠幫助讀者更好地理解和應用Trie樹。
以上就是對Trie樹的詳細介紹和應用場景的博客。希望對您有所幫助。如有任何疑問，請隨時提問。
—圖論中圖的定義與修改)
