LeetCode：https://leetcode-cn.com/problems/implement-trie-prefix-tree/

什么是前綴樹

Trie（發(fā)音類似 “try”）或者說 前綴樹 是一種樹形數(shù)據(jù)結(jié)構(gòu)，用于高效地存儲(chǔ)和檢索字符串?dāng)?shù)據(jù)集中的鍵。這一數(shù)據(jù)結(jié)構(gòu)有相當(dāng)多的應(yīng)用情景，例如自動(dòng)補(bǔ)完和拼寫檢查。

• Trie() 初始化前綴樹對象。
• void insert(String word) 向前綴樹中插入字符串 word 。
• boolean search(String word) 如果字符串 word 在前綴樹中，返回 true（即，在檢索之前已經(jīng)插入）；否則，返回 false 。
• boolean startsWith(String prefix) 如果之前已經(jīng)插入的字符串 word 的前綴之一為 prefix ，返回 true ；否則，返回 false 。

實(shí)現(xiàn)前綴樹

摘自：https://leetcode-cn.com/problems/implement-trie-prefix-tree/solution/208-shi-xian-trie-qian-zhui-shu-bao-gua-insert-sea/

這是一種叫做 單詞查找樹 的結(jié)構(gòu)。它由字符串鍵中所有的字符構(gòu)造而成，允許使用被查找鍵中的字符進(jìn)行查找。其中包括插入、查找、刪除，尋找前綴等操作。接下來先介紹Trie樹的基本性質(zhì)。

先看下面的例子：

現(xiàn)在有5個(gè)word，分別為by,by,hello,heat,the。所構(gòu)成的TrieTree如圖所示，其中包含一個(gè)根節(jié)點(diǎn)，值為空，跟幾點(diǎn)所連接的是每個(gè)word的第一個(gè)字符，每個(gè)字符按照同樣的方式生成與之連接的字符的TrieTree，在每個(gè)word的最末處，表示該word出現(xiàn)了幾次。例如：“b”處為0，表示"b"這個(gè)單詞沒有出現(xiàn)過。“y”處為2，表示“by”這個(gè)單詞出現(xiàn)了兩次。

單詞查找樹之所以有這樣的，是由于我們對于其結(jié)點(diǎn)的特殊定義。單詞查找樹的每一個(gè)節(jié)點(diǎn)都包含了下一個(gè)可能出現(xiàn)的字符的鏈接。從根節(jié)點(diǎn)開始，首先經(jīng)過的是word的首字母所對應(yīng)的鏈接，在下一個(gè)節(jié)點(diǎn)中沿著第二個(gè)字符所對應(yīng)的鏈接繼續(xù)前進(jìn)，在第二個(gè)節(jié)點(diǎn)中沿著第三個(gè)字符所對應(yīng)的鏈接向前，這樣到達(dá)最后一個(gè)字符所指向的節(jié)點(diǎn)就結(jié)束。接下來我們來看對其節(jié)點(diǎn)的定義。

TrieNode

定義單詞查找樹的結(jié)點(diǎn)為：

public class TrieNode{public int path;public int end;public HashMap<Character, TrieNode> next;public TrieNode(){path = 0;end = 0;next = new HashMap<>();} }

• path：表示當(dāng)前節(jié)點(diǎn)所能鏈接到其他節(jié)點(diǎn)的個(gè)數(shù)（在刪除操作中會(huì)用到）
• end：表示以當(dāng)前節(jié)點(diǎn)為結(jié)尾的單詞的個(gè)數(shù)
• next：HashMap<Character, TrieNode>類型，表示當(dāng)前節(jié)點(diǎn)能鏈接到的所有節(jié)點(diǎn)。

這里next同樣可以使用字符數(shù)組來表示，例如字符的范圍是小寫字母，可以以’a’~'z’字符作為索引，這樣相比起哈希表來會(huì)提高查找速度，但每一個(gè)點(diǎn)都含有一個(gè)值和26個(gè)鏈接，這樣會(huì)多出好多空節(jié)點(diǎn)，如圖所示：

Insert 操作

如同鏈表的生成過程一樣，從根節(jié)點(diǎn)開始，如果根節(jié)點(diǎn)所連接的節(jié)點(diǎn)中沒有當(dāng)前字符，則生成一個(gè)值為當(dāng)前字符的新節(jié)點(diǎn)，插入其中；如果有當(dāng)前字符，則則繼續(xù)進(jìn)行匹配，并在過程中對每一個(gè)匹配到的節(jié)點(diǎn)path進(jìn)行計(jì)數(shù)，重復(fù)上述過程，直到插完最后一個(gè)字符，并在最后一個(gè)字符的節(jié)點(diǎn)end進(jìn)行計(jì)數(shù)，表示已經(jīng)該單詞的插入操作已經(jīng)完成。

