介紹
Trie（也稱為字典樹或前綴樹）是一種特殊的資料結構，用於高效地存儲和檢索字符串集合。
該結構的名稱來自於英文單詞「retrieval」的前三個字母。
Trie 使用一種樹狀結構來組織和存儲字符串。
每個節點代表一個字元，從根節點到葉節點的路徑形成一個字符串。
在 Trie 中，共享相同前綴的字符串共用相同的前綴節點，從而實現高效的儲存和檢索。
Trie 的主要優點是：
- 前綴匹配：Trie 可以非常快速地進行前綴匹配，這使得它在許多字符串檢索的應用中非常有用。例如，你可以使用 Trie 在一個大型字典中快速查詢以特定前綴開始的單詞。
- 空間效率：儘管 Trie 在存儲字符串集合時可能需要較多的內存，但當字符串共享相同前綴時，Trie 可以有效地壓縮存儲空間，減少重複數據的存儲。
- 插入和查詢效率：Trie 的插入和查詢操作的時間複雜度都是 O(m)，其中 m 是字符串的平均長度。這使得 Trie 在需要高效的插入和查詢操作的情況下非常有用。
Trie 的基本結構由節點和指向子節點的指針組成。每個節點包含一個字符和一個指向下一級節點的指針數組（通常是一個數組，索引對應於字符集中的字符）。
此外，每個節點還可以包含其他有關字符串的訊息，例如計數器或標記，以滿足特定的應用需求。
基本的插入和查詢操作
-
Trie 的插入操作非常簡單，只需按照字符串的每個字符在 Trie 中進行遞歸查找。如果遇到缺少的字符，則創建相應的節點。當達到字符串的結尾時，可以在終止節點中標記該字符串的結束。
-
Trie 的查詢操作也很簡單，只需按照要查詢的字符串的每個字符在 Trie 中進行遞歸查找。如果遇到缺少的字符或到達了 Trie 的結尾，則可以確定該字符串不在 Trie 中。否則，繼續遞歸查找直到字符串的結尾。
除了基本的插入和查詢操作，Trie 還可以進行前綴匹配、模式匹配和字典排序等操作。
總之，Trie 是一種非常有用的資料結構，特別適合處理字符串集合和字典應用。
它提供了高效的插入、查詢和前綴匹配功能，同時具有優秀的空間壓縮性能。
實作
class TrieNode {
constructor() {
this.children = {};
this.isEndOfWord = false;
}
}
class Trie {
constructor() {
this.root = new TrieNode();
}
insert(word) {
let current = this.root;
for (let i = 0; i < word.length; i++) {
const char = word[i];
if (!current.children[char]) {
current.children[char] = new TrieNode();
}
current = current.children[char];
}
current.isEndOfWord = true;
}
search(word) {
let current = this.root;
for (let i = 0; i < word.length; i++) {
let char = word[i];
if (!current.children[char]) {
return false;// 字符不存在，該字符串不在 Trie 中
}
current = current.children[char];
}
return current.isEndOfWord;// 判斷是否為一個完整的單詞
}
startsWith(prefix) {
let current = this.root;
for (let i = 0; i < prefix.length; i++) {
let char = prefix[i];
if (!current.children[char]) {
return false; // 字符不存在，該前綴不在 Trie 中
}
current = current.children[char];
}
return true; // 所有前綴字符都存在於 Trie 中
}
}
// 使用示例
const trie = new Trie();
trie.insert("apple");
trie.insert("banana");
trie.insert("cat");
console.log(JSON.stringify(trie));
/**
{"root":{"children":{
"a":{"children":{"p":{"children":{"p":{"children":{"l":{"children":{"e":{"children":{},"isEndOfWord":true}},"isEndOfWord":false}},"isEndOfWord":false}},"isEndOfWord":false}},"isEndOfWord":false},
"b":{"children":{"a":{"children":{"n":{"children":{"a":{"children":{"n":{"children":{"a":{"children":{},"isEndOfWord":true}},"isEndOfWord":false}},"isEndOfWord":false}},"isEndOfWord":false}},"isEndOfWord":false}},"isEndOfWord":false},
"c":{"children":{"a":{"children":{"t":{"children":{},"isEndOfWord":true}},"isEndOfWord":false}},"isEndOfWord":false}},"isEndOfWord":false}}
*/
console.log(trie.search("apple")); // true
console.log(trie.search("banana")); // true
console.log(trie.search("cat")); // true
console.log(trie.search("dog")); // false
console.log(trie.startsWith("app")); // true
console.log(trie.startsWith("ban")); // true
console.log(trie.startsWith("ca")); // true
console.log(trie.startsWith("do")); // false
說明
-
在 insert 方法中，我們從根節點開始遍歷 Trie。對於要插入的每個字符，我們檢查它是否已經在當前節點的子節點中存在。
如果不存在，我們創建一個新的節點並將其添加到子節點中。然後，我們將當前節點移至新創建的節點，繼續處理下一個字符。
當處理完所有字符後，我們將最後一個字符的 isEndOfWord 屬性設置為 true，以標記字符串的結束。 -
search 方法用於檢查給定的字符串是否存在於 Trie 中。我們從根節點開始遍歷 Trie，對於字符串的每個字符，我們檢查它是否存在於當前節點的子節點中。
如果遍歷完所有字符後，最後一個節點的 isEndOfWord 屬性為 true，則表示該字符串存在於 Trie 中。 -
startsWith 方法用於檢查是否存在以給定前綴開頭的字符串。過程與 search 方法類似，我們遍歷前綴的每個字符，檢查它們是否存在於當前節點的子節點中。
如果遍歷完所有前綴字符後，所有字符都存在於 Trie 中，則表示該前綴存在。
總結
- Trie 來自於英文單詞「retrieval」，用於高效地存儲和檢索字符串集合。
- 每個節點代表一個字符，以及從根節點到葉節點的路徑形成一個字符串。同時，共享相同前綴的字符串共用相同的前綴節點。
- 關於 Trie 的優點：前綴匹配、空間效率，以及插入和查詢效率。
- 您對 Trie 節點的組成以及 Trie 插入和查詢操作的描述。
- Trie 確實可以進行前綴匹配、模式匹配和字典排序等高級操作。
- 是一種非常有用的資料結構，特別適合處理字符串集合和字典應用，具有高效的插入、查詢和前綴匹配功能，同時具有優秀的空間壓縮性能。
最後，如果你覺得我的分享對你有幫助，請給予我一個愛心，並且分享這篇文章，這將是對我最大的鼓勵！