Trie Insert and Search

break_it_down

• Each trie node will have property children which is array of 26 length and a boolean propertyis_end_of_word
• Create helper method to convertcharacter_to_index
• insert_operation
  • pCrawl set to root
  • iterate for word length count, eg: for key length 3
  • covert eachcharacter_to_index
  • if that index don’t exist create it and assign a trie node there
  • next character will be inserted in this trie node.
  • Once all character are inserted, setis_end_of_word to true.
  • 

• search

Code

# Python program for insert and search
# operation in a Trie
 
class TrieNode:
	
	# Trie node class
	def __init__(self):
		self.children = [None]*26
 
		# isEndOfWord is True if node represent the end of the word
		self.isEndOfWord = False
 
class Trie:
	
	# Trie data structure class
	def __init__(self):
		self.root = self.getNode()
 
	def getNode(self):
	
		# Returns new trie node (initialized to NULLs)
		return TrieNode()
 
	def _charToIndex(self,ch):
		
		# private helper function
		# Converts key current character into index
		# use only 'a' through 'z' and lower case
		
		return ord(ch)-ord('a')
 
 
	def insert(self,key):
		
		# If not present, inserts key into trie
		# If the key is prefix of trie node,
		# just marks leaf node
		pCrawl = self.root
		length = len(key)
		for level in range(length):
			index = self._charToIndex(key[level])
 
			# if current character is not present
			if not pCrawl.children[index]:
				pCrawl.children[index] = self.getNode()
			pCrawl = pCrawl.children[index]
 
		# mark last node as leaf
		pCrawl.isEndOfWord = True
 
	def search(self, key):
		
		# Search key in the trie
		# Returns true if key presents
		# in trie, else false
		pCrawl = self.root
		length = len(key)
		for level in range(length):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				return False
			pCrawl = pCrawl.children[index]
 
		return pCrawl.isEndOfWord
 
# driver function
def main():
 
	# Input keys (use only 'a' through 'z' and lower case)
	keys = ["the","a","there","anaswe","any",
			"by","their"]
	output = ["Not present in trie",
			"Present in trie"]
 
	# Trie object
	t = Trie()
 
	# Construct trie
	for key in keys:
		t.insert(key)
 
	# Search for different keys
	print("{} ---- {}".format("the",output[t.search("the")]))
	print("{} ---- {}".format("these",output[t.search("these")]))
	print("{} ---- {}".format("their",output[t.search("their")]))
	print("{} ---- {}".format("thaw",output[t.search("thaw")]))
 
if __name__ == '__main__':
	main()