數據結構——字典樹

數據結構教程：字典樹（Trie，前綴樹）

一、定義與特性

字典樹，又稱前綴樹或Trie樹，是一種用於存儲字符串集合的數據結構。每個節點代表一個字符串的前綴，並且從根節點到某個節點的路徑表示了該節點對應字符串。如果一個節點是葉子節點，則表示它代表的是一個完整有效的字符串。

二、基本結構與操作

1. 節點結構：

在字典樹中，每個節點通常包含若幹個指向子節點的指針，數量等於字符集的大小。例如，在ASCII字符集中，每個節點可以有26個指向子節點的指針（對於小寫英文字母）。此外，節點還可以有一個標志來表示當前節點是否為終止節點（即代表了一個完整的單詞）。

2. 基本操作：

• 插入：將一個新的字符串插入字典樹，沿著字符串中的字符創建相應的路徑，並在最後一個字符對應的節點上標記為終止節點。

• 查找：檢查給定字符串是否存在於字典樹中，通過沿著字符串的字符路徑遍歷字典樹，判斷是否存在對應的終止節點。

• 刪除：刪除字典樹中的字符串相對復雜，需要從後往前逐步撤銷字符串路徑上的標記，並合並空節點。

三、C 示例代碼片段

class TrieNode {
public:
	// 初始化所有子節點為空指針
	TrieNode() : is_word(false) {
		for (int i = 0; i < ALPHABET_SIZE;   i)
			children[i] = nullptr;
	}
	// 指向26個子節點的指針數組
	TrieNode* children[ALPHABET_SIZE];
	bool is_word; // 標記是否為有效單詞的結束節點
};
class Trie {
private:
	TrieNode* root;
public:
	Trie() { root = new TrieNode(); }
	// 插入字符串到字典樹
	void insert(const string& word) {
		TrieNode* current = root;
		for (char ch : word) {
			int index = ch - 'a'; // 假設隻處理小寫字母
			if (!current->children[index])
				current->children[index] = new TrieNode();
			current = current->children[index];
		}
		current->is_word = true;
	}
	// 檢查字符串是否在字典樹中
	bool search(const string& word) {
		TrieNode* current = root;
		for (char ch : word) {
			int index = ch - 'a';
			if (!current->children[index])
				return false;
			current = current->children[index];
		}
		return current->is_word;
	}
	// 其他操作如刪除等在此省略...
};

總結：

字典樹提供了一種高效地存儲和查詢字符串集合的方法，特別適合於查找前綴共享的大量字符串的情況，如自動補全、拼寫檢查等功能。它的主要優點在於能夠以O(m)的時間復雜度進行單個字符串的查詢（m為字符串長度），而不需要像哈希表那樣在平均情況下保證O(1)的查詢時間復雜度所需的空間代價。