- #1
Growing More Trees to Sustainable Living
- Context: MHB
- Thread starter Brian82784
- Start date
-
- Tags
- Trees
Click For Summary
SUMMARY
The discussion centers on the definitions and characteristics of tree structures, particularly focusing on complete trees as defined by NIST. Participants clarify that a complete tree is one where every level, except possibly the deepest, is fully filled, with nodes positioned as far left as possible. There is an emphasis on the need for clarity in problem statements regarding the addition of children to nodes, specifically referencing nodes v1, v6, v7, v8, and v9. Additionally, the height of a tree is defined as the maximum number of edges from the root to a leaf, with specific examples provided to illustrate these concepts.
PREREQUISITES- Understanding of tree data structures
- Familiarity with the definition of complete trees as per NIST standards
- Knowledge of tree height and its calculation
- Basic graph theory terminology
- Research the NIST definition of complete trees in detail
- Explore tree height calculations and their implications in data structures
- Learn about different types of tree structures, including binary trees and AVL trees
- Investigate common problems and solutions related to tree augmentation
Students and professionals in computer science, particularly those studying data structures, algorithm design, and anyone involved in tree-related problem-solving in programming or academic settings.
- #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 ·