Difference between revisions of "Trees"
(→TRC PowerPoint) |
|||
| (29 intermediate revisions by 6 users not shown) | |||
| Line 1: | Line 1: | ||
| − | [[File: | + | ==Overview== |
| + | <youtube>https://www.youtube.com/watch?v=0lxX428YFxw&list=PLCiOXwirraUD0G290WrVKpVYd3leGRRMW&index=8</youtube> | ||
| + | |||
| + | https://www.youtube.com/watch?v=0lxX428YFxw&list=PLCiOXwirraUD0G290WrVKpVYd3leGRRMW&index=8 | ||
| + | |||
| + | ==What is a Tree== | ||
| + | A tree is a '''connected''', '''undirected''' graph with '''no cycles''' in it. | ||
| + | |||
| + | ===Connected=== | ||
| + | All nodes must be connected to other nodes so that no part of the graph is separated. An unconnected graph is essentially 2 separate graphs. | ||
| + | |||
| + | ===Undirected=== | ||
| + | A tree can't have any directed edges/arcs. This will be an arrow on the edge/arc to indicate the direction of travel. | ||
| + | |||
| + | ===No Cycles=== | ||
| + | A run of interconnected nodes that return to the point of origin. | ||
| + | |||
| + | |||
| + | ==What is a Rooted Tree== | ||
| + | A tree with one vertex singled out as a starting point. | ||
| + | |||
| + | [[File:Tree-1.jpg|300px]] | ||
| + | |||
| + | ==What is a Binary Tree== | ||
| + | A binary tree is a graph with no cycles in which each node is succeeded by a maximum of 2 nodes, a 'left' child and a 'right' child, therefore they can be either directed or undirected. | ||
| + | |||
| + | <youtube>https://www.youtube.com/watch?v=OyOn95AOXSM&index=9&list=PLCiOXwirraUD0G290WrVKpVYd3leGRRMW</youtube> | ||
| + | |||
| + | https://www.youtube.com/watch?v=OyOn95AOXSM&index=9&list=PLCiOXwirraUD0G290WrVKpVYd3leGRRMW | ||
| + | |||
| + | ==What is a Binary Tree Search== | ||
| + | A binary tree can be created from a list of data: | ||
| + | |||
| + | #The first item in the list will be the root of your tree. | ||
| + | #You will then add an item to the tree by firstly comparing the new item to the root. | ||
| + | ##If it is alphabetically Lower than the root the new item will be placed on the left of the root. | ||
| + | ##If it is alphabetically Higher than the root the new item will be place to the right of the root. | ||
| + | #The next item in the list will again be compared to the root. | ||
| + | ##If it is alphabetically Lower than the root the new item will be placed on the left of the root. If the root already has a node to the left, the new item will be compared to this node as well. | ||
| + | ##If it is alphabetically Higher than the root the new item will be place to the right of the root. If the root already has a node to the Right, the new item will be compared to this node as well. | ||
| + | |||
| + | ===Example=== | ||
| + | The tree below shows the insertion of: 38, 13, 51, 10, 12, 40, 84, 25, 89, 37, 66, 95 (added in this order) | ||
| + | |||
| + | [[File:Trees-2.jpg|500px]] | ||
| + | |||
| + | The search phase is very similar, you start with the number you wish to find and compare it to the root. Travel from node to node using the rules: | ||
| + | #Compare the search value with the node, if they are not equal: | ||
| + | ##If it is alphabetically Lower than the node travel to the left of the node. | ||
| + | ##If it is alphabetically Higher than the node travel to the right of the node. | ||
| + | #If you reach a point and no path can be taken then the item is not in the list. | ||
| + | |||
| + | =='''Quiz'''== | ||
| + | ===Question 1=== | ||
| + | ===Question 2=== | ||
| + | ===Question 3=== | ||
| + | ===Question 4=== | ||
| + | ===Question 5=== | ||
| + | ===Question 6=== | ||
| + | ===Question 7=== | ||
| + | ===Question 8=== | ||
| + | ===Question 9=== | ||
| + | ===Question 10=== | ||
| + | ===Question 11=== | ||
| + | ===Question 12=== | ||
Latest revision as of 08:34, 25 September 2020
Contents
Overview
https://www.youtube.com/watch?v=0lxX428YFxw&list=PLCiOXwirraUD0G290WrVKpVYd3leGRRMW&index=8
What is a Tree
A tree is a connected, undirected graph with no cycles in it.
Connected
All nodes must be connected to other nodes so that no part of the graph is separated. An unconnected graph is essentially 2 separate graphs.
Undirected
A tree can't have any directed edges/arcs. This will be an arrow on the edge/arc to indicate the direction of travel.
No Cycles
A run of interconnected nodes that return to the point of origin.
What is a Rooted Tree
A tree with one vertex singled out as a starting point.
What is a Binary Tree
A binary tree is a graph with no cycles in which each node is succeeded by a maximum of 2 nodes, a 'left' child and a 'right' child, therefore they can be either directed or undirected.
https://www.youtube.com/watch?v=OyOn95AOXSM&index=9&list=PLCiOXwirraUD0G290WrVKpVYd3leGRRMW
What is a Binary Tree Search
A binary tree can be created from a list of data:
- The first item in the list will be the root of your tree.
- You will then add an item to the tree by firstly comparing the new item to the root.
- If it is alphabetically Lower than the root the new item will be placed on the left of the root.
- If it is alphabetically Higher than the root the new item will be place to the right of the root.
- The next item in the list will again be compared to the root.
- If it is alphabetically Lower than the root the new item will be placed on the left of the root. If the root already has a node to the left, the new item will be compared to this node as well.
- If it is alphabetically Higher than the root the new item will be place to the right of the root. If the root already has a node to the Right, the new item will be compared to this node as well.
Example
The tree below shows the insertion of: 38, 13, 51, 10, 12, 40, 84, 25, 89, 37, 66, 95 (added in this order)
The search phase is very similar, you start with the number you wish to find and compare it to the root. Travel from node to node using the rules:
- Compare the search value with the node, if they are not equal:
- If it is alphabetically Lower than the node travel to the left of the node.
- If it is alphabetically Higher than the node travel to the right of the node.
- If you reach a point and no path can be taken then the item is not in the list.
