[Python-ideas] Tree as a data structure (Was: Graph class)

[Jim Jewett]

On 12/19/12, anatoly techtonik <techtonik at gmail.com> wrote:
> On Sun, Dec 16, 2012 at 6:41 PM, Guido van Rossum <guido at python.org> wrote:

>> I think of graphs and trees as patterns, not data structures.

> In my world strings, ints and lists are 1D data types, and tree can be a
> very important 2D data structure.

Yes; the catch is that the details of that data structure will differ
depending on the problem.  Most problems do not need the fancy
algorithms -- or the extra overhead that supports them.  Since a
simple tree (or graph) is easy to write, and the fiddly details are
often -- but not always -- wasted overhead, it doesn't make sense to
designate a single physical structure as "the" tree (or graph)
representation.  So it stays a pattern, rather than a concrete data
structure.

> Speaking of tree as a data structure, I assume that it has a very basic
> definition:

> 1. tree consists of nodes
> 2. some nodes are containers for other nodes

Are the leaves a different type, or just nodes that happen to have
zero children at the moment?

> 3. every node has properties

What sort of properties?
A single value of a given class, plus some binary flags that are
internal to the graph implementation?
A fixed set of values that occur on every node?  (Possibly differing
between leaves and regular nodes?)
A fixed value (used for ordering) plus an arbitrary collection that
can vary by node?


> More ideas:

>   [ ] every element in a tree can be accessed by its address specificator
> as 'root/node[3]/last'

That assumes an arbitrary number of children, and that the children
are ordered.  A sensible choice, but it adds way too much overhead for
some cases.

(And of course, the same goes for the overhead of balancing, etc.)

-jJ