Boost logo

Boost :

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!

> 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

> 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...


Boost list run by bdawes at, gregod at, cpdaniel at, john at