shinchancode / trie-data-structure

Trie is a tree-based data structure, which is used for efficient retrieval of a key in a large dataset of strings.

Trie-Data-structure

Trie is a tree-based data structure, which is used for efficient retrieval of a key in a large dataset of strings.

It is a type of k-ary search tree used for storing and searching a specific key from a set. Using Trie, search complexities can be brought to optimal limit (key length).

Trie Data

Data structure and relevant algorithms for extremely fast prefix/fuzzy string searching.

Comparison with Binary Search Tree

If we store keys in a binary search tree, a well balanced BST will need time proportional to M * log N, where M is the maximum string length and N is the number of keys in the tree.

Trie is an efficient information retrieval data structure. Using Trie, search complexities can be brought to optimal limit O(M) (Where M is the maximum string length).

---

The idea is that all strings sharing common prefix should come from a common node. The tries are used in spell checking programs.

• Preprocessing pattern improves the performance of pattern matching algorithm. But if a text is very large then it is better to preprocess text instead of pattern for efficient search.
• A trie is a data structure that supports pattern matching queries in time proportional to the pattern size.

---

[Basic Implementation]

---

Do star ⭐ this Repository if you feel it helped & drop a follow!

💙 Happy Learning 💙

Demo || Working

Open the folder to view the working and output..

Usage

Create a Trie with:

Trie *t = new Trie();

Add Keys with:

// i.e. you could store any information you would like to associate with
// this particular key.
t->insert(name, num);

Find a key with:

bool ok = t->search(s);

Remove Keys with:

t->remove(name);

Search with:

t->search(s);

Prefix search with:

t->starts_with(s);

Prefix search with recommendations:

t->show_recommendations(name);

Contributing

Fork this repo and run tests with:

Connect with me: