Trie樹：從基礎到實現的全面詳解

一、什麼是Trie樹

Trie樹，也稱為前綴樹，是一種高效的字元串存儲、查找數據結構。它的核心思想是把字元串分成一個一個單元，用樹形結構進行存儲。

這種數據結構的最大特點是可以快速地進行前綴匹配，所以常用於大規模字元串的查找、分類、排序等操作。

Trie樹的名字來源於retrieval，意為「檢索」、「找回」。Trie樹的最初設計是由Edward Fredkin在1960年代提出的。

二、Trie樹的基本概念

對於每個字元串，我們可以把它看成一個由若干個字元組成的序列，例如”hello”可以看成”{‘h’, ‘e’, ‘l’, ‘l’, ‘o’}”。

在Trie樹中，每個節點都對應一段字元串，節點的子節點代表了可能的下一步字元。對於每個節點，它的所有子節點代表的字符集合是互不重疊的，也就是說，從根節點到某個節點的路徑表示的字元串必須是唯一的。

三、如何構建Trie樹

首先我們需要在根節點處建立一個空的Trie樹。然後，我們依次把所有的字元串插入到Trie樹中。

插入一個字元串的方法如下：

1. 從根節點開始，看第一個字元是否已經存在於Trie樹中。
2. 如果存在，就跳到這個字元對應的子節點，繼續判斷下一個字元。
3. 如果不存在，則新建一個節點作為當前節點的子節點，表示添加一個新的字元。
4. 按照上述方法，一直添加到字元串的最後一個字元為止。
5. 在字元串的最後一個節點打上一個標誌，表示這是一個字元串的結尾。

下面是Trie樹基本代碼實現：

class TrieNode(object):
    def __init__(self):
        self.children = {}
        self.is_end = False
 
class Trie(object):
    def __init__(self):
        self.root = TrieNode()
 
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True
 
    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end
 
    def starts_with(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

四、Trie樹的應用

1. 自動補全

利用Trie樹可以實現字元自動補全功能。具體實現方法是，從Trie樹的根節點開始，根據用戶輸入的前綴搜索Trie樹，找到以該前綴為前綴的字元串，將其推薦給用戶。

Trie樹可以實現快速的字元串的前綴查找，因此它比較適合用於實現自動補全功能。下面是基於Trie樹的自動補全代碼實現：

class TrieNode(object):
    def __init__(self):
        self.children = {}
        self.is_end = False
        self.word = None
 
class Trie(object):
    def __init__(self):
        self.root = TrieNode()
 
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True
        node.word = word
  
    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end
 
    def starts_with(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return None
            node = node.children[char]
        return node
      
    def dfs(self, node, words):
        if node:
            if node.is_end:
                words.append(node.word)
            for child in node.children.values():
                self.dfs(child, words)
                 
    def query(self, x):
        node = self.starts_with(x)
        words = []
        self.dfs(node, words)
        return words

2. 字元串排序

利用Trie樹可以實現字元串的快速排序功能。由於Trie樹存儲的是整個字元串集合，因此，對Trie樹進行前序遍歷，輸出每一個字元串即可得到一個有序字元串序列。即對Trie樹的DFS序遍歷結果進行排序。

下面是基於Trie樹實現字元串排序代碼：

class TrieNode(object):
    def __init__(self):
        self.children = {}
        self.is_end = False
 
class Trie(object):
    def __init__(self):
        self.root = TrieNode()
 
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True
 
    def dfs(self, node, word, res):
        if node.is_end:
            res.append(word)
        for char in node.children:
            self.dfs(node.children[char], word+char, res)
 
    def sort_words(self, words):
        trie = Trie()
        for word in words:
            trie.insert(word)
        res = []
        trie.dfs(trie.root, "", res)
        return res

3. 統計詞頻

由於Trie樹的每個節點代表一個字元串，因此可以通過記錄每個節點是否為字元串結尾來統計字元串出現的次數。具體實現方法是，在Trie樹的每個節點處設置一個計數器freq，每次遇到一個字元串結尾節點，就將對應的freq計數器加1。

下面是基於Trie樹實現統計詞頻的代碼：

class TrieNode(object):
    def __init__(self):
        self.children = {}
        self.is_end = False
        self.freq = 0
 
class Trie(object):
    def __init__(self):
        self.root = TrieNode()
 
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True
        node.freq += 1
 
    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end
 
    def starts_with(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return None
            node = node.children[char]
        return node
 
    def count_words(self, word):
        node = self.starts_with(word)
        if not node:
            return 0
        return node.freq

五、Trie樹的時間複雜度

Trie樹的時間複雜度與插入字元串的長度有關。將一個長度為L的字元串插入到Trie樹中，需要O(L)的時間。對於在Trie樹中搜索一個字元串或者進行前綴搜索，時間複雜度也與字元串長度有關，也是O(L)。

因此，Trie樹在處理字元串存儲和搜索方面非常高效。

六、總結

本文從Trie樹的基本概念、構建方法、應用場景以及時間複雜度方面進行了詳細的講解，並且給出了用Python實現的Trie樹代碼。除此之外，Trie樹還可以用於詞頻統計、字元串去重、最長公共前綴等問題。

有了Trie樹這種高效的數據結構，我們就可以更加方便地處理大規模的字元串問題。