trie Implementierung in Python, Objektreferenz

Question

im bei der folgenden Umsetzung trie in Python suchen:

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() 

Was mir nicht klar ist:

1. warum es zurückkehrt {a:{b:{c:{}}}} statt {a:{},b:{},c:{}}?

2. Ich lief den Code durch this, die eine Visualisierung davon gibt. Nachdem ich 'a' durchlaufen habe, bekomme ich tree = {'a':{}}, root = {}, dann nach 'b' bekomme ich tree = {a:{b:{}}}, root={}. Was nicht klar ist, ist, welche Variable den Verweis auf {b:{}} hält, der {a:{}} zugewiesen wird, um es in {a:{b:{}}} zu ändern?

Answer 1

Sie sind für jedes Zeichen in die neu geschaffene dict Wurzel Neuzuweisung, ändern Sie diese Zeile:

root = root.setdefault(character, {}) 

Um wird:

root.setdefault(character, {}) 

Dadurch wird die gewünschte Ausgabe gibt (beachten Sie, dass dict sind ungeordnet):

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