回到首页

trie树

trie树相当于查字典，如下构建字典树可以知晓树中存在的单词和构建时单词的重复次数。trie树相比hash构建词典的好处是关键字不会冲突，不会出现hash碰撞，短字符串的查询理论上来说比长字符串更快，可以对关键字按字典序排序。

#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();
	// 创建trie树
	for(int i=0;i<8;i++)trie_insert(root,keys[i]);
	// 检索字符串
	char s[][32]={"Present in trie","Not present in trie"};
	printf("%s --- %s\n","the",trie_search(root,"the")>0?s[0]:s[1]);
	printf("%s --- %s\n","these",trie_search(root,"these")>0?s[0]:s[1]);
	printf("%s --- %s\n","their",trie_search(root,"their")>0?s[0]:s[1]);
	printf("%s --- %s\n","thaw",trie_search(root,"thaw")>0?s[0]:s[1]);
	return 0;
}

在212. 单词搜索 II用到的trie树构建代码，更具有C++特点，看起来更简单，查询到单词末尾的节点含有单词

struct TrieNode{
    string word;
    unordered_map<char,TrieNode*> children;
    TrieNode(){
        this->word="";
    }
};

void insertTrie(TrieNode *root,const string &word){
    TrieNode *node=root;
    for(auto c:word){
        if(!node->children.count(c))node->children[c]=new TrieNode();
        node=node->children[c];
    }
    node->word=word;
}

参考链接：Trie树（Prefix Tree）介绍

本文创建于2022.7.7/18.8，修改于2023.3.11/23.26