Restricting the shape of a tree
Previously, we've seen trees as a fairly general data structure, in which any node can have any number of subtrees associated with it. Sometimes, that generality is exactly what you want, because one use of a tree is in representing data that's genuinely hierachical, and whether nodes have fewer or more subtrees is purely a matter of what data you'd like to represent. For example, files and directories on a filesystem are (more or less) a hierachy; similarly, if you were writing software that needed to represent the organizational structure of a company (i.e., which people report to which other people, a structure that is quite often hierarchical), you might also use a tree to represent it. The shape of the tree would be constrained only by the data in question — the files and directories you wanted to store, or the organizational structure you wanted to represent.
However, trees have use in situations where the data is not itself hierachical; we can use the hierachy provided by trees to achieve other goals, such as making certain kinds of searches or rearrangements faster. To do that, though, we quite often have to restrict the shape of our tree somewhat, by limiting how many children each node can have, or by limiting the relative heights of sibling subtrees. How we limit the shape depends on why we're limiting it and what we'll gain from it; we'll see several examples of this going forward, beginning with the ones directly below.
N-ary trees
First, we'll consider trees that restrict their shape by strictly defining how many subtrees each node will have.
An N-ary tree of order N is either:
- empty
- a root node, along with exactly N disjoint subtrees, each of which is an N-ary tree of order N
There are a couple of things to notice about this definition. First of all, look at how similar it is to the original, general definition of a tree that we saw in the General Trees notes previously. The only meaningful difference — aside from the name of the data structure — is the restriction that every non-empty tree have exactly the same number of subtrees. Secondly, you should also take note that, just as before, empty trees are still trees, though they serve a more important purpose in an N-ary tree: Since every node must have exactly N subtrees, the fact that some of them can be empty is the only way you can approximate the idea of some nodes having more (meaningful) subtrees than others.
An N-ary tree is most commonly drawn like the one below, which is an N-ary tree of order 3 — which you might also call a ternary tree.
The circles are the root nodes of each subtree. These are sometimes called internal nodes, and are the ones where data is generally stored. The smaller-sized boxes denote empty subtrees, which are sometimes called external nodes; generally, external nodes store nothing, and might be implemented with a null pointer in C++, or with an object that has member functions that return default values when asked questions like "What is your height?" or "What is your value?"
The concept of an N-ary tree is a somewhat abstract one, but one that demonstrates a core idea: Sometimes you're better off if you can restrict how many children each node can have. That restriction is used to solve different kinds of problems. For example, as we'll see, we can use N-ary trees of order 2 to organize data so that it can be efficiently searched; we'll see these later as binary search trees. Meanwhile, N-ary trees of order 4 and 8 are sometimes used to organize spatial information — where objects reside in areas of two-dimensional or three-dimensional space — so that it is relatively cheap to determine, for example, which objects are near (or are possibly colliding with) which others; when used this way, they're typically called quadtrees or octrees.
To get our minds wrapped around this concept a little more completely, let's consider one example in more depth.
Binary trees
When we restrict the number of children of each node to exactly two, we've got what's called a binary tree, which we'll define by layering an additional concept atop the N-ary tree concept we've seen already.
A binary tree is an N-ary tree of order 2, in which one of the two subtrees of each internal node is the left subtree and the other is the right subtree.
Notice, then, that we've introduced an explicit notion of ordering here, in that one of the subtrees of each node is considered the "left" and the other is considered the "right." That's not an arbitrary choice; that will enable us to accomplish some things that would be very difficult if we didn't.
If we were to draw a binary tree, we might do it like this:
Note, also, that the presence of the external nodes is implied, so we need not actually draw them. As long as we draw parent/child relationships carefully, so that it's explicit whether each subtree is a left or right subtree, we don't need to draw the external nodes; for simplicity, I'll leave them off of our binary tree diagrams from here on out. The diagram above could also, then, be drawn this way:
