Trie樹

Trie樹簡介

Trie 樹，也叫字典樹或者叫前綴樹。顧名思義，它是一個樹形結構。它是一種專門處理字符串匹配的樹狀結構，用來解決在一組字符串集合中快速查找某個字符串的問題。Trie 樹的本質，就是利用字符串之間的公共前綴，將重復的前綴合并在一起。

下面展示了一個由“hello”、“her”、“hi”、“how”、“see”以及“so”組成的Trie樹。

Trie-Tres.jpg

Trie特點

由上圖中的Trie中可知

  • Trie的每個節(jié)點存儲一個字符，根節(jié)點不保存字符
  • 從根節(jié)點到某一個節(jié)點，路徑上經過的字符連接起來，為該節(jié)點對應的字符串
  • 每個節(jié)點的所有子節(jié)點包含的字符都不相同

實現Trie樹

Trie樹節(jié)點

由于每個節(jié)點只存儲一個字符，以及指向它的子節(jié)點，那么對于每個節(jié)點有如下的數據結構

function TrieNode(key) {
    this.key = key;
    this.children = [];
}

其中key保存了這個節(jié)點的值，children中保存了該節(jié)點的所有子節(jié)點（對于小寫英文字母而言，這個數組的長度為26）

Trie樹的插入

構建一棵Trie樹就是將字符串逐個插入的過程。由于Trie的特點，插入操作的過程中。要先判斷Trie是否已經存在了與待插入字符串相同的前綴，找到所有的公共前綴后，將不同的字符插入Trie中。對于插入的過程，大致的代碼如下：

// 采用遞歸插入字符串
function insertData(data, node){
    if (data === '') {
        return;
    }

    let children = node.children;
    let haveData = null;
    
   // 判斷存儲子節(jié)點的數組中，是否有與插入字符串的第一個值匹配的節(jié)點
    for (let i in children) {
        if (children[i].key == data[0]) {
            haveData = children[i];
        }
    }
    
    if(haveData) {
        // 待插入的第一個字符已經存在children數組中，則繼續(xù)判斷下一個字符
        this.insertData(data.substring(1), haveData);
    }else{
      // 未找到相應的子節(jié)點，分為兩種情況
      // 已經是現有Trie的葉子節(jié)點
        if(children.length === 0) {
            let insertNode = new TrieNode(data[0]);
            children.push(insertNode);
            this.insertData(data.substring(1), insertNode); 
        }else{
          // 要在當前的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樹的過程中，需要遍歷所有的字符串，時間復雜度是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é)點已經是葉子節(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樹已經構建完成的情況下，查找一個字符串是否在Trie中效率是非常高的，其事件復雜度為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數組中的索引位置
* @param stringData 遞歸遍歷中的字符串
* @param delStr 調用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 遞歸函數，否則獲取的返回值為undefined
                }
            }
        }
    }
}

Trie改進

Trie樹是非常消耗內存的數據結構，用的是一種空間換時間的思路。Trie樹的問題就在于存儲子節(jié)點的children數組中。如果字符串中只包含從a到z的26個字符，那么children的長度就為26。注意，這里說的是每一個Trie樹的節(jié)點，都需要申請一個長度為26的數組，即使這個節(jié)點只有一個子節(jié)點！

那么如果字符串包含了大小寫，或者是數字特殊字符。Trie所需的空間就更大了。尤其是在重復的前綴不多的情況下，Trie樹不但不能節(jié)省內存，而且還有可能浪費更多的內存空間?？梢韵氲降姆椒ň褪?，將children修改為其他的數據結構，比如有序數組、跳表等。

對只有一個子節(jié)點的節(jié)點，而且此節(jié)點不是一個串的結束節(jié)點可以將此節(jié)點與子節(jié)點合并，這就是縮點優(yōu)化。

Trie-up.jpg

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é)點個數
    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);

// 輸出結果
> appcd
> apple
> banana
false
> apple
> banana
11

學習心得

第一次看Trie樹的概念，完全沒明白到底是什么樣的數據結構。直到看了Trie樹的圖示例，一下就明白了，Trie樹的概念非常好理解，就是把相同的前綴放到一起構成了一個數據結構。在對比字符串的時候，就像查字典一層層的比較。

對于每個節(jié)點的存儲結構確實比較繞，每次遍歷children數組就相當于去往下一層比較了，反正每次涉及到遞歸函數總是不好理解。

參考資料

?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
【社區(qū)內容提示】社區(qū)部分內容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內容（如有圖片或視頻亦包括在內）由作者上傳并發(fā)布，文章內容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關閱讀更多精彩內容

  • 什么是“Trie樹”? Trie樹，又稱前綴樹或字典樹，是一種有序樹，用于保存關聯(lián)數組，其中的鍵通常是字符串。與二...
    尼桑麻閱讀 912評論 0贊 2
  • 數據結構在各大開發(fā)語言中應用廣泛，尤其是后端開發(fā)對數據的處理，而大部分前端開發(fā)很少應用到，或是應用場景不允許等因素...
    煙傷肺閱讀 3,605評論 1贊 3
  • 字典樹（Trie）筆記 特別聲明 本文只是一篇筆記類的文章，所以不存在什么抄襲之類的。 以下為我研究時參考過的鏈接...
    Harlan1994閱讀 20,370評論 2贊 21
  • 1、 概述 Trie樹，又稱字典樹，單詞查找樹或者前綴樹，是一種用于快速檢索的多叉樹結構，如英文字母的字典樹是一個...
    Shadowsocks2閱讀 798評論 1贊 2
  • 聲明:摘自github:https://github.com/ZtesoftCS/go-ethereum-code...
    藍Renly閱讀 847評論 0贊 0

友情鏈接更多精彩內容