
Boost : 
Subject: Re: [boost] proposal for tree container
From: Gottlob Frege (gottlobfrege_at_[hidden])
Date: 20090716 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 'treeness'? 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 puremath 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 nodebased 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, nonnegative 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 'treeness' 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
loopholes)
> 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 _Kary 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 Kary tree...?
Or would it better to say, in those case, "T is, at the moment, *like*
a Kary tree, or can be considered a Kary tree for the purposes of
blah blah blah...")
> 2. A Kary 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 nonroot 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk