I am currently trying to implement a trie datastructure in Python. The key difference is, instead of the canonical form of tracking only the children of each node, I am keeping track of each node's parents and a value (which I call index). I've delineated my line of confusion with **:
class Node:
def __init__(self, c={}, p = None, i = None, is_leaf = False):
self.children = c
self.parent = p
self.index = i
self.is_leaf = is_leaf
class Trie:
def __init__(self):
self.root = self.get_node()
self.last_added = 0
def get_node(self):
return Node()
def add_node(self, key):
current = self.root
current.index = 0
current.parent = Node(i = -1)
for char in key:
if char not in current.children:
current.children[char] = Node(p = current, i = self.last_added +1)
self.last_added += 1
**current = current.children[char]
current.is_leaf = True
My confusion is this: in my trie, I would like to point my current node to the next node current = current.children[char]. However, if I were to add the string 'ABACA' to my trie, I get the following output:
In:
t = Trie()
t.add_node('ABACA')
t.root.children
Out:
{'A': <__main__.Node at 0x201ae4eb108>,
'B': <__main__.Node at 0x201ae593948>,
'C': <__main__.Node at 0x201ae593ac8>}
Somehow, I am not pointing my object current to the next node. Am I misunderstanding how the addresses of key, values are managed in Python? Sorry for such a naive question!
