Trees

[Mario Figueiredo]

Hello Terry,

> It is not play with words. A tree is a recursive - nested -
> hierachical
> data structure with the restriction of no cycles or alternate
> pathways.
> Python collections whose members are general objects, including
> collections, can be nested.  The resulting structures *are* tree
> structures, if not more general directed graphs.  They are quite
> commonly used in Python.

Let's get somethig clear. Tree data structures have an associated logic that 
justifies their name as a de facto Tree Data Structure. If your low level 
description was how you described a tree to someone new to the concept, they 
would be none the wiser about what a Tree represents or what uses they could 
have for them. This logic is no different from the internal logic that diferentiates 
a dictionary from a list and helps carry their distinct operations. Despite 
a dictionary being nothing more than a glorified list.

Just as well, tree data structures only make sense along with their logic. 
Storage, traversal, insertion, random searches, retrieval, etc, all these 
algorithms are what in the end define a Tree data structure and what will 
help categorize it. Python standard library doesn't have any tree data structure 
implementation. It has lists, dictionaries, and other base structures that 
in the end will help define storage patterns for tree data structures. And 
that's it.

A simple binary tree needs to be implemented in Python as a binary tree, 
if it wants to be recognized as such. All your code examples illustrate exactly 
that. And if you care about code reuse, you will want to define a number 
of associated algorithms to take advantage of your storage model and answer 
your performance or memory requirements. Along with your list pattern for 
storage, you will probably also want to implement an insertion/search/update/traversal 
algorithms. That's when you have a tree.