Trie樹簡介
Trie 樹庐镐，也叫字典樹或者叫前綴樹。顧名思義，它是一個樹形結(jié)構(gòu)贝搁。它是一種專門處理字符串匹配的樹狀結(jié)構(gòu)吗氏，用來解決在一組字符串集合中快速查找某個字符串的問題。Trie 樹的本質(zhì)雷逆，就是利用字符串之間的公共前綴弦讽，將重復(fù)的前綴合并在一起。
下面展示了一個由“hello”关面、“her”坦袍、“hi”、“how”等太、“see”以及“so”組成的Trie樹捂齐。
Trie特點
由上圖中的Trie中可知
- Trie的每個節(jié)點存儲一個字符，根節(jié)點不保存字符
- 從根節(jié)點到某一個節(jié)點缩抡，路徑上經(jīng)過的字符連接起來奠宜，為該節(jié)點對應(yīng)的字符串
- 每個節(jié)點的所有子節(jié)點包含的字符都不相同
實現(xiàn)Trie樹
Trie樹節(jié)點
由于每個節(jié)點只存儲一個字符，以及指向它的子節(jié)點瞻想，那么對于每個節(jié)點有如下的數(shù)據(jù)結(jié)構(gòu)
function TrieNode(key) {
this.key = key;
this.children = [];
}
其中key保存了這個節(jié)點的值压真，children中保存了該節(jié)點的所有子節(jié)點（對于小寫英文字母而言，這個數(shù)組的長度為26）
Trie樹的插入
構(gòu)建一棵Trie樹就是將字符串逐個插入的過程蘑险。由于Trie的特點滴肿，插入操作的過程中。要先判斷Trie是否已經(jīng)存在了與待插入字符串相同的前綴佃迄，找到所有的公共前綴后泼差，將不同的字符插入Trie中。對于插入的過程呵俏，大致的代碼如下：
// 采用遞歸插入字符串
function insertData(data, node){
if (data === '') {
return;
}
let children = node.children;
let haveData = null;
// 判斷存儲子節(jié)點的數(shù)組中堆缘，是否有與插入字符串的第一個值匹配的節(jié)點
for (let i in children) {
if (children[i].key == data[0]) {
haveData = children[i];
}
}
if(haveData) {
// 待插入的第一個字符已經(jīng)存在children數(shù)組中，則繼續(xù)判斷下一個字符
this.insertData(data.substring(1), haveData);
}else{
// 未找到相應(yīng)的子節(jié)點普碎，分為兩種情況
// 已經(jīng)是現(xiàn)有Trie的葉子節(jié)點
if(children.length === 0) {
let insertNode = new TrieNode(data[0]);
children.push(insertNode);
this.insertData(data.substring(1), insertNode);
}else{
// 要在當(dāng)前的children中找到合適的位置吼肥，插入字符
let validPosition = 0;
for (let j in children) {
if (children[j].key < data[0]) {
validPosition++;
}
}
let insertNode = new TrieNode(data[0]);
children.splice(validPosition, 0, insertNode);
this.insertData(data.substring(1), insertNode);
}
}
}
在插入Trie樹的過程中，需要遍歷所有的字符串麻车，時間復(fù)雜度是O(n)缀皱，n表示所有字符串的長度和。
Trie樹的查找
查找的過程與插入的過程類似动猬，需要逐層遍歷唆鸡，尋找與待匹配字符串相同的字符。其大概代碼如下：
function search (data) {
if (data === '' || this.root.children.length === 0) {
return false;
}
// 遍歷children
for (let i in this.root.children) {
if (this.searchNext(this.root.children[i], data)) {
return true;
}
}
return false;
}
// 遞歸查找
function searchNext(node, data) {
if(data[0] !== node.key) return false;
let children = node.children;
// 該節(jié)點已經(jīng)是葉子節(jié)點枣察，并且待查找字符串已查找完畢
if(children.length === 0 && data.length === 1) {
return true;
} else if(children.length > 0 && data.length > 1) {
for(let i in children) {
// 繼續(xù)判斷下一個字符
if(children[i].key === data[1]) {
return searchNext(children[i], data.substring(1));
}
}
} else {
return false;
}
}
在Trie樹已經(jīng)構(gòu)建完成的情況下争占，查找一個字符串是否在Trie中效率是非常高的燃逻，其事件復(fù)雜度為O(K)，k表示待查找字符串的長度臂痕。
Trie樹的刪除
先遞歸查找到字符串的葉子節(jié)點伯襟，然后從字符串的葉子節(jié)點逐級向根節(jié)點遞歸刪除葉子節(jié)點，直到刪除字符串握童。其大概的代碼如下：
function deleteNode(data) {
if (this.search(data)) { // 判斷是否存在該單詞（字符串）
for (let i in this.root.children) {
if (this.deleteNext(this.root, i, data, data)) {
return;
}
}
}
return this;
}
/**
* @param parent 父節(jié)點
* @param index 子節(jié)點在父節(jié)點children數(shù)組中的索引位置
* @param stringData 遞歸遍歷中的字符串
* @param delStr 調(diào)用delete方法時的原始字符串
*/
function deleteNext(parent, index, stringData, delStr) {
let node = parent.children[index];
// 若字符與節(jié)點key不相等姆怪，則不匹配
if (stringData[0] != node.key) {
return false;
} else { // 若與key相等，繼續(xù)判斷
let children = node.children;
if (children.length == 0 && stringData.length == 1) { // 葉子節(jié)點澡绩，最后一個字符稽揭，則完全匹配
// 刪除葉子節(jié)點，利用父節(jié)點刪除子節(jié)點原理
parent.children.splice(index, 1);
// 字符串從尾部移除一個字符后肥卡，繼續(xù)遍歷刪除方法
this.deleteNode(delStr.substring(0, delStr.length - 1));
} else if (children.length > 0 && stringData.length > 1) { // 既不是葉子節(jié)點溪掀，也不是最后一個字符，則繼續(xù)遞歸查找
for (let i in children) {
if (children[i].key == stringData[1]) {
return this.deleteNext(node, i, stringData.substring(1), delStr); // 記得return 遞歸函數(shù)步鉴，否則獲取的返回值為undefined
}
}
}
}
}
Trie改進
Trie樹是非常消耗內(nèi)存的數(shù)據(jù)結(jié)構(gòu)揪胃，用的是一種空間換時間的思路。Trie樹的問題就在于存儲子節(jié)點的children數(shù)組中氛琢。如果字符串中只包含從a到z的26個字符喊递，那么children的長度就為26。注意阳似，這里說的是每一個Trie樹的節(jié)點骚勘，都需要申請一個長度為26的數(shù)組，即使這個節(jié)點只有一個子節(jié)點撮奏！
那么如果字符串包含了大小寫俏讹，或者是數(shù)字特殊字符。Trie所需的空間就更大了挽荡。尤其是在重復(fù)的前綴不多的情況下藐石，Trie樹不但不能節(jié)省內(nèi)存即供，而且還有可能浪費更多的內(nèi)存空間定拟。可以想到的方法就是逗嫡，將children修改為其他的數(shù)據(jù)結(jié)構(gòu)青自，比如有序數(shù)組、跳表等驱证。
對只有一個子節(jié)點的節(jié)點延窜，而且此節(jié)點不是一個串的結(jié)束節(jié)點可以將此節(jié)點與子節(jié)點合并，這就是縮點優(yōu)化抹锄。
Trie樹完整代碼
function TrieNode(key) {
this.key = key;
this.children = [];
}
function Trie() {
this.root = new TrieNode('/'); // 添加根節(jié)點
this.insert = insert; // 插入
this.insertData = insertData;
this.search = search; // 查找
this.searchNext = searchNext;
this.deleteNode = deleteNode; // 刪除
this.deleteNext = deleteNext;
this.nodeNumber = 0; // trie所有節(jié)點個數(shù)
this.print = print; // 打印Trie樹
this.printHelper = printHelper;
}
function insert(data) {
this.insertData(data, this.root);
}
function insertData(data, node){
if (data === '') {
return;
}
let children = node.children;
let haveData = null;
for (let i in children) {
if (children[i].key == data[0]) {
haveData = children[i];
}
}
if(haveData) {
this.insertData(data.substring(1), haveData);
}else{
if(children.length === 0) {
let insertNode = new TrieNode(data[0]);
children.push(insertNode);
this.insertData(data.substring(1), insertNode);
}else{
let validPosition = 0;
for (let j in children) {
if (children[j].key < data[0]) {
validPosition++;
}
}
let insertNode = new TrieNode(data[0]);
children.splice(validPosition, 0, insertNode);
this.insertData(data.substring(1), insertNode);
}
}
}
function search (data) {
if (data === '' || this.root.children.length === 0) {
return false;
}
for (let i in this.root.children) {
if (this.searchNext(this.root.children[i], data)) {
return true;
}
}
return false;
}
function searchNext(node, data) {
if(data[0] !== node.key) return false;
let children = node.children;
if(children.length === 0 && data.length === 1) {
return true;
} else if(children.length > 0 && data.length > 1) {
for(let i in children) {
if(children[i].key === data[1]) {
return searchNext(children[i], data.substring(1));
}
}
} else {
return false;
}
}
function deleteNode(data) {
if (this.search(data)) {
for (let i in this.root.children) {
if (this.deleteNext(this.root, i, data, data)) {
return;
}
}
}
return this;
}
function deleteNext(parent, index, stringData, delStr) {
let node = parent.children[index];
if (stringData[0] != node.key) {
return false;
} else {
let children = node.children;
if (children.length == 0 && stringData.length == 1) {
parent.children.splice(index, 1);
this.deleteNode(delStr.substring(0, delStr.length - 1));
} else if (children.length > 0 && stringData.length > 1) {
for (let i in children) {
if (children[i].key == stringData[1]) {
return this.deleteNext(node, i, stringData.substring(1), delStr);
}
}
}
}
}
function print () {
for (let i in this.root.children) {
this.nodeNumber++;
this.printHelper(this.root.children[i], [this.root.children[i].key]);
}
}
function printHelper (node, data) {
if (node.children.length === 0) {
console.log('>', data.join(''));
return;
}
for (let i in node.children) {
this.nodeNumber++;
data.push(node.children[i].key);
this.printHelper(node.children[i], data);
data.pop();
}
}
let trie = new Trie();
trie.insert('apple');
trie.insert('appcd');
trie.insert('banana');
trie.print();
console.log(trie.search("app"));
trie.deleteNode('appcd')
trie.print();
console.log(trie.nodeNumber);
// 輸出結(jié)果
> appcd
> apple
> banana
false
> apple
> banana
11
學(xué)習(xí)心得
第一次看Trie樹的概念逆瑞，完全沒明白到底是什么樣的數(shù)據(jù)結(jié)構(gòu)荠藤。直到看了Trie樹的圖示例，一下就明白了获高，Trie樹的概念非常好理解哈肖，就是把相同的前綴放到一起構(gòu)成了一個數(shù)據(jù)結(jié)構(gòu)。在對比字符串的時候念秧，就像查字典一層層的比較淤井。
對于每個節(jié)點的存儲結(jié)構(gòu)確實比較繞，每次遍歷children數(shù)組就相當(dāng)于去往下一層比較了摊趾，反正每次涉及到遞歸函數(shù)總是不好理解币狠。
