【数据结构与算法】前缀树的实现

• 算法结构

🌠作者：@阿亮joy.

🎆专栏：《数据结构与算法要啸着学》

🎇座右铭：每个优秀的人都有一段沉默的时光，那段时光是付出了很多努力却得不到结果的日子，我们把它叫做扎根

在这里插入图片描述

目录

    • 👉前缀树的实现👈
      • 什么是前缀树
      • 节点的定义
      • 构造函数
      • 插入字符串
      • 查找字符串和前缀
      • 析构函数
      • 删除字符串
      • 打印前缀树
      • 完整代码
      • OJ题：实现前缀树
    • 👉总结👈

👉前缀树的实现👈

什么是前缀树

Trie（发音类似 “try”），被称为前缀树或字典树，是一种树形的数据结构，可用于高效地存储和检索字符串数据集中的键。这个数据结构有相当多的应用情景，例如自动补完和拼写检查。下图就是经典的前缀树，我们接下来要实现的前缀树的节点存储的数据比较丰富，以达到特定字符串在树中出现几次等类似的功能。

在这里插入图片描述

节点的定义

// 前缀树节点的定义
// 假设字符都是小写字母
struct TrieNode
{
	int pass = 0;	// 有几个字符串经过该节点(前缀包含这个字符的字符串数量)
	int end = 0;	// 以该节点为结尾的字符串的数量,如果不允许字符串重复插入,可以改成bool
	// next[0] == nullptr 表示没有走向'a'的路
	// next[0] != nullptr 表示有走向'a'的路
	// ...
	// next[25] != nullptr 表示有走向'z'的路
	TrieNode* next[26] = { nullptr };	// 26个空位,准备挂下一个节点'a'-'z',没有挂节点时为nullptr
	// 如果字符种类个数比较多,可以将数组换成哈希表或者set
};

构造函数

前缀树是用哨兵位头节点来管理整棵前缀树的，所以其构造函数需要 new 上一个哨兵位头节点。

class Trie
{
	typedef TrieNode Node;
public:
	Trie()
	{
		_root = new Node();
	}
private:
	Node* _root = nullptr;	// 哨兵位头节点,可以用来求前缀树中字符串的数量,也可以求空串的数量
};

注：哨兵位头节点的 pass 值可以表示前缀树含有的字符串数量，end 值可以表示前缀树含有空串的数量。因为任何字符串都会以空串作为前缀，都会经过哨兵位头节点。

插入字符串

我们从哨兵位头节点开始，插入字符串。对于当前字符对应的子节点，有以下两种情况：

  • 子节点存在：沿着指针移动到子节点，继续处理下一个字符。
  • 子节点不存在：创建一个新的子节点，记录在 next 指针数组的对应的位置上，然后沿着指针移动到子节点，继续处理下一个字符。
  • 插入字符串的同时，还需要更新沿途节点的 pass 值。

插入字符串图解：

在这里插入图片描述

class Trie
{
public:
	void Insert(const string& str)
	{
		Node* cur = _root;
		++cur->pass;	// 任何一个字符串都需要经过哨兵位头节点

		for (size_t i = 0; i < str.size(); ++i)
		{
			size_t index = str[i] - 'a';
			// 如果之前没有字符串经过该节点,则需要建出新节点
			if (cur->next[index] == nullptr)
			{
				cur->next[index] = new Node();
			}
			cur = cur->next[index];
			++cur->pass;
		}
		// cur指向字符串的最后一个节点,++cur->end表示多了一个字符串以该节点结尾
		++cur->end;
	}
}

如果不需要插入重复字符串，可以将函数的返回值改成 bool 类型。

查找字符串和前缀

class Trie
{
public:
	// 查找前缀树中有多少个要查找的字符串
	size_t Search(const string& str) const
	{
		Node* cur = _root;
		for (auto ch : str)
		{
			// 找的过程发现没路了,说明树中不存在要查找的字符串
			if (cur->next[ch - 'a'] == nullptr)
			{
				return 0;
			}
			cur = cur->next[ch - 'a'];
		}
		// cur是str最后一个字符,cur->end表示树中有多少个str
		return cur->end;
	}
	
	// 查找树中有多少个字符串以前缀prefix为前缀
	size_t StartsWith(const std::string& prefix) const
	{
		Node* cur = _root;
		for (auto ch : prefix)
		{
			// 找的过程中发现没有路,则说明没有字符串以prefix为前缀
			if (cur->next[ch - 'a'] == nullptr)
			{
				return 0;
			}
			cur = cur->next[ch - 'a'];
		}
		// cur->pass表示有多少个字符串以prefix为前缀
		return cur->pass;
	}
}

