I've been pondering this reply for a while.
There are so *many* kinds of tree.
There are rooted trees (very popular in computing) and unrooted trees (what
you get from some phylogenetic reconstructions and of course the spanning
tree of a graph).
There are trees with and without parent links.
There are inverted trees with child->parent but no parent->child links.
There are fully threaded, half threaded, and unthreaded trees.
There are binary, ternary, ..., and rose trees.
There are ordered and unordered trees.
There are unbalanced, height balanced, and weight balanced trees.
There are trees with shareable substructures and trees where everything is
locked into place (the DOM).
There are trees with no fingers, single fingers, and multiple fingers.
There are trees that do not support concurrency, that support concurrent
lookup, and that support concurrent changes.
The model described at your link is pretty close to the DOM except for
modelling the child sequence of a node as an array instead of a doubly
linked list. This means that while you *can* implement "left/right sibling"
- if no parent, return nil
- find index of node in parent's child array
- if at beginning/end return nil
- otherwise report previous/next element of parent's child array
but it takes O(#children) time instead of O(1) time.
For argument's sake, let us imagine a storage model in which
- an object with n slots takes n+1 words
- an array with n elements takes n+2 words
and let us consider a node with n children.
Your structure (label, array of children, parent) takes 6+n words in
addition to the space needed by the child nodes themselves. A (label,
first child, next sibling) structure takes 4 words. With a grand total of
M nodes, your structure takes 7M words, while the other takes 4M words.
The two data structures can represent exactly the same abstract values, but
they are good at different things.
My library, for example, contains
Tree
TreeWithParent
KeyedTree
KeyedTreeWithParent
AssociationTree
AssociationTreeWithParent
SortedSet (a splay tree)
SortedBag (a splay tree)
SortedDictionary (a splay tree)
TernarySet (a ternary search tree)
TernaryBag (ditto)
TernaryDictionary (ditto)
The sets, bags, and dictionaries *hide* the internal trees; what matters is
that they are sets, bags, and dictionaries, not that they are trees.
With such a great variety, I think it would be most useful to pick a *task*
for which some kind of tree is useful and implement *that* kind of tree and
use it for *that* task. As one possible example, consider the Document
Object Model,
which can be implemented using (parent, first child, last child, previous
sibling, next sibling) with node-specific additional data, and build an
implementation of CSS selectors atop it.
plus a number of other kinds of trees, including
On Sun, 30 Jun 2019 at 22:39, Smiljana Knezev <smilja.kne...@gmail.com>
wrote:
> Hello everyone,
>
> Next week I'm consulting with mentors on how to design an API for Tree
> data structures. I was researching a bit and wrote this blog post as a
> starting point:
> https://pharokeepers.github.io/pharo/2019/06/30/Application-Programming-Interface-API.html
>
> Feedback and ideas are more than welcome :)
>
> Best regards,
> Smiljana Knezev
>
