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樹這種高效的數據結構，我們就可以更加方便地處理大規模的字符串問題。