数据结构之Tire树

我就是我 2022-05-25 05:16 105阅读 0赞

### 1.0 简介 ###

也叫字典树

又称单词查找树 是一种树形结构，是一种哈希树的变种。

典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），

所以经常被搜索引擎系统用于文本词频统计。

它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

![这里写图片描述][z200777202049.jpg]

### 2.0 字典树具有如下性质： ###

1.  根节点不包含字符，除根节点外每一个节点都只包含一个字符。
2.  从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
3.  每个节点的所有子节点包含的字符都不相同。

### 3.0 节点结构 ###

一般来说MAX是26 因为26个英文字母呗

next是表示每层有多少种类的数，如果只是小写字母，则26即可，若改为大小写字母，则是52，若再加上数字，

则是62了，这里根 据题意来确定。

typedef struct TrieNode                     //Trie结点声明 
    {   
        bool isStr;                            //标记该结点处是否构成单词 
        int data;
        struct TrieNode *next[MAX];            //儿子分支 
    }Trie;

### 4.0 字典树的操作 ###

查找、插入和删除 删除比较少见

#### 4.1 创建 ####

1.  考察字符串的第一个字母
2.  顺着字典树的相应路径走 例如是a则走第一条路径 c就第三条这样的 可以利用 \*p-‘a’ 获取这个字符位于第几个子节点
3.  如果没有就创建

每个字典树的用法和定义均是根据自己情况定义 懂这个思想就行了 不用太拘泥于我这个

#### 4.2 查找 ####

查找就是按前缀一个个查，查到了就接着查、。。  
每次从根结点开始进行搜索；

1.  取要查找关键词的第一个字母，并根据该字母选择对应的子树并转到该子树继续进行检索；
2.  在相应的子树上，取得要查找关键词的第二个字母,并进一步选择对应的子树进行检索；　
3.  迭代上面的过程
4.  直到在某个结点处  
    
    
    1.  如果最后有个字母查到，则返回这个节点的信息
    2.  如果最后这个节点没有任何信息 则返回查询失败

#### 4.3 删除 ####

有些题目，数据比较大，需要查询完之后释放内存

删除算法 采用递归算法

void del(node *root){  
        for(int i = 0; i <MAX; ++i)  
            if(root->next[i] != NULL)  
                del(root->next[i]);  
        delete(root);  
    }

[z200777202049.jpg]: /images/20220525/555c61f6e368493db50add01d92a86fa.png

发表评论取消回复

表情：

评论列表（有 0 条评论，105人围观）

还没有评论，来说两句吧...

相关阅读

相关数据结构之树

1. 树参考链接： [短篇知识点（一）：节点与结点的区别\_汤姆和佩琦的博客-CSDN博客\_树的节点还是结点][-CSDN] [数据结构之树\_lzb\

喜欢ヅ旅行/ 2023年10月09日 14:52/ 0 赞/ 70 阅读

相关数据结构之-树

二叉树：平衡二叉树 B树 B+树红黑树的特点：红黑树是一种自平衡的二叉查找树，除了符合二叉查找树的基本特征外，它还具有下列的附加特征。

女爷i/ 2023年01月16日 06:28/ 0 赞/ 252 阅读

相关 python 树数据结构_python数据结构之树

\这个类是用于定义树的基本结构，leftjd：左节点，rightjd：右节点，data：数据 class Tree(): def \_\_init\_\_(self,lef

我不是女神ヾ/ 2022年10月27日 13:43/ 0 赞/ 269 阅读

相关数据结构之---树

作者：egg 邮箱：xtfggef@gmail.com 微博：[http://weibo.com/xtfggef][http_weibo.com_xtfggef] 博客：

秒速五厘米/ 2022年09月23日 08:10/ 0 赞/ 223 阅读

相关数据结构之树

一、树的基本概念树（Tree）是元素的集合，树有多个节点可以存储元素二、二叉树每个节点最多有两个子节点的树称为二叉树；常用来做二分查找（Binary Search）

阳光穿透心脏的1/2处/ 2022年08月19日 04:48/ 0 赞/ 233 阅读

相关数据结构之树

一、树的基本定义：树(tree)是N(N>=0)个结点的有限集合。在任意的一棵树中<1>有且只有一个特定的根(root)节点 ;<2>当n》1时其余节点可分为m个互不相交的有限

深藏阁楼爱情的钟/ 2022年08月06日 00:28/ 0 赞/ 227 阅读

相关数据结构之树

树相关的概念 > 对于大量的输入数据，链表的线性访问时间太长了，不宜使用，那么就需要一种多分支的访问情况，这个就是树。通过在节点里面增加链接个数，减少访问次数。树是各种算

「爱情、让人受尽委屈。」/ 2022年05月30日 04:44/ 0 赞/ 303 阅读

相关数据结构之B+树

1.0 简介 B+ 树是一种树数据结构， 1. B+树是B树的一种变体 2. 所有信息都存储在终端结点中 3. 每一个关键码对应一个子树 4. 内部节点的值是记

痛定思痛。/ 2022年05月25日 05:17/ 0 赞/ 215 阅读

相关数据结构之Tire树

1.0 简介也叫字典树又称单词查找树是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎

我就是我/ 2022年05月25日 05:16/ 0 赞/ 106 阅读

相关数据结构之树

树的定义树：树是n个结点的有限集。n=O 时称为空树. 在任意一棵非空树中: ( 1 ) 有旦仅有一个特定的称为根的结点: ( 2 ) 当n > 1 时，其余结

怼烎@/ 2022年05月19日 06:27/ 0 赞/ 277 阅读