CODEWITHSUNDEEP
data-structuresarchitecturetreenodestreenode
Alex Altair
Alex Altair

Reputation: 3715

Are tree data structures usually defined in terms of nodes or subtrees?

I'm studying tree traversal algorithms by writing a tree library for Ruby. In terms of basic architecture, there seem to be two reasonable choices;

  1. There exist only trees. Trees have a root value, and sub-trees.
  2. There exist trees and nodes. A node has a value, and children nodes. A tree has a root node, and sub-trees. The root nodes of the sub-trees are the children nodes of the tree's root node.

Is one of these designs more common? During development of this library, will it become "obvious" that 1) is too naive, or that 2) is unnecessarily redundant? The intended purpose of this library is general use; I'd like it to be usable for huge trees, or binary search trees, or parsing trees, etc.

I can think of other less reasonable architectures;

3) Trees are collections of nodes. A tree has a root node. A node has a value, and children. There is no concept of sub-tree.

4) If I chose a nodes-only architecture, I couldn't reasonably ask a node things like "how many nodes are in this tree", or "balance this tree".

Upvotes: 0

Views: 161

Answers (1)

Jim Mischel
Jim Mischel

Reputation: 133975

I've worked with trees in two ways. The first one is that there are only nodes, which have properties (typically a data reference, child references, and possibly a parent reference), and behaviors. This can be nice to work with because there isn't a separate Tree data type. But it has disadvantages because the empty tree is expressed by a null node. So your code is filled with things like:

if (tree == null)
    tree = node;
else
    tree.Insert(node);

That check for null makes for hard to read code.

A benefit, though, is that you can treat any node as a tree. For example you could write:

tree.Right.CountNodes();

Which would return the node count for the right subtree.

So create a Tree data structure that contains nodes. Now, nodes are just data and the tree has the behaviors. Internally there is a root node that can be null, and the Tree behaviors have to deal with it. But client code can just write:

tree.Insert(node);

You can still count nodes in a subtree, though:

tree.CountNodes(node);  // counts nodes in the subtree rooted at node

Which design you use is largely a matter of style. I've found it easier to build a Tree data structure that abstracts away the complexities of dealing with nodes and such.

Upvotes: 1

Related Questions