Drawing Trees:Level Layout for Binary Trees

Level Layout for Binary Trees

For ordered binary trees, the first linear time algorithm satisfying (A1) to (A5) was presented by Reingold and Tilford [17]. The algorithm follows the divide and conquer principle implemented in form of a postorder traversal of a tree T = (V, E) and places the nodes on grid units. For each v ∈ V with left and right child wleft , wright the algorithm computes layouts for the trees T (wleft ) and T (wright ) up to horizontal translation. When v is visited, the drawing of the right subtree T (wright ) is shifted to the right such that on every level l of the subtrees the rightmost node vleft of T (wleft ) and its neighbor, the leftmost node vright of T (wright ) are separated at least by two or three grid points. The separation value between vleft and vright is chosen such that v can be centered above the roots of T (wleft ) and T (wright ) at an integer grid coordinate.

Shifting T (wright ) is partitioned into two subtask: first, determining the amount of shift and second, performing the shift of the subtree. To determine the amount of shift, define the left contour of a tree T to be the vertices with minimum x-coordinate at each level in the tree. The right contour is defined analogously.

For an illustration, see Figure 45.2, where nodes belonging to the contours are shaded. To place T (wright ) as close to T (wleft ) as possible, the right contour of T (wleft ) and the left contour of T (wright ) are traversed calculating for every level l the amount of shift to separate the two subtrees on that specific level l. The maximum over all shift then gives the displacement for the trees such that they do not overlap. Since each node belongs to the traversed part of the left contour of the right subtree at most for one subtree combination, the total number of such comparisons is

linear for the complete tree.

In order to achieve linear running time it must be ensured that the contours are traversed without traversing (too many) nodes not belonging to the contours.

This is achieved by introducing a thread for each leaf of the subtree that has a successor in the same contour.

The thread is a pointer to this successor.

See Figure 45.2 for an illustration where the threads are represented by dotted arrows. For every node of the contour, we now have a pointer to its successor in the left (right) contour given either by its leftmost (rightmost)

child or by the thread. Finally, to update the threads, a new thread has to be added whenever two subtrees of different height are combined.

Once the shift has been determined for T (wright ) we omit shifting the subtree by updating the coordinates of its nodes, since this would result in quadratic running time. Instead, the position of each node is only determined preliminary and the shift for T (wright ) is stored at wright as the modifier mod (wright ) (se e[24]). Only mod (wright ) and the preliminary x-coordinate prelim(v) of the parent v are adjusted by the shift of T (wright ). The modifier of wright is interpreted as a value to be added to all preliminary x-coordinates in the subtree rooted at wright , except for wright itself. Thus, the coordinates of a node v in T in the final layout is its preliminary position plus the aggregated modifier modsum(v) given by the sum of all modifiers on the path from the parent of v to the root. Once all preliminary positions and modifiers have been determined the final coordinates can be easily computed by a top-down sweep.

THEOREM 45.1 [Reingold and Tilford [17]] The layout algorithm for binary trees meets the aesthetic requirements (A1)–(A5) and can be implemented such that the running time Proof By construction of the algorithm it is obvious that the algorithm meets (A1)–(A5). So it is left to show that the running time is linear in the number of nodes. Every node of T is traversed once during the postorder and the preorder traversal. So it is left to show that the time needed to traverse the contour of the two subtrees T (wleft ) and T (wright ) for every node v with children wleft and wright is linear in the number of nodes of T over all such traversals.

It is obviously necessary to travel down the contours of T (wleft ) and T (wright ) only as far as the tree with lesser height. Thus the time spent processing a vertex v in the postorder traversal is proportional to the minimum of the height of h(T (wleft )) and h(T (wright )). The running time of the postorder traversal is then given by:

The sum �v∈T min{h(T (wleft )), h(T (wright ))} can be estimated as follows. Consider a node w that is part of a contour of a subtree T (wleft ). When comparing the right contour of T (wleft ) and the left contour of T (wright ) two cases are possible. Either w is not traversed and therefore will be part of the contour of T (v) or it is traversed when comparing T (wleft ) and T (wright ). In the latter case, w is part of the right contour of T (wleft ) and after merging T (wleft ) and T (wright ) the node w is not part of the right contour of T (v). Thus every node

of T is traversed at most twice and the total number of comparisons is bounded by |V |.

We do not give the full algorithm for drawing binary trees here. Instead, the layout algorithm for n-ary trees is given in full length in the next section. The methods presented there are an expansion of Reingold and Tilfords algorithm to the more general case and still proceed for binary trees as described in this section.