питон ссылка ошибка в построении TRIE дерева

Question

Я хочу построить тривиальное TRIE дерево питона, а вот мой код

class Node: 
    def __init__(self,ref={},num=0): 
     self.ref = ref 
     self.num = num 

def makeTrie(node,s): 
    node.ref.setdefault(s[0],Node()) 
    if len(s) == 1: 
     node.ref[s[0]].num += 1 
     return 
    makeTrie(node.ref[s[0]],s[1:]) 


trie = Node() 
makeTrie(trie,'abcd') 

print trie.ref['d'].num 
print trie.ref['a'].ref['b'].ref['c'].ref['d'].num 

И я очень смущен, заявление print trie.ref['d'].num также значение !! Но я не знаю, когда я вставляю 'd' в trie? Приведенный выше код не вставляет 'd' в trie.ref['a'].ref['b'].ref['c']

Answer 1

У вас возникла проблема с mutable default arguments, я думаю.

В инициализаторе для Node у вас есть ref={}. Но {} - это dict и, следовательно, изменяемый объект. Таким образом, каждый вызов Node() вызывает инициализатор, который мутирует тот же словарь ref.

Fix (я думаю):

class Node: 
    #      vvvv 
    def __init__(self, ref=None, num=0): 
     if ref is None: # <-- 
      ref = {} # <-- 
     self.ref = ref 
     self.num = num 

def makeTrie(node,s): 
    node.ref.setdefault(s[0],Node()) 
    if len(s) == 1: 
     node.ref[s[0]].num += 1 
     return 
    makeTrie(node.ref[s[0]],s[1:]) 

trie = Node() 
makeTrie(trie,'abcd') 

try: 
    print(trie.ref['d'].num) 
except KeyError: 
    print('KeyError occurred!') 
print(trie.ref['a'].ref['b'].ref['c'].ref['d'].num) 

Результат:

KeyError occurred! 
1