Trie в питона, ссылка на объект

Question

им, глядя на следующей реализации синтаксического дерева в Python:

tree = {} 

def add_to_tree(root, value_string): 
    for character in value_string: 
     root = root.setdefault(character, {}) 

def main(): 
    tree={} 
    add_to_tree(tree, 'abc') 
    print tree 

if __name__=="__main__": 
    main() 

Что не ясно мне:

1. почему это возвращение {a:{b:{c:{}}}} вместо {a:{},b:{},c:{}}?

2. Я проверил код через this, который дает визуализацию. После повторения, хотя «a» я получаю tree = {'a':{}}, root = {}, то после «b» я получаю tree = {a:{b:{}}}, root={}. Неясно, какая переменная содержит ссылку на {b:{}}, которая присваивается {a:{}}, чтобы изменить ее на {a:{b:{}}}?

Answer 1

Вы переназначение корень вновь созданного Dict для каждого символа, измените эту строку:

root = root.setdefault(character, {}) 

Чтобы становится:

root.setdefault(character, {}) 

Это дает желаемый результат (обратите внимание, что Dict являются неупорядоченными):

{'a': {}, 'c': {}, 'b': {}}