Три реализации в Python, ссылка на объект

Question

Я смотрю на следующую реализацию Trie в 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. Я провел код через это, которое дает визуализацию этого. После итерации, хотя "а" я получаю tree = {'a':{}}, root = {} затем после "б" я получаю tree = {a:{b:{}}}, root={}, Что не ясно, так это то, что переменная содержит ссылку на {b:{}} который присваивается {a:{}} изменить его на {a:{b:{}}}?

Answer 1

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

root = root.setdefault(character, {})

Становится:

root.setdefault(character, {})

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

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