【数据结构】字典树小结

1.tree 树定义:

又叫:字典树,前缀树,单词查找树,键树。

是一种有序的多叉树。用于保存关联数组,

image-20210330185343212

2.tree 树性质:

  1. 根节点规定为空字符串,非根节点至少包含一个字符

  2. 从根节点到某一个节点,路径上经过的字符连接起来,组成的字符串为这个节点所对应的字符串

  3. 每个节点的所有子节点包含的字符互不相同


通常在构造 tree 树时,会在节点上设置一个标志,表明该节点代表的字符串是否构成单词(或 ”关键字“)。


3.tree 树优缺点:

字典树这种数据结构的设计思想很简单,就是用空间换时间,提高字符串查找效率。

优点:
  1. 插入合查询效率都是 O(n),n 为字符串长度

  2. 对比 hash,虽然理想状态hash 的查找效率是 O(1) ,但这取决于 hash 函数好坏,如果冲突多,则效率不一定比字典树高

  3. 不同的关键字在树中一定不会冲突

  4. 字典树只有在允许一个节点关联多个值的情况下,才有类似hash 碰撞的情况产生

  5. trie 树不用求 hash 值,对短字符串效果极佳。

  6. 可以进行字符串排序(按字典序)

缺点:

  1. 空间成本较高

  2. 当 hash 函数较好时,查询效率 hash 表更高

4.应用:

1、字符串检索

检索/查询功能是Trie树最原始的功能。思路就是从根节点开始一个一个字符进行比较:

  • 如果沿路比较,发现不同的字符,则表示该字符串在集合中不存在。

  • 如果所有的字符全部比较完并且全部相同,还需判断最后一个节点的标志位(标记该节点是否代表一个关键字)。

struct trie_node
{
   bool isKey;   // 标记该节点是否代表一个关键字
   trie_node *children[26]; // 各个子节点
};


2、词频统计

Trie树常被搜索引擎系统用于文本词频统计 。

struct trie_node
{
   int count;   // 记录该节点代表的单词的个数
   trie_node *children[26]; // 各个子节点
};

思路:为了实现词频统计,我们修改了节点结构,用一个整型变量count来计数。对每一个关键字执行插入操作,若已存在,计数加1,若不存在,插入后count置1。

注意:第一、第二种应用也都可以用 hash table 来做。

3、字符串排序

Trie树可以对大量字符串按字典序进行排序,思路也很简单:遍历一次所有关键字,将它们全部插入trie树,树的每个结点的所有儿子很显然地按照字母表排序,然后先序遍历输出Trie树中所有关键字即可。

4、前缀匹配

例如:找出一个字符串集合中所有以ab开头的字符串。我们只需要用所有字符串构造一个trie树,然后输出以a->b->开头的路径上的关键字即可。

trie树前缀匹配常用于搜索提示。如当输入一个网址,可以自动搜索出可能的选择。当没有完全匹配的搜索结果,可以返回前缀最相似的可能。

5、作为其他数据结构和算法的辅助结构

如后缀树,AC自动机等。


5. demo:

//
// Created by admin on 2021/3/30.
//

#include<iostream>
#include<string>

using namespace std;

#define ALPHABET_SIZE 26

typedef struct trie_node
{
    int count;  // 记录该节点代表单词的个数
    trie_node *children[ALPHABET_SIZE]; // 各个子节点
}*trie;

trie_node* create_trie_node()
{
    trie_node* pNode = new trie_node();
    pNode->count = 0;
    for(int i = 0; i < ALPHABET_SIZE; i++) {
        pNode->children[i] = NULL;
    }
    return pNode;
}

void trie_insert(trie root, char* key)
{
    trie_node* node = root;
    char* p = key;
    while(*p) {
        if (node->children[*p - 'a'] == NULL) {
            node->children[*p - 'a'] = create_trie_node();
        }
        node = node->children[*p - 'a'];
        p++;
    }
    node->count += 1;
}

// 查询:不存在返回0,存在返回出现的次数
int trie_search(trie root, char* key)
{
    trie_node* node = root;
    char* p = key;
    while(*p && node != NULL) {
        node = node->children[*p - 'a'];
        p++;
    }
    if (node == NULL) {
        return 0;
    } else {
        return node->count;
    }
}

int main() {
    char keys[][8] = {"the", "a", "there", "answer", "any", "by", "bye", "their"};
    trie root = create_trie_node();

    for(int i = 0; i < 8; i++) {
        trie_insert(root, keys[i]);
    }

    char s[][32] = {"Present in trie", "Not present in trie"};
    printf("%s occurrence times: %d\n", "the", trie_search(root, "the"));
    printf("%s occurrence times: %d\n", "these", trie_search(root, "these"));
    printf("%s occurrence times: %d\n", "their", trie_search(root, "the"));
    printf("%s occurrence times: %d\n", "thaw", trie_search(root, "thaw"));

    return 0;
}


发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

«   2021年5月   »
12
3456789
10111213141516
17181920212223
24252627282930
31
控制面板
您好,欢迎到访网站!
  查看权限
网站分类
搜索
最新留言
文章归档
网站收藏
友情链接

    Powered By Z-BlogPHP 1.5.2 Zero

    Copyright liuyang1.com. 转载文章,请注明出处。谢谢!