This section contains the design considerations for the generic binary tree.
The following are orthogonal properties of a tree:
We shall now select a subset of these combinations to implement in our tree abstraction.
The trees with heterogeneous node types are mainly seen as compile-time expression trees (e.g. matrix expressions). They can be best implemented with specialized techniques (e.g. Boost Proto). Thus we shall now concentrate on trees with homogeneous types.
I have yet to see a data structure for which having more than two children were fundamental. For an example, consider octrees. It is possible to construct a fast ray-traversal algorithm for this data structure. However, it won’t generalize to higher-dimensions because the subdivision increases the number of nodes exponentially. In addition, the algorithms are unnecessarily complex simply because they are doing many things at once (subdiving space in all n directions at once). In contrast, one obtains much cleaner, simpler and faster algorithms by using kd-trees instead (which are binary).
Here is another example of how having more than 2 children can affect the asymptotic resource and performance requirements. Consider the in-order traversal of a tree when there can be more than 2 children in a node. Then each node along the path from the root to the current node requires bookkeeping information to know which child to visit after returning back to a node from another child. Depending on the depth of the path, this may mean anything between a logarithmic and a linear storage (w.r.t. the number of nodes in the tree).
On the other hand, branching is essential. A maximum of 2 children is the minimum amount of children to open up the power of hierarchical data structures. A maximum of 1 child gives a linked list instead. Thus we shall fix the number of children per node to 2.
One important application of trees is to represent (run-time) expressions. A binary tree can represent nullary, unary prefix, unary postfix, and binary infix operators. Operators with more than two operands are rare. At first it might seem that a binary tree is not natural for the unary operators since one of the children is wasted. However, consider representing a prefix (postfix) operator as a node which has only the right (left) child. Then if you think of going through the nodes in in-order, the prefix (postfix) operator actually comes before (after) its operand, which seems logical. The in-order traversal through such an expression tree ‘reads’ the expression (as a string) from left to right. In addition, a right-rotation can be used to convert (-n)! to -(n!), so that tree rotations also make sense in this representation.
A reoccuring feature in trees is that they track some specific nodes so that they can refer to them in constant time. These nodes are the root node, the leftmost node, and the rightmost node. For example, if the tree is actually an ordered tree, then the leftmost node is the minimum node, and the rightmost node is the maximum node. The root node is the starting point for many hierarchical algorithms (e.g. kd-tree nearest neighbors searching). On the other hand, I haven’t seen any other nodes treated specially in this way. Thus tracking these nodes should cover a lot of uses (it is also very simple).
In the user interface, the children should be referred to by integer indices 0 and 1, and not by ‘left’ and ‘right’. This allows to efficiently exploit symmetries in algorithms (such as in the red-black tree implementation). In particular, the sibling of a node with the index ‘i’ is given by ‘i!’. Once the index-based interface is in place, the ‘left’ and ‘right’ functions can be added too for convenience.
A reoccuring design is to make a node an independent object, not encapsulated as a part of tree structure, and such that it contains links to its children. Here the memory of the node is usually managed with a smart pointer. This seems like a flexible design, but it is not. Some of the flaws in this approach are:
Using std::shared_ptr, it is not possible to create a working implementation of a tree which also offers links to parents. On the one hand, when constructing an expression, you don’t yet have the access to a containing shared_ptr, and thus can’t use a shared_ptr or a weak_ptr for the parent links. On the other hand, a raw pointer can not be used either, because it can not be converted to a shared_ptr later (if you do construct a shared_ptr, its reference count does not refer to the previous reference count). This could be fixed by using intrusive reference counting instead (embedding the reference counting into the node itself).
A node can be a child of many nodes at the same time. However, usually a node can have only one parent. If sharing subtrees is a point in this design, it is certainly not well realized. Subtrees are better shared by using iterators to them.
There is nothing to prevent you from creating loops in the ‘tree’. Thus the design actually reflects a graph (although with a limited amount of edges per node), and not a tree. Having a loop like this will mess up most of the tree algorithms.
A sentinel node can not be naturally incorporated into the implementation. A sentinel node is important because it gets rids of special cases in tree algorithms near the tree boundaries.
When inserting new nodes, the following use-cases come to mind.
1) Predetermined position.
In an ordered binary tree, for example, there is a unique position to which a new node should be created to contain the inserted value. The tree might be empty at insertion.
2) User-determined position, the tree always contains a root node.
In a kd-tree subdividing space, for example, the user determines the node the subdivide. Both children are then created at the same time. The tree always contains the root node, so that it can be subdivided.
3) User-determined position, possibly empty tree.
We want to support both the creation of the kd-tree and the ordered binary tree. To generalize, the creation position must be determinable by the user by a node-child pair. The problematic thing here is to specify how the root node is created. The root node could be created as a child of a sentinel node. But then it isn’t clear what the left-right child distinction means here. A way to solve this is to make the creation of the root node special, i.e. provide a function createRoot(). This is the approach we adopt.
We would like to be able to move sub-trees around in constant time, even between different trees. The design choice of how to represent the empty children references interacts with this requirement.
1) Unique sentinel references
In this option all empty children references point to the unique sentinel node of the tree. Now moving a tree into another tree requires to reassign the sentinel nodes to match the sentinel node of the assigned-to tree. This requires time linear in the number of moved nodes.
2) Null references, and a sentinel reference at the right child of the rightmost node
This option would make iterators work correctly, and also enable fast moves. However, having null references means that the internal algorithms will be much complicated since one can not assume a child of a child exists. What’s worse is that this complication also affects the user’s algorithms. The non-uniformity of having a single exceptional reference would probably also bite back.
4) Shared sentinel references
In this option sentinel nodes are used everywhere, as in option 1, but the sentinel nodes can be shared between trees, and a single tree can contain multiple different sentinel nodes. The rightmost node is always kept linked to the local sentinel node so that iterators work correctly.
The different sentinel nodes compare unequal, that is, as they would normally compare as node pointers. Doing otherwise would be a non-uniformity. Also, their unequal comparison might be needed when storing the iterators in containers.
As otherwise, detecting a sentinel node is done by testing
for a local criterion, as in if (iter.isSentinel()). The
test if (iter == tree.end()) is also correct when using the
iterators as a sequence, but not when traversing the tree
in free manner, since then the sentinel references might not
be to tree.end(). This represents a small trap in this
approach.
This approach requires that each sentinel node is reference counted.
First assume a tree keeps up a list of ‘keep-alive’
shared_ptrs to all the sentinel nodes referenced in it.
It is then difficult to think of a way to cull off these
keep-alive pointers automatically when the corresponding
sentinel nodes are no longer used in a tree. I can also
imagine that there is a strategy to grow the number of
keep-alive pointers unboundedly using only a bounded amount of nodes.
One could go a step further to change the tree child references
to shared_ptr. But this takes much of extraneous resources.
A much better way is to use specially crafted intrusive reference counting for the sentinel nodes. Here a reference count is stored alongside each sentinel node. The tree that creates the sentinel node adds one to the reference count in construction; that same tree decreases the reference count of its created sentinel node in its destruction. When constructing a node, the children will be set to point to the local sentinel node of the tree. This will add two to its reference count. When a node is destructed, it will decrease the reference count of whichever sentinel nodes its children references are set to. If the reference count of a sentinel ever reaches zero, the sentinel node is destructed. The lifetime of a sentinel node of a tree might extend beyond the tree which created it.
Consider offering a function to arbitrarily move a sub-tree to another position inside the same tree. Then the following problem presents itself: it is possible to specify a position in the moved sub-tree itself. Being able to specify such ambiguous situations is a sign of bad design. This specification is possible because the sub-tree is already itself a part of something to which it should be attached to. This can only be avoided if the moving of a sub-tree is from a tree to another.
This suggests that the correct way would be to offer a way to move/insert a whole tree as sub-tree of another tree, and in the other direction, to offer a way to detach a sub-tree to its own tree. Conceptually, it is then not possible to specify a position in the moved tree itself (*). It is even trivial to check that the moved-to tree and moved-from tree are not the same object.
When detaching a sub-tree to its own tree, its size, leftmost node, and rightmost node need to be computed. Detaching a sub-tree is useful in its own, but when used in a detach-attach sequence, these computations can be most of the time avoided when moving a sub-tree inside a tree.
(*) The position in the moved-to tree is specified with an iterator. There is no efficient way to check whether the iterator actually points to the moved-to tree at all (one would have to traverse to the root to compare). This is a general problem with iterators and not specifically related to moving sub-trees.
Knowing whether one is on the left edge or the right edge requires O(h) time, where h is the length of the edge.
1) From left edge to middle
New leftmost is the parent of the moved sub-tree.
2) From left edge to right child of rightmost
New leftmost is the parent of the moved sub-tree. New rightmost needs to be scanned.
3) From middle to left-edge
New leftmost needs to be scanned.
4) From middle to middle
No changes needed.
5) From right edge to middle
Symmetric to 1.
6) From right edge to left child of leftmost
Symmetric to 2.
6) From middle to right-edge
Symmetric to 3.
Create a tree data structure such that