Home » Data Structure & Algorithms » Trie Data Structure

Trie Data Structure

A trie is an ordered tree data structure that is used to store a dynamic set or associative array where the keys are usually strings.The term trie comes from retrieval. This term was coined by Edward Fredkin, who pronounces it /”tri”/”tree”. However, other authors pronounce it /ˈtraɪ/ “try”, in an attempt to distinguish it verbally from “tree”.Unlike a binary search tree, no node in the tree stores the key associated with that node, instead, its position in the tree defines the key with which it is associated. All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string. Values are normally not associated with every node, only with leaves and some inner nodes that correspond to keys of interest.

 

Problem :
1 : Trie Data Structure search,insert,remove,patternMatch

Question :
WAP to Print to explain insert ,Exact match search and prefix search of String int a trie data structure in O(n) time complexity.

Algorithm :
The problem is solved in iterative way.In the main method we are creating object of Trie class .A node with empty value is created as root.Now while inserting we are taking the whole word and we are inserting each character of word in the tree level wise.Now while searching we are checking each character of the word in the trie and we are proceeding according to the match found in the children trie. Similary while removing a word we are going visting each charcter and subChild and removing the same.

Program  :


Leave a comment

Your email address will not be published. Required fields are marked *

one × 1 =