Storing and searching nodes of a tree

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

On May 15, 9:25 pm, Marc 'BlackJack' Rintsch <bj_... at gmx.net> wrote:
> In <1179243655.596897.6... at e51g2000hsg.googlegroups.com>,
>
> jm.sur... at no.spam.gmail.com wrote:
> > 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?
>
> No it's O(1).  Dictionaries are implemented as hash tables.  You may write
> the condition as:
>
>     while path and path not in tree:
>
> That's a little easier to read and a bit faster too as a method lookup is
> spared.
>
> Ciao,
>         Marc 'BlackJack' Rintsch

Wow :) , thanks.
-
Suresh