211L5BSolutions

Exercise

1. Let T be a tree. Prove that there do not exist two distinct paths from any given node x in T to the the root when one always moves from a node to its parent.

By definition, all nodes have exactly one parent. In a tree with a height of 1, the parent of any leaf is the root. Thus if the height of the tree is 1, there can not exist more than one path to the root. By induction, sub set of the tree, has only one path to the root, and that is through the parent of that subset.

3. Finish the proof of Proposition 1 for the cases (e1 − e2) and (e1 ⋆ e2).

Basis. If e is either an integer variable or an integer, then it is the root of its own tree.

Induction. Assume that e1 and e2 are expressions represented by expression trees Te1 and Te2 , respectively. Then the labeled tree T representing (e1 + e2) is defined as follows:

1. Create a new node r and declare r to be the root of the tree T . Label r with -.
2. Add edges from r to each of the roots r1 and r2 of trees Te1 and Te2 , respectively. Thus each ri is now a child of r, and we have made r to be a parent of each of the roots of the trees Te1 and Te2 .
3. Declare all nodes of trees T1 and T2 to be nodes of T .
4. Preserve all the labels of Te1 and Te2 .

Induction two. Assume that e1 and e2 are expressions represented by expression trees Te1 and Te2 , respectively. Then the labeled tree T representing (e1 + e2) is defined as follows:

1. Create a new node r and declare r to be the root of the tree T . Label r with *.
2. Add edges from r to each of the roots r1 and r2 of trees Te1 and Te2 , respectively. Thus each ri is now a child of r, and we have made r to be a parent of each of the roots of the trees Te1 and Te2 .
3. Declare all nodes of trees T1 and T2 to be nodes of T .
4. Preserve all the labels of Te1 and Te2 .

5. Let T be a tree. Compute the value h(T ) of T as follows:

• (a) If T consists of the root only then h(T ) = 0.
• (b) Assume that x1, . . ., xk are the children of the root r of T . Let T1, . . ., Tn be subtrees of T whose roots are x1, . . ., xn. Set h(T ) = max{h(T1), h(T2), . . . , h(Tn)} + 1, where max{h(T1), h(T2), . . . , h(Tn)} is the largest value among all h(T1), h(T2), . . ., h(Tn).

Prove by induction that h(T ) equals the height of the tree T .

Each sub tree is made up of the maximum height of their heighest sub tree +1.

Basis. If x1 is the root of its own tree. This tree has a height 0.

Induction Assume that x1 and x2 are both roots of their own tree with a height of 0. By making a new root and combining the trees x1 and x2 as two distinct children of the new root, the tree has a height of 1 and can be represented by (T1). The new height is calculated by taking the highest value of the two sub trees(in this case 0) and adding one.

When this process reaches the root, it is clear that the height of the tree T is equal to the maximum height of the roots sub trees plus one i.e. h(T).

7. Consider FindComponents(G) algorithm. Assume that the following operations take one unit of time:

• (a) Building the tree merge(T1, T2) from trees T1 and T2.
• (b) Moving to the parent of any node x in a given tree T .

Let m be the number of edges of G and n be the number of vertices in G. Show that the forest Fm can be built in time proportional to m·log(n).

The time taken to merge two trees takes a constant unit. For a worst case there will be exactly m of these operations. For each of these operations there will be a corresponding search through all existing trees to find the match for the edge. The time taken to search through any such tree will be log(n) as the time to move between a child and parent is 1.

9. A tree is finitely branching if every node of the tree has finitely many children. A tree is finite if it has finitely many nodes. Clearly all the finite trees are finitely branching. Give examples of infinite finitely branching trees.

An example of an infinite finitely branching tree would be a tree with a root which has a finite amount of branches. Each branch also has a finite amount of branches. Down each path however there will be an infinite number of vertices.

Programming exercises

1. Write a program that given a tree outputs all of its leaves.

3. Write a program that given a tree with a left-to-right order on children of its nodes outputs the nodes of the tree in pre-order.

5. Implement the FindComponents(G) algorithm.