public void insert(String word){if(word == null || word.equals("")) return ;TrieNode node = root;for(int i = 0; i<word.length(); i++){char ch = word.charAt(i);if(!node.next.containsKey(ch)) {node.next.put(ch,new TrieNode());}node = node.next.get(ch);node.path++;}node.end++; }

Search 操作

同insert操作基本相同，由于我這里使用的是Hashmap進(jìn)行的節(jié)點(diǎn)存儲(chǔ)，故如果在匹配的過程中沒能匹配到，則表示搜索失敗，匹配到后最后一個(gè)字符時(shí)，如果當(dāng)前end值不為零，則表示匹配成功。

public boolean search(String word){if(word == null || word.equals("")) return false;TrieNode node = root;for(int i = 0; i<word.length(); i++){char ch = word.charAt(i);if(!node.next.containsKey(ch)) return false;node = node.next.get(ch);}if(node.end == 0) return false;return true; }

startwith 操作

同search操作基本相同，只是這里判斷到最后一個(gè)字符的時(shí)候，不需要判斷end值。因?yàn)檫@里只需要檢查前綴是否存在。

public boolean startsWith(String word){if(word == null || word.equals("")) return false;TrieNode node = root;for(int i = 0; i<word.length(); i++){char ch = word.charAt(i);if(!node.next.containsKey(ch)) return false;node = node.next.get(ch);}return true; }

delete 操作

delete操作同上述操作大致相同，這里需要使用到path變量，回憶一下，path：表示當(dāng)前節(jié)點(diǎn)所能鏈接到其他節(jié)點(diǎn)的個(gè)數(shù)。還以五個(gè)單詞為例，例如刪除’the’，當(dāng)匹配到‘t’時(shí)，由于進(jìn)行path–操作后，此時(shí)判斷path為0，過可直接將當(dāng)前節(jié)點(diǎn)置空，后面的數(shù)據(jù)則不用再去遍歷即可。java中的垃圾回收機(jī)制會(huì)處理其他的被斷開的節(jié)點(diǎn)，如果在C++中，則需要全部匹配，之后調(diào)用析構(gòu)函數(shù)去操作。

public void delete(String word){if(word == null || word.equals("") || !search(word)) return ;TrieNode node = root;for (int i = 0; i < word.length(); i++) {char ch = word.charAt(i);if(--node.next.get(ch).path == 0){node.next.remove(ch);return;}node = node.next.get(ch);}node.end--; }

代碼

import java.util.HashMap;public class Trie {private TrieNode root;/*** Initialize your data structure here.*/public Trie() {root = new TrieNode();}/*** Inserts a word into the trie.*/public void insert(String word) {if (word == null || word.equals("")) {return;}TrieNode node = root;for (int i = 0; i < word.length(); i++) {char ch = word.charAt(i);if (!node.next.containsKey(ch)) {node.next.put(ch, new TrieNode());}node = node.next.get(ch);node.path++;}node.end++;}/*** Returns if the word is in the trie.*/public boolean search(String word) {if (word == null || word.equals("")) {return false;}TrieNode node = root;for (int i = 0; i < word.length(); i++) {char ch = word.charAt(i);if (!node.next.containsKey(ch)) {return false;}node = node.next.get(ch);}if (node.end == 0) {return false;}return true;}/*** Returns if there is any word in the trie that starts with the given prefix.*/public boolean startsWith(String prefix) {if (prefix == null || prefix.equals("")) {return false;}TrieNode node = root;for (int i = 0; i < prefix.length(); i++) {char ch = prefix.charAt(i);if (!node.next.containsKey(ch)) {return false;}node = node.next.get(ch);}return true;}public void delete(String word) {if (word == null || word.equals("") || !search(word)) {return;}TrieNode node = root;for (int i = 0; i < word.length(); i++) {char ch = word.charAt(i);if (--node.next.get(ch).path == 0) {node.next.remove(ch);return;}node = node.next.get(ch);}node.end--;}public class TrieNode {public int path;public int end;public HashMap<Character, TrieNode> next;public TrieNode() {this.path = 0;this.end = 0;next = new HashMap<>();}} }/*** Your Trie object will be instantiated and called as such:* Trie obj = new Trie();* obj.insert(word);* boolean param_2 = obj.search(word);* boolean param_3 = obj.startsWith(prefix);*/

總結(jié)

以上是生活随笔為你收集整理的Java 实现 Trie (前缀树)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。