Storing and searching nodes of a tree

[Marc 'BlackJack' Rintsch]

In <1179243655.596897.6450 at e51g2000hsg.googlegroups.com>,
jm.suresh 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