Binary Trees in Python

[[diegueus9] Diego Andrés Sanabria]

Hello!!!

I want know if python have binary trees and more?

[Roy Smith]

In article <ma***************************************@python. org>,
[diegueus9] Diego Andrés Sanabria <ze****@gmail.com> wrote:

Hello!!!

I want know if python have binary trees and more?

Python does not come with a tree data structure. The basic data structures
in Python are lists, tuples, and dicts (hash tables).

People who are used to C++'s STL often feel short-changed because there's
not 47 other flavors of container, but it turns out that the three Python
gives you are pretty useful. Many people never find a need to look beyond
them.

If you do need to go beyond them, it's easy enough to build your own.
Here's one example of a binary ordered tree that you might find useful:

http://aspn.activestate.com/ASPN/Coo.../Recipe/286239

[Ramza Brown]

[diegueus9] Diego Andrés Sanabria wrote:

Hello!!!

I want know if python have binary trees and more?

Yea, binary trees are more data structures as opposed to libraries:

Here is one approach ( remove the 'java.lang' stuff)

http://www.newspiritcompany.com/BinaryTreePyNew.html

--
Ramza from Atlanta
http://www.newspiritcompany.com

[Steve M]

[diegueus9] Diego Andrés Sanabria <[e-mail]> wrote:

Hello!!!

I want know if python have binary trees and more?

You might be interested that ZODB comes with some B-tree
implementations. They can be used alone or you can persist them in the
ZODB quite easily.

http://www.zope.org/Wikis/ZODB/FrontPage

[Jorgen Grahn]

On Sat, 20 Aug 2005 15:19:55 -0400, Roy Smith <ro*@panix.com> wrote:

In article <ma***************************************@python. org>,
[diegueus9] Diego Andrés Sanabria <ze****@gmail.com> wrote:

Hello!!!

I want know if python have binary trees and more?

Python does not come with a tree data structure. The basic data structures
in Python are lists, tuples, and dicts (hash tables).

People who are used to C++'s STL often feel short-changed because there's
not 47 other flavors of container, but it turns out that the three Python
gives you are pretty useful. Many people never find a need to look beyond
them.

Uh, the STL has seven flavors:
- vector
- deque
- list
- set
- map
- multimap
- multiset
so that's not too bad for a static language. Each of them
is vital for some purpose, but vector and map are by far the
most commonly used.

Neither C++ nor Python has tree structures in their standard libraries. I
assume that's because there is no single interface that is proven to suit
everybody's needs.

/Jorgen

--
// Jorgen Grahn <jgrahn@ Ph'nglui mglw'nafh Cthulhu
\X/ algonet.se> R'lyeh wgah'nagl fhtagn!

[François Pinard]

[Jorgen Grahn]

Neither C++ nor Python has tree structures in their standard
libraries. I assume that's because there is no single interface that
is proven to suit everybody's needs.

It is already easy writing "tree constants" using recursive tuples or
lists. To process simple trees in Python, I usually subclass some
Node type from list, and write the traversal methods that suit the
application. The sub-classing already allow for indexing sub-nodes by
"self[index]", and iterating over all by "for subnode in self:", etc.
In my experience, it all goes pretty easily, while staying simple.

However, things related to balancing, finding paths between nodes, or
searching for patterns, etc. may require more work. There are surely
a flurry of tree algorithms out there. What are the actual needs you
have, and would want to see covered by a library?

--
François Pinard http://pinard.progiciels-bpi.ca

[Jeff Schwab]

Jorgen Grahn wrote:

On Sat, 20 Aug 2005 15:19:55 -0400, Roy Smith <ro*@panix.com> wrote:

In article <ma***************************************@python. org>,
[diegueus9] Diego Andrés Sanabria <ze****@gmail.com> wrote:

Hello!!!

I want know if python have binary trees and more?
Python does not come with a tree data structure. The basic data structures
in Python are lists, tuples, and dicts (hash tables).

People who are used to C++'s STL often feel short-changed because there's
not 47 other flavors of container, but it turns out that the three Python
gives you are pretty useful. Many people never find a need to look beyond
them.

Uh, the STL has seven flavors:
- vector
- deque
- list
- set
- map
- multimap
- multiset

There are others, e.g. std::valarray. There are also adapters that use
the above templates to implement other structures, adding or limiting
functionality as appropriate; e.g., std::heap and std::stack.
so that's not too bad for a static language. Each of them
is vital for some purpose, but vector and map are by far the
most commonly used.

Neither C++ nor Python has tree structures in their standard libraries. I
assume that's because there is no single interface that is proven to suit
everybody's needs.

Hmmm... I guess I never noticed the lack. C++ has structures or
language features that represent most of the common things trees are
typically used to implement. Of course, a "tree" can be represented in
so many ways, it's more of a design pattern than a data structure. :)

[Chris Smith]

>>>>> "[diegueus9]" == [diegueus9] Diego Andrés Sanabria <diegueus9> writes:

[diegueus9]> Hello!!! I want know if python have binary trees and
[diegueus9]> more?

The latest boost, 1.33, says it has a python wrapper for the boost
graph library.
Boost explicitely states that it's experimental, but my emerge was
successful.
See http://boost.org
-Chris

[Jorgen Grahn]

On Sun, 21 Aug 2005 08:52:10 -0400, François Pinard <pi****@iro.umontreal.ca> wrote:

[Jorgen Grahn]

Neither C++ nor Python has tree structures in their standard
libraries. I assume that's because there is no single interface that
is proven to suit everybody's needs.

It is already easy writing "tree constants" using recursive tuples or
lists. To process simple trees in Python, I usually subclass some
Node type from list, and write the traversal methods that suit the
application. The sub-classing already allow for indexing sub-nodes by
"self[index]", and iterating over all by "for subnode in self:", etc.
In my experience, it all goes pretty easily, while staying simple.

However, things related to balancing, finding paths between nodes, or
searching for patterns, etc. may require more work. There are surely
a flurry of tree algorithms out there. What are the actual needs you
have, and would want to see covered by a library?

I have no needs, actually ... but yes, the things you mention (balancing,
traversal ...) were the ones I was thinking about.

/Jorgen

--
// Jorgen Grahn <jgrahn@ Ph'nglui mglw'nafh Cthulhu
\X/ algonet.se> R'lyeh wgah'nagl fhtagn!