TRIE DATA STRUCTURE

In this project we are going to Implement TRIE DATA STRUCTURE using classes in C++.

Table Of Contents:

• Insertion
• Deletion
• Search Function

Definiton of TRIE DATA STRUCTURE

A trie, also called a prefix tree or radix tree, is a tree-like data structure that stores strings in a way that allows for efficient retrieval

Applications of TRIE DATA STRUCTURE:

• Sorting Dictionaries
• Auto Complete Features While Typing
• Phone Number Searching

Phone Directory Application:

In this Project we are Going to Implement Phone Directory by using Trie Data Structure

The phone directory application demonstrates the practical application of the Trie data structure. It allows users to:

• Add Contacts: User can add Contacts along with their Phone Numbers to the directory.
• Search Directory:Users can search the entire directory.

How it Works ?

The Trie data structure is implemented using a TrieNode class and a Trie class in C++. Each node in the Trie represents a single character. The TrieNode class contains an array of pointers to child nodes, representing possible next characters in the string. The Trie class provides methods for inserting words into the Trie and retrieving suggestions based on a given prefix.

Usage:

To use the phone directory application:

Compile the source code (main.cpp) using a C++ compiler.
Run the compiled executable.
Follow the on-screen instructions to add contacts or search the directory.

Time Complexity Analysis of Tries

Analysis for Inertion:

- When inserting a key into a trie,the time complexity depends on the length of the key.Let n be the number of characters in the key to be inserted.
-In the worst-case scenario,each character requires traversing a new edge in the trie.So,the time complexity for insertion is O(n),where n is the length of the key.

Analysis for Deletion:

-Deletion in a trie involves traversing down the trie based on the characters of the key to be deleted,similar to insertion.
-In the worst case,this traversal extends to the length of the key,resulting in a time complexity of O(n),where n is the length of the key.

Analysis for Search:

-Searching in a trie involves navigating through the trie based on the characters of the searched key.
-The traversal progresses until either the key is found or a character is not present in the trie.In the worst case,this traversal extends to the length of the key,resulting in a time complexity of O(n),where n is the length of the key being searched.

In the above time complexity table 'n' and 'm' represents the size of the string and the number of strings that are stored in the trie.