字典树(trie)

一、字典树的概念

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

Trie data structure

二、字典树的功能

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

  • 1、维护字符串集合(即字典)。
  • 2、向字符串集合中插入字符串(即建树)。
  • 3、查询字符串集合中是否有某个字符串(即查询)。
  • 4、统计字符串在集合中出现的个数(即统计)。
  • 5、将字符串集合按字典序排序(即字典序排序)。
  • 6、求集合内两个字符串的LCP(Longest Common Prefix,最长公共前缀)(即求最长公共前缀)。
本以为(Trie)字典树很难,却发现也就这么回事!

三、字典树的代码实现

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
/***************************************************************
 * C++ implementation of  Trie
 *author : Alex Li 
 * date : 2023-6-2
 * version : 1.0
 * ****************************************************************/ 

#include <iostream>
using namespace std;
 
const int ALPHABET_SIZE = 26;
 
// trie node
struct TrieNode {
    struct TrieNode* children[ALPHABET_SIZE];
    // isEndOfWord is true if the node represents end of a word
    bool isEndOfWord;
};
 
// Returns new trie node (initialized to NULLs)
struct TrieNode* getNode(void){
    struct TrieNode* pNode = new TrieNode;
     pNode->isEndOfWord = false;
     for (int i = 0; i < ALPHABET_SIZE; i++)
        pNode->children[i] = NULL;
     return pNode;
}
 
// If not present, inserts key into trie  If the key is prefix of trie node, just
// marks leaf node
void insert(struct TrieNode* root, string key){
    struct TrieNode* pCrawl = root;
     for (int i = 0; i < key.length(); i++) {
        int index = key[i] - 'a';
        if (!pCrawl->children[index])
            pCrawl->children[index] = getNode();
         pCrawl = pCrawl->children[index];
    }
     // mark last node as leaf
    pCrawl->isEndOfWord = true;
}
 
// Returns true if key presents in trie, else false
bool search(struct TrieNode* root, string key){
    struct TrieNode* pCrawl = root;
     for (int i = 0; i < key.length(); i++) {
        int index = key[i] - 'a';
        if (!pCrawl->children[index])
            return false;
         pCrawl = pCrawl->children[index];
    }
     return (pCrawl != NULL && pCrawl->isEndOfWord);
}
 
// Returns true if root has no children, else false
bool isEmpty(TrieNode* root){
    for (int i = 0; i < ALPHABET_SIZE; i++)
        if (root->children[i])return false;
        return true;
}
 
// Recursive function to delete a key from given Trie
TrieNode* remove(TrieNode* root, string key, int depth = 0){
    // If tree is empty
    if (!root)
        return NULL;
 
    // If last character of key is being processed
    if (depth == key.size()) {
         // This node is no more end of word after
        // removal of given key
        if (root->isEndOfWord)
            root->isEndOfWord = false;
         // If given is not prefix of any other word
        if (isEmpty(root)) {
            delete (root);
            root = NULL;
        }
 
        return root;
    }
 
    // If not last character, recur for the child obtained using ASCII value
    int index = key[depth] - 'a';
    root->children[index] =
          remove(root->children[index], key, depth + 1);
 
    // If root does not have any child (its only child got
    // deleted), and it is not end of another word.
    if (isEmpty(root) && root->isEndOfWord == false) {
        delete (root);
        root = NULL;
    }
 
    return root;
}
 
// Driver
int main(){
    // Input keys (use only 'a' through 'z' and lower case)
    string keys[] = { "the", "a", "there",
                      "answer", "any", "by",
                      "bye", "their", "hero", "heroplane" };
    int n = sizeof(keys) / sizeof(keys[0]);
     struct TrieNode* root = getNode();
     // Construct trie
    for (int i = 0; i < n; i++)
        insert(root, keys[i]);
     // Search for different keys
    search(root, "the") ? cout << "Yes\n" : cout << "No\n";
    search(root, "these") ? cout << "Yes\n" : cout << "No\n";
    search(root, "bye") ? cout << "Yes\n" : cout << "No\n";
    remove(root, "bye");
    search(root,"bye")? cout << "Yes\n" : cout << "No\n";
    return 0;
}
Scroll to Top