Search

A compact searchable representation of static binary trees is presented that can be traversed in O( h ) time where h is the height of the tree. The space requirement for a tree with n nodes is less than 2.5 n +( h −1)(2+log 2 (( n −1)/( h −1))) bits. The access time per node is in O(1). The scheme uses a cumulative-count technique to map the nodes at each level in the tree into sequential memory locations. The mapping requires the nodes to be of uniform size.

We consider the problem of finding a k -median in a directed tree. We present an algorithm that computes a k -median in O (Pk 2 ) time where k is the number of resources to be placed and P is the path length of the tree. In the case of a balanced tree, this implies O (k 2 n log n) time, in a random tree O (k 2 n 3/2 ), while in the worst case O (k 2 n 2 ) . Our method employs dynamic programming and uses O (nk) space, while the best known algorithms for undirected trees require O (n 2 k) space.

The tree-layout problem is to compute the coordinates of nodes of a tree so that the tree, when drawn on a piece of paper, appeals to human understanding. The tree-layout problem, which seems inherently sequential at the first glance, can be solved with a data-parallel algorithm. It takes O( height × log width ) time on width processors when proper communication links between processors are available, where height and width are the height and width of the tree, respectively. The layout calculated by the algorithm has the minimum width.

We show that the complete binary tree with n > 8 leaves can be embedded in the hypercube with n nodes such that: paths of the tree are mapped onto edge-disjoint paths of the hypercube, at most two tree nodes (one of which is a leaf) are mapped onto each hypercube node, and the maximum distance from a leaf to the root of the tree is log2n + 1 hypercube edges (which is optimally short). This embedding facilitates efficient implementation of many P-RAM algorithms on the hypercube.

We discuss the problem of ranking nodes of a tree, which is a restriction of the general node coloring problem. A tree is said to have rank number k if its vertices can be ranked using the integers 1, 2,…,k such that if two nodes have the same rank i, then there is a node with rank greater than i on the path between the two nodes. The optimal rank number of a tree gives the minimum height of its node separator tree. We present an O(n log n) algorithm for optimal node ranking of trees.

We show that an n-node complete binary tree can be embedded into an n-node linear array such that the maximum edge length is n log n , and the distribution of the tree nodes is regular in the sense that if each node in the tree array is a finite-state machine and each edge is a communication channel, then the message exchanges (i.e., communication) among the tree nodes can be easily simulated by the linear array which has also finite-state machines for its nodes. The embedding is optimal with respect to the maximum edge length. The motivation for this is the proof of the following result: every cellular (or (log n)-depth iterative) tree array running in T(n) time can be simulated by a linear cellular (or iterative) array in nT(n) log n time.

The binary tree is an important interconnection pattern for VLSI chip layouts. Suppose that the nodes are separated by at least unit distance and that a wire has unit width. The usual layout of a complete binary tree with n leaves takes chip area ( nlogn), but it can be arranged that all the leaves are on the boundary of the chip. In contrast, the “recursive H” layout has area of order n, but has only O( p n) leaves on the boundary. Thus, the recursive H layout enjoys a small area at the expense of a small number of possible I/O ports. This note shows that it is not possible to design a complete binary tree layout with area O(n) and all leaves on the boundary. More precisely, if the boundary of the chip is a convex plane curve and the leaves on the boundary are separated by at least unit distance, then area of order nlogn is necessary just to accomodate all the wires.