searching algorithm

[James Stroud]

Gordon Airporte wrote:
> 
>> For the above (abrideged) dictionary, you would generate (use a
>> fixed-width "programmers" font so the tree looks good):
>>
>>                  a
>>                  |
>>                  b
>>                  |
>>                  s
>>                 / \
>>                i   o
>>               /   / \
>>              n   l   r
>>             /   / \   \
>>            t   u   v   b->(absorbirati, crpisti)
>>           /    |   |
>> (pelin)<-h     t   e->(odrije?iti, osloboditi)
>>          |     |
>> (pelin)<-e     e->(apsolutan, apsolutni kod)
>>
>> As the user enter letters, you just march down the tree, printing
>> all the words held in leaf nodes held in the current node.
>>
> 
> Call me dense, but how does one do this in Python - which doesn't have 
> pointers? Dictionaries with dictionaries within dictionaries... (with 
> each letter as the key and the its children as values) is going to be 
> extremely space inefficient, right?

How would this be significantly more space inefficient than "pointers"? 
The implementation of the dict would, in fact, itself be pointers, where 
each key (same memory requirement if using pointers) is mapped to a 
pointer to a dict node or a pointer to a leaf, same as with a more "low 
level" construction. A printout of the graph as a dict might look a 
little ugly, though.

I could be wrong, however.

James