- #1
MHB Growing More Trees to Sustainable Living
- Thread starter Brian82784
- Start date
-
- Tags
- Trees
Click For Summary
The discussion centers on the definitions and concepts related to tree structures, particularly the definition of a complete tree as outlined by NIST. There is some confusion regarding the levels of nodes, with suggestions that the root should be considered level 0. The formulation of the problem is criticized for lacking clarity, especially concerning how to properly add children to certain nodes to achieve a complete tree. Additionally, there is uncertainty about the notation T(v3) versus (T, v3), indicating a need for clarification on these terms. Overall, the conversation highlights the complexities and varying interpretations of tree structure definitions in academic contexts.
- #2
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.
- #3
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.
- #4
- #5
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: