什么是 Trie 树?
编程如画
共 4372字,需浏览 9分钟
· 2020-12-31
黑脸面试官
猿同学,看你简历上说熟悉数据结构,说说你对 Trie 树的理解。
猿六
Trie 树是一种数据结构,它又叫字典树。
![](https://filescdn.proginn.com/1c41a86b108c143006407c0745931b1d/0b3ff490e4de95f5114f110367d9dff8.webp)
根节点不包含字符,其他节点包含一个字符。 从根节点到某一节点经过的字符连接起来构成一个字符串。如图中的 him 、 her 、 cat 、 no 、 nova。 一个字符串与 Trie 树中的一条路径对应。 在实现过程中,会在叶节点中设置一个标志,用来表示该节点是否是一个字符串的结尾,本例中用青色填充进行标记。 Trie 树中每个节点存储一个字符,从根节点到叶节点的一条路径存储一个字符串。另外,有公共前缀的字符串,他们的公共前缀会共用节点。如 her、 him 共用 h 节点。
![](https://filescdn.proginn.com/5cd10eaae62e97c6427b30757323802b/ca569b89dccd95d4a80aa30d271dda03.webp)
黑脸面试官
如何生成 Trie 树?
猿六
Trie 树的生成过程,就是不断将字符串插入树中。
根节点不存在子节点 h,因此创建子节点 h。 在节点 h 的基础上插入第二个字符 i。 节点 h 不存在子节点 i,创建子节点 i。 在节点 i 的基础上插入第三个字符 m。 节点 i 不存在子节点 m,创建子节点 m。并将该节点标记为字符串结束标志,完成 him 字符串插入。
![](https://filescdn.proginn.com/469ab27d49d87c43ccd81030ed398e93/ef71f2cb2ac19b85d7142ff6f3ed4561.webp)
根节点存在子节点 h。不用重新创建子节点 h。 在节点 h 的基础上插入第二个字符 e。 节点 h 不存在子节点 e,创建子节点 e。 在节点 e 的基础上插入第三个字符 r。 节点 e 不存在子节点 r,创建子节点 r。并将该节点标记为字符串结束标志,完成 her 字符串插入。
![](https://filescdn.proginn.com/f5c4edede58a43a50273867ba32c5ed9/86865c8013f76b2ad6d68cf266fd1a47.webp)
根节点不存在子节点 c,因此创建子节点 c。 在节点 c 的基础上插入第二个字符 a。 节点 c 不存在子节点 a,创建子节点 a。 在节点 a 的基础上插入第三个字符 t。 节点 a 不存在子节点 t,创建子节点 t。并将该节点标记为字符串结束标志,完成 cat 字符串插入。
![](https://filescdn.proginn.com/ac23cd71b8cffb912ed2ae3dd499eb59/d63e64640398f692863bc00bbe4dd0d3.webp)
根节点不存在子节点 n,因此创建子节点 n。 在节点 n 的基础上插入第二个字符 o。 节点 n 不存在子节点 o,创建子节点 o。并将该节点标记为字符串结束标志,完成 no 字符串插入。
![](https://filescdn.proginn.com/b38b61d6f5a62682c2e90490e343e27c/2a89868aa43a87df6de070efa5fe48cf.webp)
根节点存在子节点 n,不用重新创建子节点 n。 在节点 n 的基础上插入第二个字符 o。 节点 n 存在子节点 o,不用重新创建子节点 o。 在节点 o 的基础上插入第三个字符 v。 节点 o 不存在子节点 v,创建子节点 v。 在节点 v 的基础上插入第四个字符 a。 节点 v 不存在子节点 a,创建子节点 a。并将该节点标记为字符串结束标志,完成 nova 字符串插入。
![](https://filescdn.proginn.com/653db8ea16d7ba6a6718184773e1e615/bd64453d25b2853cc6497f86bd82129d.webp)
黑脸面试官
如何删除一个字符串?
猿六
删除一个字符串需要考虑的地方较多。
![](https://filescdn.proginn.com/877cd44692dd9beaf9712836a00f6442/a36ebc59eb08727317c5cdf11622caf0.webp)
![](https://filescdn.proginn.com/bee3560b7e99da7804e93dd1f65a8be7/f3f60c3b23d5c509e6a29dd2592c3c78.webp)
![](https://filescdn.proginn.com/e190ce8ff9f432459340c5960eae9bd2/c52fbc1a923249d9ed2babe1e5ae9853.webp)
![](https://filescdn.proginn.com/f395771704ee5d0c36caccc2c187dcdb/70afaf8830194111c2b94c319b22c03f.webp)
黑脸面试官
Trie 树有什么用?
猿六
Trie 树又叫字典树。字典是用来查字的,Trie 树最基本的作用是在树上查找字符串。
![](https://filescdn.proginn.com/65e0000c967db0a9d9b7097b26867d85/80e5286ca14a2818b6f1907a8dd204d1.webp)
黑脸面试官
写一下 Trie 树实现插入,检索,删除字符串的代码。
//实现 Trie 树节点结构
struct trie_node
{
int isKey = 0; //标志,0:不是字符串结尾,1:是字符串结尾
trie_node* child[26] = {nullptr}; //指向子节点指针
};
//插入字符串:
void insert(string s, trie_node* root)
{
trie_node* p = root;
for (auto c : s)
{
int n = c - 'a';
if (!p->child[n])//没有对应子节点,创建
{
trie_node* q =new trie_node;
p->child[n] = q;
}
p = p->child[n];
}
p->isKey = 1;//字符串结尾标志位置为1
}
//检索字符串
bool search(string s, trie_node* root)
{
trie_node* p = root;
for (auto c : s)
{
int n = c - 'a';
if (!p->child[n])
return 0;
p = p->child[n];
}
if (p->isKey)
return 1;
return 0;
}
//删除字符串:
void remove(string s, trie_node* root)
{
if (!search(s, root))
return;
stack
stkt;//存储路径上节点 stack<int> stkc;//存储待删除字符串
trie_node* p = root;
for (auto c : s)
{
int n = c - 'a';
stkc.push(n);
stkt.push(p->child[n]);
p = p->child[n];
}
p->isKey = 0;//情况二,将标志位置为0
while (!stkt.empty())
{
trie_node* q;
q = stkt.top();
if (q->isKey == 1)//情况三,如果标志位1,停止
return;
for (int i = 0; i < 26; i++)//情况四,如果还有其他字符串公用此前缀,停止
{
if (q->child[i])
return;
}
delete q;//删除节点
stkt.pop();
stkt.top()->child[stkc.top()] = nullptr;//删除边
stkc.pop();
}
}
黑脸面试官
Trie 树还有其他用途吗?
猿六
可以用来词频统计
//重写 Trie 树节点结构
struct trie_node
{
int isKey = 0; //标志,0:不是字符串结尾,1:是字符串结尾
int count = 0;//记录出现次数
trie_node* child[26] = {nullptr}; //指向子节点指针
};
//重写插入字符串:
void insert(string s, trie_node* root)
{
trie_node* p = root;
for (auto c : s)
{
int n = c - 'a';
if (!p->child[n])
{
trie_node* q =new trie_node;
q->count += 1;
p->child[n] = q;
}
p = p->child[n];
}
p->isKey = 1;
}
//实现词频统计
int count(string s, trie_node* root)
{
if(!search(s,root))
return 0;
trie_node* p = root;
for (auto c : s)
{
int n = c - 'a';
p = p->child[n];
}
return p->count;
}
黑脸面试官
说说 Trie 树的优缺点。
猿六
Trie树的核心思想是空间换时间,利用字符串的公共前缀来减少无谓的字符串比较以达到提高查询效率的目的。
黑脸面试官
恩,今天先到这,等下一轮面试吧。
猿六
恩恩,谢谢黑脸面试官。
黑脸面试官
你说谁脸黑,你没下一次面试了。
评论