注：查找的过程和插入的过程非常的相似，只是查找时发现没有路，就直接返回 0，表示树中没有该字符串或者树中的字符串不以 prefix 为前缀。注：如果树中有要查找的字符串 str，则 cur->end 表示树中有多少个 str；如果树有字符串以 prefix 为前缀，则 cur->pass 表示多少个字符串以 prefix 为前缀。

析构函数

class Trie
{
	typedef TrieNode Node;
public:
	~Trie()
	{
		Destroy(_root);
	}
private:
	void Destroy(Node* root)
	{
		// 先销毁孩子节点,才能够销毁自己
		for (int i = 0; i < 26; ++i)
		{
			// root->next[i]不为空,则说明有节点,需要递归释放节点
			if (root->next[i] != nullptr)
			{
				Destroy(root->next[i]);
			}
		}
		delete root;
	}
}

前缀树析构时，需要先释放孩子节点，才能够释放哨兵位头节点。而孩子节点有可能会有孩子节点，所以我们可以采用递归去释放节点。

删除字符串

class Trie
{
	typedef TrieNode Node;
public:
	// 从树中删除字符串str,注：如果有多个str,只会删除一次
	void Erase(const string& str)
	{
		// 树中没有str,无法删除
		if (Search(str) == 0)
			return;

		Node* cur = _root;
		--cur->pass;

		for (size_t i = 0; i < str.size(); ++i)
		{
			size_t index = str[i] - 'a';
			// 如果发现str是唯一经过该节点的字符串
			// 那么就需要递归去释放当前节点及后续路径的节点
			if (--cur->next[index]->pass == 0)
			{
				Destroy(cur->next[index]);	// 递归释放节点
				cur->next[index] = nullptr;	// next需要置为nullptr
				return;
			}
			cur = cur->next[index];
		}
		// 如果字符串的所有字符都删除了一遍,还有该路径,那么最后要
		// --cur->end,表明树中str的个数减少了一个
		--cur->end;
	}
}

删除字符串时，需要看树中是否有需要删除的字符串。如果没有，直接 return 即可。如果有，才进行删除。进行删除时，如果发现 str 是唯一经过该节点的字符串，那么就需要递归去释放当前节点及后续路径的节点。

打印前缀树

class Trie
{
	typedef TrieNode Node;
public:
	void Print() const
	{
		cout << "根节点:[" << "pass: " <pass << " end: " <end << "]" << endl;
		_Print(_root);
	}
private:
	void _Print(Node* root) const
	{
		if (root == nullptr)
			return;
		for (int i = 0; i < 26; ++i)
		{
			if (root->next[i] == nullptr)
				continue;
			else
			{
				cout << "节点" << (char)('a' + i) << ":[pass: " <next[i]->pass << " end: " <next[i]->end << "]" <next[i]);
			}
		}
	}
}

完整代码

#pragma once

#include 
#include 
#include 
using namespace std;

// 前缀树节点的定义
// 假设字符都是小写字母
struct TrieNode
{
	int pass = 0;	// 有几个字符串经过该节点(前缀包含这个字符的字符串数量)
	int end = 0;	// 以该节点为结尾的字符串的数量,如果不允许重复插入,可以改成bool
	// next[0] == nullptr 表示没有走向'a'的路
	// next[0] != nullptr 表示有走向'a'的路
	// ...
	// next[25] != nullptr 表示有走向'z'的路
	TrieNode* next[26] = { nullptr };	// 26个空位,准备挂下一个节点'a'-'z',没有挂节点时为nullptr
	// 如果字符种类个数比较多,可以将数组换成哈希表或者set
};

class Trie
{
	typedef TrieNode Node;
public:
	Trie()
	{
		_root = new Node();
	}

	~Trie()
	{
		Destroy(_root);
	}

	// 查找前缀树中有多少个要查找的字符串
	size_t Search(const string& str) const
	{
		Node* cur = _root;
		for (auto ch : str)
		{
			// 找的过程发现没路了,说明树中不存在要查找的字符串
			if (cur->next[ch - 'a'] == nullptr)
			{
				return 0;
			}
			cur = cur->next[ch - 'a'];
		}
		// cur是str最后一个字符,cur->end表示树中有多少个str
		return cur->end;
	}

