| by YoungTimes | No comments

面试刷题-前缀树(Trie)

Trie树,又称前缀树或字典树,是一种树形结构。典型应用是用于统计和排序大量的字符串,经常被搜索引擎系统用于文本词频统计或者自动联想搜索词等。

谷歌的搜索建议

Trie有三个基本特征:

1)除根节点外,每一个节点都只包含一个字符;

2)从根节点到某一节点的路径上经过的字符连接起来,为该节点对应的字符串;

3)每个节点的所有子节点包含的字符都不相同。)

保存了8个键的trie结构:”A”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”.

Trie树实现

Trie 树的结点结构

假设Trie树中存储的全部是英文字符串,英文最多有26个字母,所以TrieNode的next节点最多有26个。

class TrieNode {
public:
    bool isEnd; //该结点是否是一个串的结束
    std::shared_ptr<TrieNode> next[26]; //字母映射表

public:
    TrieNode():isEnd(false) {
	std::cout << "TrieNode Constructor" << std::endl;
	for (int i = 0; i < 26; i++) {
	    next[i] = nullptr;
	}
    }
	
    ~TrieNode() {
	std::cout << "TrieNode Destructor" << std::endl;
    }
};

TrieNode中并没有直接保存字符值,而是通过数字与字母的映射来实现字符的存储。

Trie 树的插入(Insert)

向 Trie 中插入一个单词word。首先从根结点的子结点开始与 word 第一个字符进行匹配,一直匹配到前缀链上没有对应的字符,然后不断插入新的结点,直到插入完 word 的最后一个字符;同时将最后一个结点的isEnd设置为true,表示它是一个单词的末尾。

void insert(const std::string& word) {
    auto node = _root;
    for (const auto& c : word) {
        if (node->next[c -'a'] == nullptr) {
	    node->next[c -'a'] = std::make_shared<TrieNode>();
	}
	node = node->next[c - 'a'];
    }
    node->isEnd = true;
}

Trie 树的搜索(Search)

查找 Trie 中是否存在单词word。从根结点的子结点开始,一直向下匹配,如果出现结点值为空就返回 false;如果匹配到了最后一个字符,则只需判断 node->isEnd即可。

bool search(const std::string& word) {
    auto node = _root;
    for (const char& c : word) {
        node = node->next[c - 'a'];
	if (node == nullptr) {
	    return false;
	}
    }
    return node->isEnd;
}

Trie树的前缀匹配(prefix)

判断Trie中是否有以prefix 为前缀的单词。和search操作类似,只是不需要判断最后一个字符结点的isEnd,因为既然能匹配到最后一个字符,那一定有单词是以它为前缀的。

bool startsWith(const std::string& prefix) {
    auto node = _root;
    for (const char& c : prefix) {
	node = node->next[c-'a'];
	if (node == nullptr) {
	    return false;
	}
    }
    return true;
}

完整Trie树代码

完整Trie树的C++代码如下:

#include <string>
#include <memory>
#include <iostream>

class TrieNode {
public:
    bool isEnd; //该结点是否是一个串的结束
    std::shared_ptr<TrieNode> next[26]; //字母映射表

public:
    TrieNode():isEnd(false) {
	std::cout << "TrieNode Constructor" << std::endl;
	for (int i = 0; i < 26; i++) {
	    next[i] = nullptr;
	}
    }
	
    ~TrieNode() {
	std::cout << "TrieNode Destructor" << std::endl;
    }
};

class Trie {
public:
    Trie() {
	_root = std::make_shared<TrieNode>();
    }
	
    ~Trie() { }
	
private:
    std::shared_ptr<TrieNode> _root = nullptr;
	
public:
    void insert(const std::string& word) {
	auto node = _root;
	for (const auto& c : word) {
	    if (node->next[c -'a'] == nullptr) {
		node->next[c -'a'] = std::make_shared<TrieNode>();
	    }
	    node = node->next[c - 'a'];
	}
	node->isEnd = true;
    }

    bool search(const std::string& word) {
	auto node = _root;
	for (const char& c : word) {
	    node = node->next[c - 'a'];
	    if (node == nullptr) {
		return false;
	    }
	}
	return node->isEnd;
    }

    bool startsWith(const std::string& prefix) {
	auto node = _root;
	for (const char& c : prefix) {
	    node = node->next[c-'a'];
	    if (node == nullptr) {
		return false;
	    }
	}
	return true;
    }
};

int main() {
    auto obj = std::make_shared<Trie>();
    obj->insert("apple");
	
    bool ret = obj->search("apple");
    std::cout << "search apple result:" << ret << std::endl;
	
    ret = obj->search("app");
    std::cout << "search app result:" << ret << std::endl;
	
    ret = obj->startsWith("app");
    std::cout << "startsWith app result:" << ret << std::endl;
	
    obj->insert("apple");
	
    ret = obj->search("app");
    std::cout << "search app result:" << ret << std::endl;
	
    return 0;
}

程序的输入如下:

TrieNode Constructor
TrieNode Constructor
TrieNode Constructor
TrieNode Constructor
TrieNode Constructor
TrieNode Constructor
search apple result:1
search app result:0
startsWith app result:1
search app result:0
TrieNode Destructor
TrieNode Destructor
TrieNode Destructor
TrieNode Destructor
TrieNode Destructor
TrieNode Destructor

参考材料

https://zh.wikipedia.org/wiki/Trie

https://leetcode-cn.com/problems/implement-trie-prefix-tree/solution/trie-tree-de-shi-xian-gua-he-chu-xue-zhe-by-huwt/

除非注明,否则均为[半杯茶的小酒杯]原创文章,转载必须以链接形式标明本文链接

本文链接:http://www.banbeichadexiaojiubei.com/index.php/2020/12/26/%e9%9d%a2%e8%af%95%e5%88%b7%e9%a2%98-%e5%89%8d%e7%bc%80%e6%a0%91trie/