Storing and searching nodes of a tree

[jm.suresh@no.spam.gmail.com]

Hi, I have a tree data structure and I name each node with the
following convention:

a
|---aa
|    |--- aaa
|    |--- aab
|
|---ab
|
|---ac


I use these names as keys in a dictionary, and store node's data.
Now given a name like "abc", I want to find the key with the following
rule:
If the key exists return the value
If the key does not exist, return the value of the leaf node whose
name is in the given name. For, "abc", it is "ab" . For, "ad", it is
"a".

I suppose there must be a simpler solution to this problem. I
implemented it like this:
d = {'a':0, 'aa':12, 'ab':43, 'aaa':22, 'aab':343, 'ac':33}
name = 'abc'
key = max( [ x for x in d.iterkeys() if x in name] )
value =  d[key]

I can change the data structure from dictinory to tuple of key,value
pairs or any thing, and afford to keep them in a particular order. Is
there any way I can speed up this as I have to do this for around 4000
times with tree size being ~5000.

-
Suresh