Trie树的C++实现

［来源］达内［编辑］达内［时间］2012-09-08

Trie，又称单词查找树、前缀树，是一种哈希树的变种。应用于字符串的统计与排序，经常被搜索引擎系统用于文本词频统计。

Trie—单词查找树

< p style="margin: 5px auto; padding: 0px; text-indent: 0px; line-height: 19px; color: rgb(0, 0, 0); font-size: 13px; font-family: verdana, 'ms song', 宋体, Arial, 微软雅黑, Helvetica, sans-serif; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: left; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; background-color: rgb(254, 254, 242); "> Trie，又称单词查找树、前缀树，是一种哈希树的变种。应用于字符串的统计与排序，经常被搜索引擎系统用于文本词频统计。

< p style="margin: 5px auto; padding: 0px; text-indent: 0px; line-height: 19px; color: rgb(0, 0, 0); font-size: 13px; font-family: verdana, 'ms song', 宋体, Arial, 微软雅黑, Helvetica, sans-serif; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: left; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; background-color: rgb(254, 254, 242); ">性质：
1.根节点不包含字符，除根节点外的每一个节点都只包含一个字符。
2.从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
3.每个节点的所有子节点包含的字符都不相同。

< p style="margin: 5px auto; padding: 0px; text-indent: 0px; line-height: 19px; color: rgb(0, 0, 0); font-size: 13px; font-family: verdana, 'ms song', 宋体, Arial, 微软雅黑, Helvetica, sans-serif; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: left; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; background-color: rgb(254, 254, 242); ">优点：
1.查询快。对于长度为m的键值，最坏情况下只需花费O(m)的时间；而BST需要O(m log n)的时间。
2.当存储大量字符串时，Trie耗费的空间较少。因为键值并非显式存储的，而是与其他键值共享子串。

< p style="margin: 5px auto; padding: 0px; text-indent: 0px; line-height: 19px; color: rgb(0, 0, 0); font-size: 13px; font-family: verdana, 'ms song', 宋体, Arial, 微软雅黑, Helvetica, sans-serif; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: left; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; background-color: rgb(254, 254, 242); ">2.插入字符串
1).设置当前节点为根节点，设置当前字符为插入字符串中的首个字符；
2).在当前节点的子节点上搜索当前字符，若存在，则将当前节点设为值为当前字符的子节点；否则新建一个值为当前字符的子节点，并将当前结点设置为新创建的节点。
3).将当前字符设置为串中的下个字符，若当前字符为0，则结束；否则转2.

< p style="margin: 5px auto; padding: 0px; text-indent: 0px; line-height: 19px; color: rgb(0, 0, 0); font-size: 13px; font-family: verdana, 'ms song', 宋体, Arial, 微软雅黑, Helvetica, sans-serif; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: left; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; background-color: rgb(254, 254, 242); ">3.查找字符串
搜索过程与插入操作类似，当字符找不到匹配时返回假；若全部字符都存在匹配，判断最终停留的节点是否为树叶，若是，则返回真，否则返回假。

< p style="margin: 5px auto; padding: 0px; text-indent: 0px; line-height: 19px; color: rgb(0, 0, 0); font-size: 13px; font-family: verdana, 'ms song', 宋体, Arial, 微软雅黑, Helvetica, sans-serif; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: left; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; background-color: rgb(254, 254, 242); ">4.删除字符串
首先查找该字符串，边查询边将经过的节点压栈，若找不到，则返回假；否则依次判断栈顶节点是否为树叶，若是则删除该节点，否则返回真。

< div style="margin: 5px 0px; padding: 5px; background-color: rgb(245, 245, 245); font-family: 'Courier New'; font-size: 12px; border: 1px solid rgb(204, 204, 204); overflow: auto; color: rgb(0, 0, 0); font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: left; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; " class="cnblogs_code">

#include <iostream>
using namespace
 std;  /*
 trie的节点类型 */
 template <int
 Size> //
Size为字符表的大小struct
 trie_node  {     

bool terminable; //
当前节点是否可以作为字符串的结尾

    int node; //
子节点的个数

    trie_node *child[Size]; //
指向子节点指针    /*
 构造函数 

*/     trie_node() : terminable(
false), node(0
) { memset(child, 0, sizeof
(child)); } };  /*
 trie */
 template <int
 Size, typename Index> //
