- #1
Growing More Trees to Sustainable Living
- Context: MHB
- Thread starter Brian82784
- Start date
-
- Tags
- Trees
Click For Summary
Discussion Overview
The discussion revolves around the concept of complete trees in the context of tree structures, focusing on definitions, interpretations, and specific problems related to tree height and node addition. Participants are examining a set of problems and their solutions, with an emphasis on the correctness of definitions and the formulation of the problems.
Discussion Character
- Technical explanation
- Debate/contested
- Homework-related
Main Points Raised
- Some participants propose that the definition of a complete tree involves all levels being filled except possibly the deepest, and that nodes must be added in a specific manner.
- There is uncertainty regarding the level counting of the root, with some suggesting it should be level 0 instead of level 1.
- Participants note that the problem statement may not be clearly formulated, leading to different interpretations of how to achieve a complete tree.
- One participant expresses confusion about the notation T(v3) and its distinction from (T, v3), indicating a need for clarification on definitions used in the problems.
- There are multiple ways proposed to augment the tree to make it complete, suggesting variability in approach and interpretation.
Areas of Agreement / Disagreement
Participants do not reach a consensus on the definitions and interpretations of complete trees, with multiple competing views and ongoing uncertainty about the problem formulations and notations.
Contextual Notes
Limitations include potential misunderstandings of definitions, unclear problem statements, and unresolved questions regarding specific notations and their meanings.
- #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:
Similar threads
High School
Probably a silly question about tree diagrams
- · Replies 16 ·
- · Replies 9 ·
- · Replies 1 ·
- · Replies 3 ·
- · Replies 1 ·
- · Replies 19 ·
- · Replies 55 ·
- · Replies 1 ·
- · Replies 2 ·
- · Replies 1 ·