数据结构（12）-- 前缀树（字典树、Trie）

看、未来

发布于 2021-09-18 10:35:16

7220

发布于 2021-09-18 10:35:16

文章被收录于专栏：CSDN搜“看，未来”

文章目录

什么是前缀树？

直接说可能不太理解，我直接来张图：

晓得了吧，一种特殊的N叉树。用于检索字符串数据集中的键。

Trie的应用场景

自动补全

就是前面那张谷歌的图，我也想自己截，奈何技术跟不上啊。

拼写检测

最长前缀匹配

比方说正则表达式，不过正则比这个要复杂一些了。

可以用来提取出表中所有以“ABC”开头的数据，但是数据表浩如烟海，你总不能让我去遍历吧！！！

Trie存在即合理

在平衡树、哈希表等树据结构的重重包围之下，Trie还是占据了一席之地，那么它有什么突出点呢？

这些树据结构，虽然各有千秋，但是总有鞭长莫及的时候，碧如：

找到具有同一前缀的全部键值。
按词典序枚举字符串的数据集。

没办法吧！！

随着哈希表大小增加，会出现大量的冲突，时间复杂度可能增加到 O(n)与哈希表相比，Trie 树在存储多个具有相同前缀的键时可以使用较少的空间。此时 Trie 树只需要 O(m)的时间复杂度，其中 m 为键长（顶多5*m）。而在平衡树中查找键值需要 O(mlog⁡n)时间复杂度。

Trie的实现

节点结构

Trie 树是一个有根的树，其结点具有以下字段：。

最多 R 个指向子结点的链接，其中每个链接对应字母表数据集中的一个字母。
布尔字段，以指定节点是对应键的结尾还是只是键前缀。

class Trie {
private:
    bool isEnd;
    Trie* next[26];
public:
    void insert(string word);
    bool search(string word);
    bool startsWith(string prefix);	//前缀匹配
};

先捋一下这个节点结构，会发现它没有包当前节点值。这是为什么呢？这是由于它的字母映射表机制决定的（next）。

next当中包括了接下来可能会出现的所有字母，所以只需：

for (int i = 0; i < 26; i++) {
    char ch = 'a' + i;
    if (parentNode->next[i] == NULL) {
        //说明父结点的后一个字母不可为 ch
    } else {
        //说明父结点的后一个字母可以是 ch
    }
}

自己捋一下。

增

往前缀树中插入一个单词。

这有三种情况。 1、这个单词已经存在 2、这个单词已经是前缀了 3、这个单词不存在

对这三种情况，首先要做的都是遍历这棵树。如果存在，那就没事儿了。如果是前缀，那就改成完整的单词。如果不存在，那就把缺少的字母补进去，并设为完整的单词。

void insert(string word) {
    Trie* node = this;
    for (char c : word) {
        if (node->next[c-'a'] == NULL) {
            node->next[c-'a'] = new Trie();
        }
        node = node->next[c-'a'];
    }
    node->isEnd = true;
}

查

在前缀树中查找一个单词是否存在。这里有两种情况：查到一半发现单词断层了，这妥妥的没了、查到最后，结果这个单词只是前缀，那也是不行的。

bool search(string word) {
    Trie* node = this;
    for (char c : word) {
        node = node->next[c - 'a'];
        if (node == NULL) {
            return false;
        }
    }
    return node->isEnd;
}

前缀匹配

匹配一个单词是否是前缀树中的前缀。

你看呢？

bool search(string word) {
    Trie* node = this;
    for (char c : word) {
        node = node->next[c - 'a'];
        if (node == NULL) {
            return false;
        }
    }
    return true;
}

代码集合

整理一下代码：

#include<iostream>

using namespace std;

class Trie {
private:
	bool isEnd;
	Trie* next[26];

public:
	void insert(string s) {
		Trie* node = this;
		for (char c : s) {
			if (NULL == next[c - 'a']) {
				next[c - 'a'] = new Trie();
			}
			node = next[c - 'a'];
		}
		node->isEnd = true;
	}

	bool search(string s) {
		Trie* node = this;
		for (char c : s) {
			if (NULL == next[c - 'a']) {
				return false;
			}
			node = next[c - 'a'];
		}

		return node->isEnd;
	}

	bool startsWith(string prefix) {
		Trie* node = this;
		for (char c : prefix) {
			if (NULL == next[c - 'a']) {
				return false;
			}
			node = next[c - 'a'];
		}

		return true;
	}
};

int main() {

}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021/03/18 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度