Storing and searching nodes of a tree

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

On May 15, 6:33 pm, Marc 'BlackJack' Rintsch <bj_... at gmx.net> wrote:
> In <1179233407.473173.259... at h2g2000hsg.googlegroups.com>,
>
>
>
> jm.sur... 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

If I have the tree in the dictionary, the code would like this,
def search(tree, path):
   while path and not(tree.haskey(path)):
         path = path[:-1]
   if path:
         return tree[path]
   else:
         raise KeyError('path not on tree')

Another qn -- dict.haskey() takes logn time, am I right?

-
Suresh