Re: [boost] proposal for tree container

Subject: Re: [boost] proposal for tree container
From: Gottlob Frege (gottlobfrege_at_[hidden])
Date: 2009-07-16 02:50:53

On Thu, Jul 16, 2009 at 2:18 AM, Ross Levine<ross.levine_at_[hidden]> wrote:
> On Thu, Jul 16, 2009 at 12:26 AM, Gottlob Frege <gottlobfrege_at_[hidden]>wrote:
>
>> What are the requirements of 'tree-ness'?  Containers like
>> std::map/list/deque/vector/... all have well defined requirements.
>
>
> This is one of those questions that seems trivial but is very important to
> actually lay out.

Glad you agree.  Many people I work with just like to run ahead and
(blindly, in my opinion) type code as fast as they can!

<cut/paste>
> Someone check my work.

OK! My pure-math proof/theorem/formalism hat popped onto my head, but
I'll try not to get too picky.

>
> Here's what I can come up with:
>
> 1. A tree is a node-based container. If nonempty, every node has exactly one
> parent, except for one node. This node is called the _root node_.

node, parent, container, etc undefined.
I can live with that.  Can't define everything!

> 2. Every node has a finite, non-negative number of children. A node's
> children is the same as the set of nodes which have that node as a parent.

In fact, this is the definition of 'child'.

> Corollary: There is exactly one simple path between any two different nodes
> (a simple path is a path that has no repeated vertices).

vertex undefined but I think you meant 'node' :-)
simple path undefined
  this is actually worth defining, somewhat (in my head at least),
because, in addition to these requirements, there is nothing stopping
a tree from having 'extra' edges (ie linking children together) but
obviously these don't form a part of the 'tree-ness' so
shouldn't/can't be used as part of a path. (that's just my head trying
to imagine how the corrollary could be false, and closing the
loop-holes)

> Corollary: A node's parent lies on the path between it and the root node.
>
>
> Definitions:
> 1. If any node in tree T have at most K children, then T is a _K-ary tree_.

'have at most' at the moment, or 'can have at most' at any time?
Maybe it depends on context? (ie T is, at the moment, a K-ary tree...?
Or would it better to say, in those case, "T is, at the moment, *like*
a K-ary tree, or can be considered a K-ary tree for the purposes of
blah blah blah...")

> 2. A K-ary tree is _full_ if every node has either 0 or K children.
> 3. The _distance_ between two nodes, A and B, is the number of edges in the
> path that connects A and B.
> 4. The _height_ of tree T is equal to the maximum distance from the root
> node to any other node.
> 5. The _degree_ of a node is the number of children, plus the number of
> parents. Since every node (except the root) has exactly one parent, the
> degree of a non-root node is the number of children plus 1.

what's 'degree' typically used for? is it more for graphs?  Seems
useless as a concept of its own, separate from 'number of children',
at least for trees.  (just wondering)

> 6. A node is a _leaf_ node if it has no children.
> 7. An _ordered tree_ is a tree in which the position of the nodes, and the
> order of a node's children, is significant.
>
> That's all I can think of right now. Someone check my work.

excellent stuff.  I can't think of any other requirements - anything I
could consider adding just makes it a specialization of tree.

I guess it might be useful to mention ('corollary') that a tree is
thus a type of graph, more specifically a type of DAG. I'm trying to
imagine if there are interesting cases between 'tree' and 'DAG' that
are worth thinking about...

Tony