第一次接触trie树,翻了一些算法树竟然没有找到。于是在google上各种查找,现在对自己所了解的trie总结一下,以便将来复习,并给出简单的实现。
Trie,又称字典树、单词查找树,是一种树形结构,用于保存大量的字符串。它的优点是:利用字符串的公共前缀来节约存储空间。
相对来说,Trie树是一种比较简单的数据结构.理解起来比较简单,正所谓简单的东西也得付出代价.故Trie树也有它的缺点,Trie树的内存消耗非常大.当然,或许用左儿子右兄弟的方法建树的话,可能会好点.
其基本性质可以归纳为:
1. 根节点不包含字符,除根节点外每一个节点都只包含一个字符。
2. 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。
3. 每个节点的所有子节点包含的字符都不相同。
其基本操作有:查找 插入和删除,当然删除操作比较少见.我在这里只是实现了对整个树的删除操作,至于单个word的删除操作也很简单.
搜索字典项目的方法为:
(1) 从根结点开始一次搜索;
(2) 取得要查找关键词的第一个字母,并根据该字母选择对应的子树并转到该子树继续进行检索;
并进一步选择对应的子树进行检索。
附在该结点上的信息,即完成查找。
其他操作类似处理.
实现代码:
if(search(s)!=NULL)
return;
int l = strlen(s);
for(int i=0;i<l;i++)
{
if(p->next[s[i]-'a']==NULL)
p->next[s[i]-'a']= new TreeNode;
else
p->next[s[i]-'a']->num++;
p=p->next[s[i]-'a'];
}
p->term=true;//设置刚插入字符串的最后一个字符节点终止标志
}
void del_tree(TreeNode * node)//删除以node为根的trie树
{
if(node == NULL)
return;
else
{
for(int i=0;i<26;i++)
if(node->next[i]!=NULL)
del_tree(node->next[i]);
delete node;
node=NULL;
}
}
void del(char *s,TreeNode * root)//删除以root为根中的字符串s
{
TreeNode *p;
p = root;
int i =0;
int l = strlen(s);
if(p==NULL)
return;
for(i=0;i<l;i++)
{
if(p->next[s[i]-'a']==NULL)//not exist
return;
else
{
if(p->next[s[i]-'a']->num >1)
{
if(i==l-1)//aaa aaaaa情况
{
p->next[s[0]-'a']->num--;
p->next[s[0]-'a']->term = false;
break;
}
p=p->next[s[i]-'a'];
}
else//num=1,说明以“到目前为止的字符串”为前缀的字符串只有s,删除s的剩余节点
{
TreeNode *tmp = p->next[s[i]-'a'];
p->next[s[i]-'a']=NULL;
del_tree(tmp);
break;
}
}
}
}
int main()
{
root = new TreeNode;
char s1[100] ="abc";
char s2[100] ="cde";
char s3[100] ="acd";
char s4[100] ="aaa";
char s5[100] ="aaa";
char s6[100] ="asdaa";
char s7[100] ="sdqwerqwe";
char s8[100] ="aaaaaa";
insert(s1);
insert(s2);
insert(s3);
insert(s4);
insert(s5);
insert(s6);
insert(s7);
insert(s8);
del(s3,root);
del(s4,root);
del(s6,root);
if(search(s1)!=NULL)
cout<<s1<<endl;
if(search(s2)!=NULL)
cout<<s2<<endl;
if(search(s3)!=NULL)
cout<<s3<<endl;
if(search(s4)!=NULL)
cout<<s4<<endl;
if(search(s5)!=NULL)
cout<<s5<<endl;
if(search(s6)!=NULL)
cout<<s6<<endl;
if(search(s7)!=NULL)
cout<<s7<<endl;
if(search(s8)!=NULL)
cout<<s8<<endl;
}