資料結構之前綴樹

“字典樹又稱前綴樹，Trie樹，是一種樹形結構，是一種哈希樹的變種，典型應用是用于統計，排序和保存大量的字串（但不僅限于字串），所以經常被搜索引擎系統用于文本詞頻統計，

它的優點是：利用字串的公共前綴來減少查詢時間，最大限度地減少無謂的字串比較，查詢效率比哈希樹高，”------百度百科

前綴樹大致長成這樣：

前綴樹的特點：

1.根節點不包含任何字符內容，除根節點之外的其他節點只能包含一個字符；
??2.從根節點到某一節點，路徑上經過的字符連接起來，為該節點對應的字串；
??3.每個節點的所有子節點包含的字符都不相同，
??4.除根節點外，每個節點都包含一個是否是單詞或字串結尾的標識，

根據前綴樹的性質我們可以定義出他的大體結構：

我們首先來看使用陣列的方式來定義：

struct TrieNode {
		TrieNode()
			:pass(0)
			, end(0)
			, _next(26)//26個節點對應26個不同字母
		{}
		int pass;l
		int end;//記錄字串的結尾
		vector<TrieNode*>_next;
		~TrieNode() {
			for (auto it : _next) {//遍歷釋放節點
				delete it;
			}
		}
	};

前綴樹的插入：

①insert，意思就是像前綴樹中插入字串，我們先來想一想插入的程序，由于前綴樹的每個結點代表一個字母，那么其插入的程序肯定是一個一個字母進行插入的，那就對整個字串進行遍歷，如果當前字母所在的子結點為空，說明當前結點的下面還沒有串入該字母，那就直接將該字母所在的子結點處開辟一個新的結點；如果當前字符所對應的子結點不為空，那就迭代到該子結點，繼續遍歷下一個字母……當字串遍歷結束后，那最后一個字母所在的結點自然而然就是末尾結點了，那就將其end++即可：

void Insert(string word) {
			if (!word.size()) {//空串直接回傳
				return;

			}
			TrieNode* Node = _root;
			Node->pass++;
			int index = 0;//記錄對應映射位置
			for (int i = 0; i < word.size(); i++) {
				index = word[i] - 'a';
				if (!Node->_next[index]) {//如果沒有子節點開辟一個
					Node->_next[index] = new TrieNode;
				}
				Node = Node->_next[index];//迭代往后走
				Node->pass++;
			}
			Node->end++;
		}

前綴樹的查找：Search

意思就是查找當前樹中是否存在某一字串，其實根據上面插入的程序，也不難想到查找的方式了，依然是根據字串每個字符來迭代至相應結點，如果該字串中某一字符所對應的結點為空，那就說明這個字串不存在了，如果均不為空，那是不是說明這個字串就在樹中呢？不一定，比如說在前面的樹的結構圖中查找“og”，實際上這個字串是沒有的，但是它的每個結點又都存在，因此，我們還需要引入另一個判斷條件，即是這個字串的末尾字符對應的結點是否也是末尾結點，如果也是末尾結點，那么就說明字串存在了，否則就不存在，該段代碼如下：

	//word這個單詞之前加入過幾次
int Search(string word) {
			if (!word.size()) {
				return 0;
			}
			TrieNode* Node = _root;
			int index = 0;
			for (int i = 0; i < word.size(); i++) {//遍歷字串
				index = word[i] - 'a';
				if (!Node->_next[index]) {
					return 0;
				}
				Node = Node->_next[index];//迭代
			}
			return Node->end;
		}

前綴樹的前綴查找：PrefixNumber

PrefixNumber，簡單的講，就是判斷樹中是否有該前綴，比如說在前面的樹的結構圖中查找“og”，很明顯“og”是一個前綴，因此就回傳true了，這樣說的話，PrefixNumber的實作還比search更簡單，不用判斷末尾字符對應結點是否為末尾結點了，對應代碼如下：

int PrefixNumber(string pre) {
			if (!pre.size()) {
				return 0;
			}
			int index = 0;
			TrieNode* Node = _root;
			for (int i = 0; i < pre.size(); i++) {//遍歷
				index = pre[i] - 'a';
				if (Node->_next[index] == nullptr) {
					return 0;
				}
				Node = Node->_next[index];
			}
			return Node->pass;
		}

前綴樹的洗掉：

首先我們找到第一個要洗掉字串中pass值為1的位置并記錄他的父親節點和對應的下標并將所有pass值為1的節點放入set中遍歷結束后在將其一個一個釋放并將其父節點的指向置空，對應代碼：

	void Delete(string word) {
			if (!word.size()) {
				return;
			}
			if (Search(word) != 0) {
				set<TrieNode*>DeleteSet;
				TrieNode* prev = nullptr;
				int delteIndex = -1;
				TrieNode* Node = _root;
				Node->pass--;
				int index = 0;
				for (int i = 0; i < word.size(); i++) {
					index = word[i] - 'a';
					if (--Node->_next[index]->pass == 0) {
						prev = (prev == nullptr ? Node : prev);//記錄第一個pass為1的節點
						delteIndex = (delteIndex == -1 ? index : delteIndex);//記錄其下標
						DeleteSet.insert(Node->_next[index]);//放入set中
					}
					Node = Node->_next[index];
				}
				Node->end--;
				if (prev)
					prev->_next[delteIndex] = nullptr;//置空
				for (auto& it : DeleteSet) {//遍歷節點釋放
					delete it;
				}
			}

		}

代碼匯總：

