Next Topic

字典树(trie)

数据结构与算法第四章树(tree) 字典树(trie)

一、字典树的概念

字典树，顾名思义，是关于“字典”的一棵树。即：它是对于字典的一种存储方式（所以是一种数据结构而不是算法）。这个词典中的每个“单词”就是从根节点出发一直到某一个目标节点的路径，路径中每条边的字母连起来就是一个单词。

二、字典树的功能

根据字典树的概念，我们可以发现：字典树的本质是把很多字符串拆成单个字符的形式，以树的方式存储起来。所以我们说字典树维护的是”字典“。那么根据这个最基本的性质，我们可以由此延伸出字典树的很多妙用。简单总结起来大体如下：

1、维护字符串集合（即字典）。
2、向字符串集合中插入字符串（即建树）。
3、查询字符串集合中是否有某个字符串（即查询）。
4、统计字符串在集合中出现的个数（即统计）。
5、将字符串集合按字典序排序（即字典序排序）。
6、求集合内两个字符串的LCP（Longest Common Prefix，最长公共前缀）（即求最长公共前缀）。

三、字典树的代码实现

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2025-03-05 22:49:03
 * 最后修改: 2025-03-06 11:11:58
 * 文件描述: Trie树的实现 undordered_map
****************************************************************/
#include <iostream>
#include <unordered_map>
using namespace std;

struct TrieNode{
    unordered_map<char, TrieNode*> children;
    bool isEnd = false;
};

void insert(TrieNode* root, const string& word){
    TrieNode* node=root;
    for(char ch:word){
        if(node->children.count(ch)==0){
            node->children[ch]=new TrieNode();
        }
        node=node->children[ch];
    }
    node->isEnd=true;
}

//搜索单词是否在Trie树中
bool search(TrieNode* root, const string& word){
    TrieNode* node=root;
    for(auto &ch:word){
        if(node->children.count(ch)==0){
          return false;
        }
        node=node->children[ch];                                                                                                                                                                                                                                                                                                                                                                                                       
    }
    return node->isEnd;
}

//搜索是否有给定前缀的单词在Trie树中    
bool startWith(TrieNode* root, const string& prefix){
    TrieNode* node=root;
    for(auto &ch:prefix){
        if(node->children.count(ch)==0){
           return false;
        }
    }
    return true;
}

//删除一个单词
void deleteWord(TrieNode* root, const string& word){
    TrieNode* node=root;
    for(auto &ch:word){
        if(node->children.count(ch)==0){
            cout << "not found" << endl;
            return;
        }
        node=node->children[ch];
    }
    node->isEnd=false;
}

//删除整个Trie树
void deleteTrie(TrieNode* root){
    for(auto &ch:root->children){
        deleteTrie(ch.second);
    }
    delete root;
}

int main(){
    TrieNode* root = new TrieNode();
   // 插入单词
   insert(root, "apple");
   insert(root, "app");

    cout << "Search 'apple': " << (search(root, "apple") ? "Yes" :  "No")<<endl;
    deleteWord(root, "apple");
    cout << "Search 'apple': " << (search(root, "apple") ? "Yes" :  "No")<<endl;
    cout << "Search 'app': " << (search(root, "apple") ? "Yes" :  "No")<<endl;   // true
    cout << "Search 'ap': " <<(search(root, "apple") ? "Yes" :  "No")<<endl;     // false
    cout << "Starts with 'ap': " << (startWith(root, "ap") ? "Yes" : "No") << endl;
    cout << "Starts with 'ban': " << (startWith(root, "ban") ? "Yes" : "No") << endl;
    
    deleteTrie(root);
    return 0;
}

i4683

p4683

P4683

Previous Topic

Back to Lesson

Next Topic