在本文中,我们将讨论C++ 中的trie 数据结构及其属性、操作和示例。
Trie 数据结构是一种多路树,用于存储不同的字符串。每个字符串由存储在树状结构(即Trie 数据结构)中的字符组成。它也称为基数树或前缀树或数字树。基本上,“ trie ”一词来自“re trie val”一词,意思是检索或取回某些东西。它用于各种任务,例如拼写检查、搜索单词、自动完成等。
Trie数据结构的性质:
trie 数据结构有多种属性。trie数据结构的一些主要属性如下:
- Trie数据结构是树结构的形式,其中每个节点代表字符串的单个字符,从根到节点覆盖的路径代表特定的字符串。
- trie数据结构从根节点开始,根节点始终为空并表示空字符。从根节点开始,出现各种其他分支,保存字符串的其他字符。
- trie 数据结构中字符串的末尾称为叶节点。每个叶节点可能包含额外的信息。
它可以存储和共享引用共享前缀的字符串的公共初始部分。共享公共前缀可以更轻松地高效搜索一组字符串。Trie 数据结构中的操作:
在 trie 数据结构中可以完成三种操作:
1、插入操作:
该操作用于向Trie中添加一个新节点,即一个新字符串。
2、搜索操作:
该操作用于查找特定字符串并检查它是否存在于Trie 数据结构中。
3、删除操作:
此操作用于删除Trie 数据结构中存在的字符串。
例子:
我们举个例子,用C++实现trie数据结构来执行插入、搜索和删除操作。
include <iostream> using namespace std; //Describing the size of the character. define CHAR_SIZE 128 //Here is a class that can be used to store a Trie node. class Trie { public: bool isLeaf; Trie* character[CHAR_SIZE]; Trie() { this->isLeaf = false; for (int k = 0; k< CHAR_SIZE; k++) { this->character[k] = nullptr; } } void insert(string); bool search(string); bool haveChildren(Trie const*); bool deletion(Trie*&, string); }; //Here is an iterative function for inserting a key in a Trie. void Trie::insert(string key) { //Beginning from the root node. Trie* curr = this; for (int k = 0; k< key.length(); k++) { //If the path does not exist, a new node will be created. if (curr->character[key[k]] == nullptr) { curr->character[key[k]] = new Trie(); } //Moving to the next node. curr = curr->character[key[k]]; } //Current node is marked as a leaf. curr->isLeaf = true; } bool Trie::search(string key) { //If the Trie is empty, then return false. if (this == nullptr) { return false; } Trie* curr = this; for (int k = 0; k< key.length(); k++) { curr = curr->character[key[k]]; if (curr == nullptr) { return false; } } return curr->isLeaf; } //Determines whether or not a specified node has any child nodes. bool Trie::haveChildren(Trie const* curr) { for (int k = 0; k< CHAR_SIZE; k++) { if (curr->character[k]) { return true; //A child has beenfound. } } return false; } //Here is a recursive function that can be used to delete a key from a Trie. bool Trie::deletion(Trie*& curr, string key) { //If the Trie is empty, then return false. if (curr == nullptr) { return false; } if (key.length()) { if (curr != nullptr && curr->character[key[0]] != nullptr && deletion(curr->character[key[0]], key.substr(1)) && curr->isLeaf == false) { if (!haveChildren(curr)) { delete curr; curr = nullptr; return true; } else { return false; } } } //If the end of the key has been reached. if (key.length() == 0 && curr->isLeaf) { if (!haveChildren(curr)) { //Delete the current node. delete curr; curr = nullptr; //Delete the parent nodes that are not at the leaf level. return true; } else { curr->isLeaf = false; return false; } } return false; } //Trie data structure C++ implementation int main() { Trie* head = new Trie(); head->insert("java"); cout << head->search("java") << " "; //Returns 1 (If found) head->insert("javatpoint"); cout << head->search("javatpoint") << " "; //Returns1 cout << head->search("javaa") << " "; //Returns0 (If not found) head->insert("javac"); cout << head->search("javac") << " "; //Returns1 head->insert("j"); cout << head->search("j"); //Returns1 cout << endl; head->deletion(head, "java"); cout << head->search("java") << " "; //Returns0 cout << head->search("javatpoint") << " "; //Returns1 cout << head->search("javac"); //Returns1 cout << endl; head->deletion(head, "j"); cout << head->search("j") << " "; //Returns0 cout << head->search("javac") << " "; //Returns1 cout << head->search("javatpoint"); //Returns1 cout << endl; head->deletion(head, "javatpoint"); cout << head->search("javatpoint") << " "; //Returns0 cout << head->search("javac") << " "; //Returns1 head->deletion(head, "javac"); cout << head->search("javac"); //Returns0 cout << endl; if (head == nullptr) { cout << "Empty!!\n"; //Trie is empty now } cout << head->search("javac"); //Returns0 return 0; }
|
上述 C++ 程序的解释:
- 首先,程序中包含 C++ 库。
- 我们假设马可 "CHAR_SIZE "有 128 个字符。
- 我们创建了一个名为 "Trie "的类,该类有四个成员函数:insert、search、haveChildren 和 deletion。
- 插入 "函数用于向 Trie 中添加字符串。
- search "函数用于在 Trie 中搜索字符串,如果发现该字符串,则返回 true。
- haveChildren "函数用于检查给定 Trie 节点中是否有非零的子节点。
- delete "函数是一个递归函数,用于从 Trie 中删除一个字符串。
- 使用 "insert "函数插入各种字符串,包括 "java"、"javatpoint"、"javac "和 "j"。
- 使用 "search"功能检查各种字符串是否存在。搜索字符串 "java "时,返回 true。同样,搜索字符串 "javatpoint "时,返回 true。搜索字符串 "javaa "时,返回 false,因为 Trie 中没有这个字符串。搜索字符串 "javac "时,返回 true;搜索字符串 "j "时,返回 true。
- 然后,使用 "deletion "删除字符串 "java"、"javatpoint"、"javac "和 "j"。
- 删除操作完成后,"search "方法会再次被调用,以验证字符串是否已从 Trie 中成功删除。
- 如果搜索操作成功,找到字符串时返回 1,找不到字符串时返回 0。
- 最终输出将显示 Trie 为空。它会打印 "Empty!!"并返回 O。
结论
在本文中,我们了解了 Trie 数据结构,这是一种存储字符串集合的树状结构。它有多种应用,如单词搜索、拼写检查、自动完成等。我们还了解了 Trie 数据结构的各种操作,包括插入、搜索和删除操作。