struct TrieNode {
		TrieNode()
			:pass(0)
			, end(0)
			, _next(26)
		{}
		int pass;
		int end;
		vector<TrieNode*>_next;
		~TrieNode() {
			for (auto it : _next) {
				delete it;
			}
		}
	};
	class Trie {
	public:
		Trie()
			:_root(new TrieNode)
		{}
		void Insert(string word) {
			if (!word.size()) {
				return;

			}
			TrieNode* Node = _root;
			Node->pass++;
			int index = 0;
			for (int i = 0; i < word.size(); i++) {
				index = word[i] - 'a';
				if (!Node->_next[index]) {
					Node->_next[index] = new TrieNode;
				}
				Node = Node->_next[index];
				Node->pass++;
			}
			Node->end++;
		}
		void Delete(string word) {
			if (!word.size()) {
				return;
			}
			if (Search(word) != 0) {
				set<TrieNode*>DeleteSet;
				TrieNode* prev = nullptr;
				int delteIndex = -1;
				TrieNode* Node = _root;
				Node->pass--;
				int index = 0;
				for (int i = 0; i < word.size(); i++) {
					index = word[i] - 'a';
					if (--Node->_next[index]->pass == 0) {
						prev = (prev == nullptr ? Node : prev);//記錄第一個pass為1的節點
						delteIndex = (delteIndex == -1 ? index : delteIndex);
						DeleteSet.insert(Node->_next[index]);
					}
					Node = Node->_next[index];
				}
				Node->end--;
				if (prev)
					prev->_next[delteIndex] = nullptr;
				for (auto& it : DeleteSet) {
					delete it;
				}
			}

		}
		//word這個單詞之前加入過幾次
		int Search(string word) {
			if (!word.size()) {
				return 0;
			}
			TrieNode* Node = _root;
			int index = 0;
			for (int i = 0; i < word.size(); i++) {
				index = word[i] - 'a';
				if (!Node->_next[index]) {
					return 0;
				}
				Node = Node->_next[index];
			}
			return Node->end;
		}
		int PrefixNumber(string pre) {
			if (!pre.size()) {
				return 0;
			}
			int index = 0;
			TrieNode* Node = _root;
			for (int i = 0; i < pre.size(); i++) {
				index = pre[i] - 'a';
				if (Node->_next[index] == nullptr) {
					return 0;
				}
				Node = Node->_next[index];
			}
			return Node->pass;
		}
		~Trie() {

		}
	private:
		TrieNode* _root;
	};

但是如果字符種類特別多上面這種動態陣列的方式實作的就不夠用這時我們可以采用hash表來存盤節點：其他思路都是一樣的在這里就只給出代碼：

struct TrieNode {

		int _pass;
		int _end;
		unordered_map<char, TrieNode*>_hash;
		TrieNode()
			:_pass(0)
			,_end(0)
		{}
		~TrieNode() {
			for (auto &x : _hash) {
				delete x.second;
			}
		}
	};

	class Trie{
	public:
		Trie()
	    :_root(new TrieNode)
		{}

			void Insert(string word) {
				if (word.size() == 0)return;
				TrieNode* Node = _root;
				Node->_pass++;
				for (int i = 0; i < word.size(); i++) {
					if (Node->_hash[word[i]]==nullptr) {
						Node->_hash[word[i]] = new TrieNode;
					}
					Node = Node->_hash[word[i]];
					Node->_pass++;

				}
				Node->_end++;
		     }
	
			int Search(string word) {
				if (word.size() == 0) {
					return 0;
				}
				TrieNode* Node = _root;
				for (int i = 0; i < word.size(); i++) {
					if (Node->_hash[word[i]] == nullptr) {
						return 0;
					}
					Node=Node->_hash[word[i]];
				}
				return Node->_end;
			}
		int PrefixNumber(string pre) {
			if (pre.size() == 0)return 0;
			TrieNode* Node = _root;
			for (int i = 0; i < pre.size(); i++) {
				if (Node->_hash[pre[i]] == nullptr) {
					return 0;
				}
				Node = Node->_hash[pre[i]];
			}
			return Node->_pass;
		}
		void delte(string word) {
			if (word.size() == 0)return;
			if (Search(word) !=0) {
				TrieNode* Node = _root;
				set<TrieNode*>DeleteSet;
			
				TrieNode* prev = nullptr;
				int deleteIndex = -1;
				Node->_pass--;
				for (int i = 0; i < word.size(); i++) {
					if (--Node->_hash[word[i]]->_pass == 0) {
						prev = (prev == nullptr ? Node : prev);
						deleteIndex = (deleteIndex == -1 ? i : deleteIndex);
						DeleteSet.insert(Node->_hash[word[i]]);
					}
					Node = Node->_hash[word[i]];
				}
				Node->_end--;
				if(prev)
				prev->_hash[word[deleteIndex]] = nullptr;
				for (auto& x : DeleteSet) {
					delete x;
				}
			}
    	}
	private:
		TrieNode* _root;
	};

最后🙌🙌🙌🙌
結語：對于個人來講，在演算法上進行探索是一件有趣的時間，一個程式員，如果不喜歡編程，那么可能就失去了這份職業的樂趣，刷到我的文章的人，我希望你們可以駐足一小會，忙里偷閑的閱讀一下我的文章，可能文章的內容對你來說很簡單，(^▽^)不過文章中的每一個字都是我認真專注的見證！希望您看完之后，若是能幫到您，勞煩請您簡單動動手指鼓勵我，我必回報更大的付出~