Size为字符表的大小，Index为字符表的哈希函数class
 trie  { 

public:     
/* 定义类型别名 
*/     typedef trie_node
<Size> node_type;     typedef trie_node
<Size>* link_type;      

/* 构造函数 
*/     trie(Index i 
= Index()) : index(i){ }      /*
 析构函数 */

    ~trie() { clear(); }      /*
 清空 */

    void
 clear()      {         clear_node(root);         for
 (

int i = 0; i < Size; ++
i)             root.child[i] = 0


;     }      /*
 插入字符串 */
     template 

<typename Ite
rator>
    void
 insert(Iterator begin, Iterator end)      {         link_type cur = &root; //
当前节点设置为根节点

        for (; begin != end; ++
begin)          {             if
 (!cur->child[index[*begin]]) //
若当前字符找不到匹配，则新建节点            {                 cur
->child[index[*begin]] = new
 node_type;                 

++cur->node; //
当前节点的子节点数加一            }             cur 
= cur->child[index[*begin]]; //
将当前节点设置为当前字符对应的子节点        }         cur
->terminable = 

true; //
设置存放最后一个字符的节点的可终止标志为真

    }      /*
 插入字符串，针对C风格字符串的重载版本 
*/

    void insert(const
 char *
str)     {         insert(str, str + strlen(str));      }      
/*

 查找字符串，算法和插入类似 
*/     template 
<typename Iterator>
    bool
 find(Iterator begin, Iterator end)      {         link_type cur = &root;         
for (; begin != end; ++
begin)          {             

if (!cur->child[index[*
begin]])                  

return false
;             cur = cur->child[index[*

begin]];         }         

return cur->
terminable;     }      

/*
 查找字符串，针对C风格字符串的重载版本 

*/

    bool find(const
 char *str)      {         
return find(str, str +
 strlen(str));      }      /*
 删除字符串 

*/     template 
<typename Iterator>
    bool
 erase(Iterator begin, Iterator end)      {         bool
 result; //
用于存放搜索结果        erase_node(begin, end, root, result);         
return result;     }      
/*
 删除字符串，针对C风格字符串的重载版本 

*/

    bool erase(char
 *str)      {             return
 erase(str, str + strlen(str));      }      


/* 按字典序遍历单词树 


*/     template 
<typename Functor>
    void
 traverse(Functor &execute = Functor())      {         visit_node(root, execute);     }  
private

:     /*
 访问某结点及其子结点 
*/

     template 
<typename Functor>
    void
 visit_node(node_type cur, Functor &execute)      {         execute(cur);         
for

 (int i = 0
; i < Size; ++i)          {             
if

 (cur.child[i] == 0) 
continue

;             visit_node(*
cur.child[i], execute);         }     }     

/*
 清除某个节点的所有子节点 

*/

    void
 clear_node(node_type cur)      {         for
 (int

 i = 0; i < Size; ++
i)          {             if
 (cur.child[i] == 

0) continue
;             clear_node(*cur.child[i]);             delete cur.child[i];             cur.child[i] 
= 0;             
if (--cur.node == 0
) break;         }     }      
/*
 边搜索边删除冗余节点，返回值用于向其父节点声明是否该删除该节点 

*/     template 
<typename Iterator>
    bool
 erase_node(Iterator begin, Iterator end, node_type &cur, bool
 &result)      {         

if (begin == end) //
当到达字符串结尾：递归的终止条件

        {              result 
= cur.terminable; //
如果当前节点可以作为终止字符，那么结果为真            cur.terminable = false
;  

//设置该节点为不可作为终止字符，即删除该字符串

            return cur.node == 
0;    //
若该节点为树叶，那么通知其父节点删除它

        }         //
当无法匹配当前字符时，将结果设为假并返回假，即通知其父节点不要删除它

        if
 (cur.child[index[*begin]] == 0) 
return result = 

false;          //
判断是否应该删除该子节点

        else if
 (erase_node((++begin)--, end, *(cur.child[index[*begin]]), result))          {              delete cur.child[index[
*begin]]; //删除该子节点

            cur.child[index[*begin]] = 0
; //
子节点数减一             

//
若当前节点为树叶，那么通知其父节点删除它            if
 (--cur.node == 

0 && cur.terminable == false
) return true


;          }         return 
false

; //其他情况都返回假

    }      /*
 根节点 */
     node_type root;      /*
 将字符转换为索引的转换表或函数对象 
*/

     Index index; };  //
index function object

class IndexClass {   
public:     
int operator
[](const char
 key)       {           return
 key % 26;       } };  
int main() {     trie
<26,IndexClass>
 t;     t.insert(

"tree
");     t.insert(
"tea


");     t.insert(
"A"
);     t.insert("
ABC"
);      if
(t.find("tree
"))         cout
<<"find tree
"<<endl;     
else         cout
<<"not find tree


"<<endl;      
if

(t.find("tre
"))         cout
<<"find tre
"<<endl;     
else         cout
<<"not find tre
"<<endl;          
if(t.erase("
tree"
))         cout<<"
delete tree"
<<endl;     else
         cout<<"
not find tree"
<<

endl;      if(t.find(
"tree"
))         cout<<"
find tree"
<<endl;     else
         cout<<"
not find tree"
<<endl;      return
 0; }

顶

踩

上一篇：指向const对象的指针和const指针
下一篇：获取Sprite的实际Rect

Trie树的C++实现

资源下载

2002-2014 达内科技有限公司版权所有京ICP备08000853号

Trie树的C++实现

资源下载

2002-2014 达内科技有限公司 版权所有 京ICP备08000853号

2002-2014 达内科技有限公司版权所有京ICP备08000853号