Brian82784
- 19
- 0
Growing More Trees to Sustainable Living
- Topic:
- Thread starter Brian82784
- Start date
-
- Tags
- Trees
Join the discussion
Registration is free. Start your own thread to ask a follow-up.
4 replies · 3K views
Discussion
Evgeny.Makarov
Gold Member
MHB
- 2,434
- 4
I come into contact with tree structures only occasionally, so I don't remember all definitions. Besides, some concepts have been used in different senses in different sources.
1a) This is correct if levels are counted from 1. I think it is more likely that the root has level 0.
1b-d) Correct.
2) Correct.
3) According to NIST, a complete tree is one "in which every level, except possibly the deepest, is entirely filled. At depth $n$, the height of the tree, all nodes are as far left as possible". This grouping to the left means that no only a child has to be added to v1, but also it must have three children of its own. The problem statement does not make it clear how to write this. A similar observation applies to v2: if children are added to the left of v6, then they themselves have to have three children each.
Also, there is more than one way to turn this tree into a complete one: for example, one could add from 0 to 3 children grouped left to v7 and 0 children to v8 and v9. One could add 0 or 1 child to v6 (zero if no children are added to v7--v9). As for v10 and v11, they should definitely not have children.
This problem does not seem to be formulated very well. Perhaps you have a different definition of a complete tree.
Edit: Forgot 4) and 5). I am not sure what T(v3) denotes and what the difference is with (T, v3). You should review the definition of tree height in your source, but I think it's the maximum number of edges from the root to a leave. Then the height of the whole tree in the second picture is 2.
1a) This is correct if levels are counted from 1. I think it is more likely that the root has level 0.
1b-d) Correct.
2) Correct.
3) According to NIST, a complete tree is one "in which every level, except possibly the deepest, is entirely filled. At depth $n$, the height of the tree, all nodes are as far left as possible". This grouping to the left means that no only a child has to be added to v1, but also it must have three children of its own. The problem statement does not make it clear how to write this. A similar observation applies to v2: if children are added to the left of v6, then they themselves have to have three children each.
Also, there is more than one way to turn this tree into a complete one: for example, one could add from 0 to 3 children grouped left to v7 and 0 children to v8 and v9. One could add 0 or 1 child to v6 (zero if no children are added to v7--v9). As for v10 and v11, they should definitely not have children.
This problem does not seem to be formulated very well. Perhaps you have a different definition of a complete tree.
Edit: Forgot 4) and 5). I am not sure what T(v3) denotes and what the difference is with (T, v3). You should review the definition of tree height in your source, but I think it's the maximum number of edges from the root to a leave. Then the height of the whole tree in the second picture is 2.
johng1
- 234
- 0
Hi,
I agree with Markov; the definition of complete tree is as specified in his link. Also unless you have misinterpreted the definitions, your text/instructor is "marching to his own drummer". For example, the height of a tree with one node is 0. The following tree is the result of augmenting your original tree to a complete tree; the color coding indicates the nodes which are added.
I agree with Markov; the definition of complete tree is as specified in his link. Also unless you have misinterpreted the definitions, your text/instructor is "marching to his own drummer". For example, the height of a tree with one node is 0. The following tree is the result of augmenting your original tree to a complete tree; the color coding indicates the nodes which are added.
Brian82784
- 19
- 0
Evgeny.Makarov
Gold Member
MHB
- 2,434
- 4
The number of vertices that have to be added to v4 and v5 is incorrect. I repeat the remarks that one must add leaves to some added vertices and that this tree can be made complete in several ways. Also, as I said in post #2,
What do you denote by (T, v3) and T(v3)?Evgeny.Makarov said: