trie tree Algorithm
The Trie Tree Algorithm, also known as the Prefix Tree or Digital Tree, is a highly efficient data structure that represents a dynamic set of strings with a tree-like structure. It is widely used in search engines, text processing, and autocomplete features due to its efficient string matching and retrieval capabilities. Trie Trees are comprised of nodes, where each node represents a single character in the stored strings. Each node can have multiple children, with each child representing the next character in the string. The root of the tree represents an empty string, and a complete string can be represented by traversing the tree from the root node to a node with a special marker indicating the end of a string.
One of the key advantages of the Trie Tree Algorithm is its ability to search, insert, and delete strings in a time complexity proportional to the length of the string being processed, making it highly efficient for large datasets. As the Trie Tree Algorithm only needs to traverse the tree up to the length of the string in question, it can perform these operations in O(L) time, where L is the length of the string. Furthermore, the Trie Tree Algorithm can effectively handle the storage and retrieval of strings with common prefixes, as these strings will share the same path in the tree up to the point where they diverge. This efficient handling of shared prefixes allows for significant compression and optimization in the storage and retrieval of large datasets, making the Trie Tree Algorithm an important tool in the world of text processing and search engines.
#include <stdio.h>
#include <stdbool.h>
#include <iostream>
#include <string>
// structure definition
typedef struct trie {
struct trie * arr[26];
bool isEndofWord;
} trie;
// create a new node for trie
trie * createNode() {
trie * nn = new trie();
for (int i = 0; i < 26; i++)
nn -> arr[i] = NULL;
nn -> isEndofWord = false;
return nn;
}
// insert string into the trie
void insert(trie * root, std::string str) {
for (int i = 0; i < str.length(); i++) {
int j = str[i] - 'a';
if (root -> arr[j]) {
root = root -> arr[j];
} else {
root -> arr[j] = createNode();
root = root -> arr[j];
}
}
root -> isEndofWord = true;
}
// search a string exists inside the trie
bool search(trie * root, std::string str, int index) {
if (index == str.length()) {
if (!root -> isEndofWord)
return false;
return true;
}
int j = str[index] - 'a';
if (!root -> arr[j])
return false;
return search(root -> arr[j], str, index + 1);
}
/*
removes the string if it is not a prefix of any other
string, if it is then just sets the endofword to false, else
removes the given string
*/
bool deleteString(trie * root, std::string str, int index) {
if (index == str.length()) {
if (!root -> isEndofWord)
return false;
root -> isEndofWord = false;
for (int i = 0; i < 26; i++)
return false;
return true;
}
int j = str[index] - 'a';
if (!root -> arr[j])
return false;
bool
var = deleteString(root, str, index + 1);
if (var) {
root -> arr[j] = NULL;
if (root -> isEndofWord) {
return false;
} else {
int i;
for (i = 0; i < 26; i++)
if (root -> arr[i])
return false;
return true;
}
}
}
int main() {
trie * root = createNode();
insert(root, "hello");
insert(root, "world");
int a = search(root, "hello", 0);
int b = search(root, "word", 0);
printf("%d %d ", a, b);
return 0;
}
