Storing and searching nodes of a tree

[Marc 'BlackJack' Rintsch]

In <1179233407.473173.259110 at h2g2000hsg.googlegroups.com>,
jm.suresh at no.spam.gmail.com wrote:

> 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.

What about this:

def search(tree, path):
    while path:
        result = tree.get(path)
        if result is not None:
            return result
        path = path[:-1]
    raise KeyError('path not on tree')

Ciao,
	Marc 'BlackJack' Rintsch