C++前綴樹字典樹的學習與模擬實現(xiàn)代碼示例
前綴樹介紹
在計算機科學中,trie,又稱前綴樹或字典樹,是一種有序樹,用于保存關(guān)聯(lián)數(shù)組,其中的鍵通常是字符串。常用與拼寫檢查自動補全等; 是一種查找結(jié)構(gòu)他的存儲邏輯類似于哈希表,但是它相對于哈希表來說,限制更多,通用性較差,但是它的功能更加強大,可定制性也更強。 leetcode指路:實現(xiàn)Trie(前綴樹)
如圖可以查看trie樹的基本結(jié)構(gòu):
與二叉查找樹不同,鍵不是直接保存在節(jié)點中,而是由節(jié)點在樹中的位置決定。(這個是前綴樹的精髓,也是難理解的地方,他不用存儲某個節(jié)點的實際字符,他的對應下標映射出了需要存儲的字符!)
一個節(jié)點的所有子孫都有相同的前綴,也就是這個節(jié)點對應的字符串,而根節(jié)點對應空字符串。
一般情況下,不是所有的節(jié)點都有對應的值(他們只是前綴),只有葉子節(jié)點和部分內(nèi)部節(jié)點所對應的鍵才有相關(guān)的值。
C++實現(xiàn)
核心思想
單鏈表:通過Node中封裝的Node* next來找下一個連著的節(jié)點;
二叉樹:通過Node中封裝的Node* left 和 Node* right來找左右孩子節(jié)點;
前綴樹?
因為維護了26個可能的Node*節(jié)點,所以跟上面一個道理,只是不能枚舉出來了,用了一個Node*arr[26]來維護,恰巧把這個數(shù)組的下標設(shè)計成了某個字符的種類,就可以達到利用邏輯下標存儲一個實際字符的作用了!
前綴樹插入示意圖
上圖中,每經(jīng)過一個節(jié)點,將該節(jié)點的pass
值加一,將末尾節(jié)點的end值加一。通過這種操作記錄所有經(jīng)過的數(shù)據(jù)記錄
前綴樹的插入是靈魂所在,搞懂了之后結(jié)構(gòu)就明白了,不管是查找還是刪除無非就是類似對鏈表的相關(guān)操作;
前綴樹的大致框架
假設(shè)只存小寫字符:
#include <iostream> #include <vector> #include <string> using namespace std; //26 個小寫英文字母 #define NUM 26 class Trie{ private: Trie* arr[NUM];//多叉樹(最大26個分支,因為26個小寫字母嘛) int end; //代表word完整單詞的個數(shù),0就是無此單詞,只是一個前綴;insert一個單詞的時候,這個單詞的end首次出現(xiàn)就置為1;之后重復插入就end++; int pass; //代表以此前綴為公共前綴的節(jié)點個數(shù),每次insert的時候會調(diào)整; public: Trie() { memset(arr,0,sizeof(arr));//每個新節(jié)點的映射數(shù)組內(nèi)容置nullptr end = 0; ncount = 0; //初始化時以該映射信息字符為前綴的個數(shù)為1(這個字符本身算的1) } //插入單詞 void Insert(string &x) { } //查找 完全匹配字符串x 的數(shù)量 int Find(string &x) { } //查找 前綴為字符串x 的數(shù)量 int FindContain(string& x) { } //刪除某個單詞(前綴) bool Erase(string &x) { } ~Trie() { //因為new了26個連續(xù)的tire*空間,不要某個節(jié)點,不要把它對應給下層準備的26個空間也delete掉 防止內(nèi)存泄漏 for (int i = 0; i < NUMBER; i++) { if (nexts[i]){ delete nexts[i]; } } } };
- 二叉樹,父節(jié)點之下包含兩個節(jié)點,分別為左右子節(jié)點,分別開辟空間,進行數(shù)據(jù)存儲。
- 前綴樹的結(jié)構(gòu)也是類似的,它的每個節(jié)點包含兩個部分: 值部分和指針部分。
- 它的存儲方式為:在一棵樹上,從根到子節(jié)點,分別存儲所有目標數(shù)據(jù)的每一個下標位置上的數(shù)據(jù)
- 值部分主要又包含兩個數(shù)據(jù): 路過該節(jié)點的數(shù)量為pass, 以該節(jié)點為結(jié)尾的數(shù)量為end。
- 指針部分主要包含它的所有子節(jié)點(比如26個小寫字母),記為arr
下面的實現(xiàn)給出了四個接口:
Insert
插入字符串,給前綴樹添加一組數(shù)據(jù)
其中
Insert
方法需要注意插入新單詞的過程中,路徑所有前綴的個數(shù)pass+1
Find
查找已存入的完整匹配的字符串個數(shù)FindContain
查找已存入的前綴匹配的字符串個數(shù)Erase
從前綴樹中擦除一個完整字符串
Erase
方法需要注意的是:
- 需Find先檢查字符串是否存在;
- pass == 1 時,代表其下沒有任何可能存在的字符子串,所以直接將這個節(jié)點delete刪除即可;
- pass不為1且存在這個字符串,我們把end有效字符串個數(shù)-1就行
- 移除節(jié)點時,需要提前寫好析構(gòu)函數(shù),將其節(jié)點開辟的26個Node*內(nèi)存全部釋放,以免出現(xiàn)內(nèi)存泄漏;
前綴樹插入字符串
另外,下面的功能代碼不過多解釋,代碼注釋自行理解,核心要點就是用數(shù)組下表映射的方式確定前往哪一條鏈表,之后的尋找和插入等操作都有點像鏈表的操作,搞個cur指針向后遍歷等;
//插入單詞 void Insert(const string &x) { int size = x.size(); Node* cur = root; cur->pass++;//不管insert啥,我們root空節(jié)點的pass相當于必須+1,最終這個root->pass可以代表一共insert了幾次=-= for (int i = 0; i<size; i++) { char index = x[i] - 'a'; //該字符在當前分支下的映射為空,沒有那就new if (cur->arr[index] == nullptr) { cur->arr[index] = new Node; } cur->arr[index]->pass++; //不管 cur->arr[index] 是new的還是本來就有,insert要路過他了,他的pass+1, cur = cur->arr[index];//同時cur下指過去,進行下一個字符的insert } cur->end++;//insert最終將完整字符串個數(shù)end+1 }
前綴樹查找完整的字符串
//查找 完全匹配字符串 x 的數(shù)量 -->end int Find(const string &x) { int size = x.size(); Node* cur = root; for (int i = 0; i < size; i++) { char index = x[i] - 'a'; //搜索到某個字符斷了,沒有這個完整的字符串x 返回0 if (cur->arr[index] == nullptr) return 0; //沒斷,繼續(xù)向下一個字符搜索; cur = cur->arr[index]; } return cur -> end;//返回完整字符串x的有效個數(shù)end }
前綴樹查找前綴匹配的字符串
//查找 前綴為字符串 x 的數(shù)量 -->pass int FindContain(const string& x) { //與Find一模一樣的邏輯,只是最后的return 變了,這體現(xiàn)了Node*封裝 int end 和int pass的好處了吧 int size = x.size(); Node* cur = root; for (int i = 0; i < size; i++) { char index = x[i] - 'a'; if (cur->arr[index] == nullptr) return 0; cur = cur->arr[index]; } return cur -> pass; }
前綴樹刪除完整字符串
//刪掉某個完整單詞-以及這個單詞后面可能存在的所有路徑;(end>1 出現(xiàn)了很多次時,只需要end--一下) bool Delete(const string &x) { if (Find(x) == 0) return false;//壓根沒這個單詞,刪除失敗; //有這個單詞,我們需要找到他的prev前一個,delete掉他,prev的arr[x]=nullptr! Node* cur = root; Node* prev = root; int size = x.size(); for (int i = 0; i < size; i++) { char index = x[i]-'a'; //if (cur->arr[index] == nullptr) return false;這句不需要,都過了Find 肯定x每個字符都存在于字典樹中 cur->pass--;//別忘了路過的路徑都得-1; prev = cur; cur = cur->arr[index]; } if (cur->end==1) {//代表x所在字符串的個數(shù)只有1,直接遞歸delete刪掉它 和 他后面的子串 delete cur;//這個delete調(diào)析構(gòu),我們析構(gòu)已經(jīng)寫好了,防止內(nèi)存泄漏; prev->arr[x[size - 1]-'a'] = nullptr; // prev的arr[x最后一個字符-'a'] = nullptr! } else cur->end--;//end>1 :end--代表這個節(jié)點的有效字符串個數(shù)-1,end==1 end-- == 0,這個節(jié)點的字符有效個數(shù)為0了,但是他因為pass>1,暫時保存 后面的不刪; //end>1,那就end有效個數(shù)-1就行了; return true; }
總結(jié)
- 這個字典樹的樹結(jié)構(gòu)可以根據(jù)需求來進行多樣式的處理;比如我為了實現(xiàn)設(shè)計的功能,每個節(jié)點都保存了pass和end倆int方便功能記錄和函數(shù)內(nèi)的使用;
- 字典樹本質(zhì)上是犧牲空間,換查找同前綴的字符串提升時間效率的一種措施,但是我們這種每個節(jié)點都開26個數(shù)組的方式是非常浪費空間的,比如只有一個有效字符下標,其他25個nullptr都浪費了,而且在大量相同的前綴下就是單鏈表,浪費更嚴重。
- 這時候我們可以把Node*arr[26]數(shù)組換成map<char,Node*>這樣搞(每層某一個char只會出現(xiàn)一次,所以char做key沒問題),需要配對啥就insert給紅黑樹中添加啥,大大節(jié)省空間;
所以說這個樹沒有啥固定玩法,可塑性太強了…這可能也是不刷題的我不常見的愿因?
完整代碼
#include <iostream> #include <vector> #include <string> using namespace std; //26 個小寫英文字母 #define NUM 26 //前綴樹節(jié)點 class Node { public: Node* arr[NUM];//多叉樹(最大26個分支,因為26個小寫字母嘛) int end; //代表 int pass; //代表以此前綴為公共前綴的節(jié)點個數(shù),每次insert的時候會調(diào)整 Node() { end = 0; pass = 0; memset(arr, 0, sizeof(arr)); } ~Node() { //這里有點遞歸的意思,除了刪除當前節(jié)點,更重要的是如果當前節(jié)點的子節(jié)點還有非空。遞歸delete掉! for (int i = 0; i < NUM; i++) { if (arr[i]!=nullptr) delete arr[i]; } } }; //前綴樹主體 class Trie{ public: Node* root = nullptr; public: Trie() { root = new Node; } //插入單詞 void Insert(const string &x) { int size = x.size(); Node* cur = root; cur->pass++;//不管insert啥,我們root空節(jié)點的pass相當于必須+1,最終這個root->pass可以代表一共insert了幾次=-= for (int i = 0; i<size; i++) { char index = x[i] - 'a'; //該字符在當前分支下的映射為空,沒有那就new if (cur->arr[index] == nullptr) { cur->arr[index] = new Node; } cur->arr[index]->pass++; //不管 cur->arr[index] 是new的還是本來就有,insert要路過他了,他的pass+1, cur = cur->arr[index];//同時cur下指過去,進行下一個字符的insert } cur->end++;//insert最終將完整字符串個數(shù)end+1 } //查找 完全匹配字符串 x 的數(shù)量 -->end int Find(const string &x) { int size = x.size(); Node* cur = root; for (int i = 0; i < size; i++) { char index = x[i] - 'a'; //搜索到某個字符斷了,沒有這個完整的字符串x 返回0 if (cur->arr[index] == nullptr) return 0; //沒斷,繼續(xù)向下一個字符搜索; cur = cur->arr[index]; } return cur -> end;//返回完整字符串x的有效個數(shù)end } //查找 前綴為字符串 x 的數(shù)量 -->pass int FindContain(const string& x) { //與Find一模一樣的邏輯,只是最后的return 變了,這體現(xiàn)了Node*封裝 int end 和int pass的好處了吧 int size = x.size(); Node* cur = root; for (int i = 0; i < size; i++) { char index = x[i] - 'a'; if (cur->arr[index] == nullptr) return 0; cur = cur->arr[index]; } return cur -> pass; } //刪掉某個完整單詞-以及這個單詞后面可能存在的所有路徑;(end>1 出現(xiàn)了很多次時,只需要end--一下) bool Delete(const string &x) { if (Find(x) == 0) return false;//壓根沒這個單詞,刪除失敗; //有這個單詞,我們需要找到他的prev前一個,delete掉他,prev的arr[x]=nullptr! Node* cur = root; Node* prev = root; int size = x.size(); for (int i = 0; i < size; i++) { char index = x[i]-'a'; //if (cur->arr[index] == nullptr) return false;這句不需要,都過了Find 肯定x每個字符都存在于字典樹中 cur->pass--;//別忘了路過的路徑都得-1; prev = cur; cur = cur->arr[index]; } if (cur->end==1) {//代表x所在字符串的個數(shù)只有1,直接遞歸delete刪掉它 和 他后面的子串 delete cur;//這個delete調(diào)析構(gòu),我們析構(gòu)已經(jīng)寫好了,防止內(nèi)存泄漏; prev->arr[x[size - 1]-'a'] = nullptr; // prev的arr[x最后一個字符-'a'] = nullptr! } else cur->end--;//end>1 :end--代表這個節(jié)點的有效字符串個數(shù)-1,end==1 end-- == 0,這個節(jié)點的字符有效個數(shù)為0了,但是他因為pass>1,暫時保存 后面的不刪; //end>1,那就end有效個數(shù)-1就行了; return true; } };
到此這篇關(guān)于C++前綴樹字典樹的學習與模擬實現(xiàn)代碼示例的文章就介紹到這了,更多相關(guān)C++前綴樹字典樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Linux下實現(xiàn)C++操作Mysql數(shù)據(jù)庫
由于工作需要抽出一周的時間來研究C/C++訪問各種數(shù)據(jù)庫的方法,并打算封裝一套數(shù)據(jù)庫操作類,現(xiàn)在奉上最簡單的一部分:在Linux下訪問MySQL數(shù)據(jù)庫。2017-05-05詳解C++如何實現(xiàn)在Word文檔中創(chuàng)建列表
這篇文章主要為大家詳細介紹了介紹如何使用C++在Word文檔中創(chuàng)建編號列表、項目符號列表和多級列表,感興趣的小伙伴可以跟隨小編一起學習一下2023-05-05C語言 數(shù)據(jù)結(jié)構(gòu)與算法之字符串詳解
這篇文章將帶大家深入了解C語言數(shù)據(jù)結(jié)構(gòu)與算法中的字符串,文中主要是介紹了字符串的定義、字符串的比較以及一些串的抽象數(shù)據(jù)類型,感興趣的可以學習一下2022-01-01