	// 查找树中有多少个字符串以前缀prefix为前缀
	size_t StartsWith(const std::string& prefix) const
	{
		Node* cur = _root;
		for (auto ch : prefix)
		{
			// 找的过程中发现没有路,则说明没有字符串以prefix为前缀
			if (cur->next[ch - 'a'] == nullptr)
			{
				return 0;
			}
			cur = cur->next[ch - 'a'];
		}
		// cur->pass表示有多少个字符串以prefix为前缀
		return cur->pass;
	}

	// 插入字符串
	void Insert(const string& str)
	{
		Node* cur = _root;
		++cur->pass;	// 任何一个字符串都需要经过哨兵位头节点

		for (size_t i = 0; i < str.size(); ++i)
		{
			size_t index = str[i] - 'a';
			// 如果之前没有字符串经过该节点,则需要建出新节点
			if (cur->next[index] == nullptr)
			{
				cur->next[index] = new Node();
			}
			cur = cur->next[index];
			++cur->pass;
		}
		// cur指向字符串的最后一个节点,++cur->end表示多了一个字符串以该节点结尾
		++cur->end;
	}

	// 从树中删除字符串str,注：如果有多个str,只会删除一次
	void Erase(const string& str)
	{
		// 树中没有str,无法删除
		if (Search(str) == 0)
			return;

		Node* cur = _root;
		--cur->pass;

		for (size_t i = 0; i < str.size(); ++i)
		{
			size_t index = str[i] - 'a';
			// 如果发现str是唯一经过该节点的字符串
			// 那么就需要递归去释放当前节点及后续路径的节点
			if (--cur->next[index]->pass == 0)
			{
				Destroy(cur->next[index]);	// 递归释放节点
				cur->next[index] = nullptr;	// next需要置为nullptr
				return;
			}
			cur = cur->next[index];
		}
		// 如果字符串的所有字符都删除了一遍,还有该路径,那么最后要
		// --cur->end,表明树中str的个数减少了一个
		--cur->end;
	}

	void Print() const
	{
		cout << "根节点:[" << "pass: " <pass << " end: " <end << "]" << endl;
		_Print(_root);
	}

private:
	void Destroy(Node* root)
	{
		// 先销毁孩子节点,才能够销毁自己
		for (int i = 0; i < 26; ++i)
		{
			if (root->next[i] != nullptr)
			{
				Destroy(root->next[i]);
			}
		}
		delete root;
	}

	void _Print(Node* root) const
	{
		if (root == nullptr)
			return;
		for (int i = 0; i < 26; ++i)
		{
			if (root->next[i] == nullptr)
				continue;
			else
			{
				cout << "节点" << (char)('a' + i) << ":[pass: " <next[i]->pass << " end: " <next[i]->end << "]" <next[i]);
			}
		}
	}

private:
	Node* _root = nullptr;	// 哨兵位头节点,可以用来求前缀树中字符串的数量,也可以求空串的数量
};

前缀树的测试

void TrieTest()
{
	Trie t;
	vector v = { "abc","abd", "abe", "abe", "" ,"a" , "bc", "bd", "be" };
	for (string& str : v)
	{
		t.Insert(str);
	}
	// 前缀树的打印
	t.Print();
	cout << "----------------------" << endl;

	// 输出空串的数量
	cout << "空串的数量: " << t.Search("") << endl;
	// 任意字符串均以空串为前缀/树中字符串的数量
	cout << "树中字符串的数量: " << t.StartsWith("") << endl;
	// 以"ab"为前缀的字符串个数
	cout << "以ab为前缀的字符串个数: " << t.StartsWith("ab") << endl;

	cout << "----------------------" << endl;
	// 测试删除
	for (string& str : v)
	{
		t.Erase(str);
	}
	t.Print();
}

在这里插入图片描述

OJ题：实现前缀树

这里是引用

LeetCode 上的实现前缀树是比我们实现的前缀树是要难度低的，所以只需要将上面的代码拷贝过去，再将函数名和函数的返回值修改成题目要求的样子就可以通过了。

在这里插入图片描述

👉总结👈

本篇博客主要讲解了什么是前缀树以及前缀树的实现等。那么以上就是本篇博客的全部内容了，如果大家觉得有收获的话，可以点个三连支持一下！谢谢大家！💖💝❣️

本文来自网络，不代表协通编程立场，如若转载，请注明出处：https://net2asp.com/4489fc68c8.html

赞 (0)
« 上一篇 1天前
下一篇 » 1天前

相关推荐