Trie Data Structure

[Soumen Khatua]

from collections import defaultdict


class TrieNode():

def __init__(self):
self.children = defaultdict()
self.terminating = False


class Trie():

def __init__(self):
self.root = self.get_node()

def get_node(self):
return TrieNode()

def get_index(self, ch):
return ord(ch) - ord('a')

def insert(self, word):

root = self.root
len1 = len(word)

for i in range(len1):
index = self.get_index(word[i])

if index not in root.children:
root.children[index] = self.get_node()
root = root.children.get(index)

root.terminating = True

def search(self, word):
root = self.root
len1 = len(word)

for i in range(len1):
index = self.get_index(word[i])
if not root:
return False
root = root.children.get(index)

return True if root and root.terminating else False

def delete(self, word):

root = self.root
len1 = len(word)

for i in range(len1):
index = self.get_index(word[i])

if not root:
print ("Word not found")
return -1
root = root.children.get(index)

if not root:
print ("Word not found")
return -1
else:
root.terminating = False
return 0

def update(self, old_word, new_word):
val = self.delete(old_word)
if val == 0:
self.insert(new_word)



if __name__ == "__main__":

strings = ["pqrs", "pprt", "psst", "qqrs", "pqrs"]

t = Trie()
for word in strings:
t.insert(word)

Could anyone tell me,How Inset function is working here? actually I'm not able to track it. Specially if index is alerady available in root.children then how it is creating an another TrieNode object.

Thank you in advance 

[onlinejudge95]

I am ready to answer your question, but not here it's a Django User's Group. The question you are asking is about implementation of an algorithm which is language agnostic. Technically, it shouldn't be asked in the Python Mailing list too.

Keep a watch on your inbox though. :)

Thanks,

onlinejudge95

--
You received this message because you are subscribed to the Google Groups "Django users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to django-users...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/django-users/CAPUw6WbzxcxyzwKynS9vnZe5cwem2bT8bjLZS%2BO9C%2BfyV6V6MA%40mail.gmail.com.

[Soumen Khatua]

Sorry.

But I don't have any mail in my inbox from your side.

Thank you 

To view this discussion on the web visit https://groups.google.com/d/msgid/django-users/CAD%3DM5eTHoFBbwPiMphieWSB8pemHM0Tzs_r1CjfjdPVB0NWCaw%40mail.gmail.com.