2. Let T be the set of all rooted, ordered, possibly empty, binary trees. Rooted means...

Transcribed Image Text:

2. Let T be the set of all rooted, ordered, possibly empty, binary trees. Rooted means that we are not considering trees as special cases of graphs (where any connected graph without cycles specifies a single tree, regardless of how it's laid out). Ordered means that the mirror image of a tree is considered a distinct tree, unless the original tree is symmetrical. Including the empty tree allows us to say that each node has exactly two sub-trees, which can help avoid dividing into cases. And then it's convenient to define the height of a tree to be its number of levels, so that the height of a tree is always a natural number. In particular, the height of an empty tree is zero. And the height of any non-empty tree is one more than the maximum of the heights of its root's two sub-trees. If you have any trouble with this question, do the following first. In particular, before asking about this question on the bulletin board or in office hours, make sure you have done this "warmup" first and feel free to ask about it: • Draw the set of trees for each of the heights 0, 1, 2, and 3. As usual, try to combine previous trees (in particular, avoid thinking about it as adding leaves). Try to be systematic. If there are more trees of height 3 than you want to draw, try to describe a partition of the set of them into sub-sets collecting elements you could construct in "similar" ways. • Describe how you could generate the set of trees of height 4 now, or if the specialness of small trees is hiding a general approach then describe how you could generate the set of trees of height 236 from the sets of trees of all previous heights. • If you use Σ or II notation, check the initial and final indices of each use by instantiating the term formula with the initial and the final indices. And instantiate your recurrence and proof with small heights. You may use "..." notation, but you still have to pay attention to whether you are assuming that there are at least as many terms as you write out explicitly and whether that assumption is correct. Even if you use Σ or II notation it is worth writing them out with "..." notation as a check (in particular, that requires instantiating the terms with at least the initial and final index), and it often visually reveals the algebra you want to perform on them. ● Try instances of the Inductive Step. (a) For each he N, let by be the number of elements of T of height h. State, and justify, a recurrence for b. (b) Define a sequence by ao = 0, and an+1 = a + 1 for each n € N. Prove, by Complete Induction, that bh+1 = ah+1 - a for each he N. 2. Let T be the set of all rooted, ordered, possibly empty, binary trees. Rooted means that we are not considering trees as special cases of graphs (where any connected graph without cycles specifies a single tree, regardless of how it's laid out). Ordered means that the mirror image of a tree is considered a distinct tree, unless the original tree is symmetrical. Including the empty tree allows us to say that each node has exactly two sub-trees, which can help avoid dividing into cases. And then it's convenient to define the height of a tree to be its number of levels, so that the height of a tree is always a natural number. In particular, the height of an empty tree is zero. And the height of any non-empty tree is one more than the maximum of the heights of its root's two sub-trees. If you have any trouble with this question, do the following first. In particular, before asking about this question on the bulletin board or in office hours, make sure you have done this "warmup" first and feel free to ask about it: • Draw the set of trees for each of the heights 0, 1, 2, and 3. As usual, try to combine previous trees (in particular, avoid thinking about it as adding leaves). Try to be systematic. If there are more trees of height 3 than you want to draw, try to describe a partition of the set of them into sub-sets collecting elements you could construct in "similar" ways. • Describe how you could generate the set of trees of height 4 now, or if the specialness of small trees is hiding a general approach then describe how you could generate the set of trees of height 236 from the sets of trees of all previous heights. • If you use Σ or II notation, check the initial and final indices of each use by instantiating the term formula with the initial and the final indices. And instantiate your recurrence and proof with small heights. You may use "..." notation, but you still have to pay attention to whether you are assuming that there are at least as many terms as you write out explicitly and whether that assumption is correct. Even if you use Σ or II notation it is worth writing them out with "..." notation as a check (in particular, that requires instantiating the terms with at least the initial and final index), and it often visually reveals the algebra you want to perform on them. ● Try instances of the Inductive Step. (a) For each he N, let by be the number of elements of T of height h. State, and justify, a recurrence for b. (b) Define a sequence by ao = 0, and an+1 = a + 1 for each n € N. Prove, by Complete Induction, that bh+1 = ah+1 - a for each he N.

Answer rating: 100% (QA)

This question is asking to analyze rooted ordered binary trees and to establish a relationship between the number of binary trees of a certain height ... View the full answer