字典樹 Trie

今天完成了字典樹 Trie的模板，可以在O(N) (N=字串長度)的時間搜尋一個字串
插入的時間亦是O(N)，在字串匹配上有很大的幫助(AC字動機)，但是因為每個節點都要記錄所有字元，是非常耗空間的
通常將根節點設為"沒有字元"，若是想進一步了解Trie請自行google吧!
以下為模板:

	#ifndef TRIE
	#define TRIE
	template<typename T,char L='A',char R='z'>
	class trie{
	private:
	struct node{
	node *tr[R-L+1],*pa;
	T data;
	int ref;
	bool is;
	node():ref(0),is(0){
	for(int i=0;i<=R-L;i++)tr[i]=NULL;
	}
	~node(){
	for(int i=0;i<=R-L;i++){
	if(tr[i])delete tr[i];
	}
	}
	}root;
	int _size;
	public:
	class point_iterator{
	friend trie;
	private:
	node *p;
	public:
	point_iterator(){p=NULL;}
	inline operator bool (){return p?1:0;}
	inline T &operator *(){return p->data;}
	inline void operator =(T d){p->data=d;}
	};
	inline void clear(){
	for(int i=0;i<=R-L;i++)if(root.tr[i]){
	delete root.tr[i],root.tr[i]=NULL;
	}
	}
	trie(){root.ref=0;clear();_size=0;}
	~trie(){clear();}
	inline int size(){return _size;}
	inline point_iterator find(const char *s){
	point_iterator it;
	node *now=&root;
	for(int i=0;s[i];i++){
	if(!now->tr[s[i]-L])return it;
	now=now->tr[s[i]-L];
	}
	if(now->is)it.p=now;
	return it;
	}
	inline point_iterator insert(const char *s,T data){
	point_iterator it=find(s);
	if(it){it=data;return it;}
	node *now=&root;
	_size++;
	for(int i=0;s[i];i++){
	if(!now->tr[s[i]-L]){
	now->tr[s[i]-L]=new node;
	now->tr[s[i]-L]->pa=now;
	}
	now=now->tr[s[i]-L],now->ref++;
	}
	now->data=data;now->is=1;
	it.p=now;
	return it;
	}
	inline T &operator[](const char *s){
	point_iterator it=find(s);
	if(!it)it=insert(s,T());
	return it.p->data;
	}
	inline bool erase(const char *s){
	if(!find(s))return 0;
	node *now=&root;_size--;
	for(int i=0;s[i];i++){
	if(i&&!now->ref){
	now->pa->tr[s[i-1]-L]=NULL;
	delete now;return 1;
	}
	now=now->tr[s[i]-L],now->ref--;
	}
	now->is=0;
	return 1;
	}
	};
	#endif

view raw trie.cpp hosted with ❤ by GitHub

跟stl map的用法類似
trie<int >t;  //定義一個存int的Trie
trie<int ,'a','z'>t  //定義一個字元範圍是'a'到'z'的Trie(預設是'A'~'z')
trie<int >::point_iterator it;  //定義一個節點迭代器
t.insert("asd",1);  //插入1到"asd"的位置(若原來已有值則覆蓋)，傳回插入節點的point_iterator
t.find("asd");  //傳回"asd"位置的point_iterator，若無資料point_iterator為NULL，請注意
t["asf"];  //若"asd"存在資料，傳回其引用位置，若不存在則插入並傳回其引用位置
t.erase("asd");  //刪除"asd"節點，若成功刪除則傳回true，失敗(無結點)則傳回false
t.size(); //傳回字串的總數
t.clear();  //清空trie