使用C++实现trie树（单词查找树，字典树）

Trie树又叫做单词查找树或字典树，Trie树是一种高效的信息检索数据结构。通过使用Trie树，可以将搜索复杂度提高到最优限制(键长)。如果我们将键存储在二叉搜索树中，一个平衡良好的BST需要与M * log N成比例的时间，其中M是最大字符串长度，N是树中的键数。使用Trie树，我们可以在O(M)时间内搜索key，但是，代价是在Trie存储需求上。

Trie树有什么用？trie树的应用如下：

1、散列：在散列中，我们将键转换为一个小值，该值用于索引数据。平均在O(L)时间内支持搜索、插入和删除操作。

2、自平衡BST：自平衡二叉搜索树(BST)(如红黑树、AVL树、Splay树等)中搜索、插入和删除操作的时间复杂度为O(llog n)，其中n为总字数，L为字数长度。自平衡BSTs的优点是，他们保持有序，使操作如最小，最大，最接近和第k个最大更快。

Trie树的完整C++实现如下：

#include <iostream>

// 定义字符大小
#define CHAR_SIZE 128

// 表示Trie节点的类
class Trie
{
public:
    bool isLeaf;
    Trie* character[CHAR_SIZE];

    // 构造函数
    Trie()
    {
        this->isLeaf = false;

        for (int i = 0; i < CHAR_SIZE; i++)
            this->character[i] = nullptr;
    }

    void insert(std::string);
    bool deletion(Trie*&, std::string);
    bool search(std::string);
    bool haveChildren(Trie const*);
};

// 迭代函数：在Trie中插入一个键
void Trie::insert(std::string key)
{
    // 从根节点开始
    Trie* curr = this;
    for (int i = 0; i < key.length(); i++)
    {
        // 如果路径不存在，则创建一个新节点
        if (curr->character[key[i]] == nullptr)
            curr->character[key[i]] = new Trie();

        // 转到下一个节点
        curr = curr->character[key[i]];
    }

    // 将当前节点标记为叶子
    curr->isLeaf = true;
}

// 在Trie中搜索键的迭代函数
// 如果在Trie中找到键，则返回true，否则返回false
bool Trie::search(std::string key)
{
    // trie为空返回false
    if (this == nullptr)
        return false;

    Trie* curr = this;
    for (int i = 0; i < key.length(); i++)
    {
        // 下一个节点
        curr = curr->character[key[i]];

        // 如果字符串无效(在Trie中到达路径末端)
        if (curr == nullptr)
            return false;
    }

    // 如果当前节点是叶节点，并且我们已经到达了字符串的末尾，则返回true
    return curr->isLeaf;
}

// 如果给定节点有任何子节点，则返回true
bool Trie::haveChildren(Trie const* curr)
{
    for (int i = 0; i < CHAR_SIZE; i++)
        if (curr->character[i])
            return true;    

    return false;
}

// 在Trie中删除键的递归函数
bool Trie::deletion(Trie*& curr, std::string key)
{
    if (curr == nullptr)
        return false;

    if (key.length())
    {
        if (curr != nullptr &&
            curr->character[key[0]] != nullptr &&
            deletion(curr->character[key[0]], key.substr(1)) &&
            curr->isLeaf == false)
        {
            if (!haveChildren(curr))
            {
                delete curr;
                curr = nullptr;
                return true;
            }
            else {
                return false;
            }
        }
    }

    if (key.length() == 0 && curr->isLeaf)
    {
        if (!haveChildren(curr))
        {
            delete curr;
            curr = nullptr;

            return true;
        }

        else
        {
            curr->isLeaf = false;

            return false;
        }
    }

    return false;
}

int main()
{
    Trie* head = new Trie();

    head->insert("hello");
    std::cout << head->search("hello") << " ";      // 1

    head->insert("helloworld");
    std::cout << head->search("helloworld") << " "; // 1

    std::cout << head->search("helll") << " ";      // 0 (Not found)

    head->insert("hell");
    std::cout << head->search("hell") << " ";       // 1

    head->insert("h");
    std::cout << head->search("h");                 // 1

    std::cout << std::endl;

    head->deletion(head, "hello");
    std::cout << head->search("hello") << " ";      // 0

    std::cout << head->search("helloworld") << " "; // 1
    std::cout << head->search("hell");              // 1

    std::cout << std::endl;

    head->deletion(head, "h");
    std::cout << head->search("h") << " ";          // 0
    std::cout << head->search("hell") << " ";       // 1
    std::cout << head->search("helloworld");        // 1

    std::cout << std::endl;

    head->deletion(head, "helloworld");
    std::cout << head->search("helloworld") << " "; // 0
    std::cout << head->search("hell") << " ";       // 1

    head->deletion(head, "hell");
    std::cout << head->search("hell");              // 0

    std::cout << std::endl;

    if (head == nullptr)
        std::cout << "Trie empty!!\n";              // empty

    std::cout << head->search("hell");              // 0

    return 0;
}