最近在公司实习了两个月,做的是大数据,感触挺深的,我做的是底层数据抽取模块,算法真的很重要,我是用trie书,Trie树也称字典树,因为其效率很高,所以在在字符串查找、前缀匹配等中应用很广泛,其高效率是以空间为代价的。
Trie树的操作
在Trie树中主要有3个操作,插入、查找和删除。一般情况下Trie树中很少存在删除单独某个结点的情况,因此只考虑删除整棵树。
1.插入
假设存在字符串str,Trie树的根结点为root。i=0,p=root。
1)取str[i],判断p->next[str[i]-97]是否为空,若为空,则建立结点temp,并将p->next[str[i]-97]指向temp,然后p指向temp;
若不为空,则p=p->next[str[i]-97];
2)i++,继续取str[i],循环1)中的操作,直到遇到结束符'\0',此时将当前结点p中的isStr置为true。
2.查找
假设要查找的字符串为str,Trie树的根结点为root,i=0,p=root
1)取str[i],判断判断p->next[str[i]-97]是否为空,若为空,则返回false;若不为空,则p=p->next[str[i]-97],继续取字符。
2)重复1)中的操作直到遇到结束符'\0',若当前结点p不为空并且isStr为true,则返回true,否则返回false。
3.删除
删除可以以递归的形式进行删除。
感觉算法太重要了 |