10-Trees (1) Huylm PDF

Chapter 10
Trees
10.1- Introduction to Trees
Introduction to Trees…
Introduction to Trees
circuit disconnected
Proof: page 684
Some Page 686

terminologies:
Subtree
Root node (vertex)
Internal node
Leaf
Parent
Child
Siblings
Descendants
Ancestors
Full Full Full

3-ary
Binary Ternary 5-ary
Some terminologies on binary tree:

Left child, right child, left subtree, right subtree
Trees
Q1.
a. If T is a tree with 999 vertices, then T has ________ edges.
b. There are ________ non-isomorphic trees with four vertices.
c. There are ________ non-isomorphic rooted trees with four vertices.
d. There are ________ full binary trees with six vertices.
A m-ary tree is called balanced if all leaves are
at levels h or h-1.
h=4 h=4 h=3

All leaves are at All leaves are at All leaves are at
levels 3, 4 levels 2,3, 4 levels 3
→ Balanced → Not Balanced → Balanced
Q2.
a. Every full binary tree with 61 vertices has ________ leaves.
b. Every full binary tree with 50 leaves has ________ vertices.
c. Every full 3-ary tree with 13 vertices has ________leaves.
d. If T is a full binary tree with 50 internal vertices, then T has ________vertices.
e. There are ________ full 3-ary trees with 6 vertices.
f. If T is a binary tree with 100 vertices, its minimum height is ________.
g. If T is a full binary tree with 101 vertices, its maximum height is ________.
10.2- Applications of Trees
⚫ Binary Search Trees

⚫ Decision Trees
⚫ Prefix Codes
Constructing a Binary Search Tree
Q3. Set up a binary tree for the following list, in the given order, using alphabetical
ordering: STOP, LET, THERE, TAPE, NONE, YOU, ANT, NINE, OAT, NUT. Explain step by
step how you would search for the word TEST in your tree.
Q4. Construct a binary search tree for numbers: 23, 16, 43, 5, 9, 1, 6, 2, 33, 27.
Algorithm for inserting an element to BST
Complexity: O(logn)
Proof: page 698
Decision Trees
The Counterfeit Coin Problem
Q5. Suppose you have 5 coins, one of which is heavier than the other four. How many
weighings are used to find the fake coin? Draw the decision tree for using a pan balance
scale to find the heavy coin.
Decision Trees
Q6. Suppose you have 8 coins, one of which is lighter than the others. How many weighings are
used to find the fake coin?
Q7. Suppose you have 50 coins, one of which is lighter than the others. How many weighings are
used to find the bad coin?
Prefix Codes: Introduction
⚫ There are 26 characters → We can use 8 bit

(ASCII) only to store a character.
⚫ The word “sane” can be stored in 32 bits
⚫ May we can store this word in fewer bit?
Prefix Codes: Introduction
⚫ Construct a binary tree with a

prefix code.
⚫ “sane” will be store as
11111011100 ➔ 11 bits
11111011100 : s
11111011100 : a
11111011100 : n
11111011100 : e
➔ Compression factor: 32/11 ~ 3
Prefix Codes: Huffman Coding Algorithm
⚫ Counting occurrences of characters in a text ➔

frequencies (probabilities) of each character.
⚫ Constructing a binary tree representing prefix
codes of characters.
➔ The set of binary codes representing each
character.
➔ Coding source text
Q8. Use Huffman coding to encode the following symbols with the frequencies listed:
A: 0.08, B: 0.10, C: 0.12, D: 0.15, E: 0.20, F: 0.35.
What is the average number of bits used to encode a character?
Q9. Use Huffman coding to encode the word: “minimum”.
Q10. Use Huffman coding to encode the word: “pass the exam”.
Traversal Algorithms
⚫ At a time, a vertex is visited

⚫ Bases on orders of tasks, traversals are
classified into:
– Preorder traversal. N L R
– Inorder traversal. L N R
– Postorder traversal. L R N
Traversal Algorithms
Preorder Traversal
a, b, e, f, c, d, g, h, i
Inorder Traversal
e, b, f, a, c, g, d, h, i
Postorder Traversal
e, f, b, c, g, h, i, d, a
Traversal
Infix, Prefix, and Postfix Notation
⚫ Expression Trees
⚫ Expression Trees
⚫ Infix form:
operand_1 operator operand_2 x+y
⚫ Prefix form:
operator(operand_1,operand_2) +xy
⚫ Postfix form:
(operand_1,operand_2)operator xy+
⚫ How to find prefix and postfix form from infix
form?
(1) Draw expression tree.
(2) Using Preorder traverse → Prefix form
Using Postorder traverse → Postfix form
Infix form
Prefix form
Postfix form
Q11. Represent the expression ((x +2) ↑ 3) ∗ (y −(3+x)) − 5 using a binary tree. Write
this expression in
a. prefix notation.
b. postfix notation.
Q12. What is the value of each of these prefix expressions?
a. − ∗ 2 / 8 4 3
b. ↑ − ∗ 3 3 ∗ 4 2 5
c. + − ↑ 3 2 ↑ 2 3 / 6 − 4 2
d. ∗ + 3 + 3 ↑ 3 + 3 3 3
Q13. What is the value of each of these postfix expressions?

a. 5 2 1−−3 1 4 ++ ∗
b. 9 3 / 5 + 7 2 − ∗
c. 3 2 ∗ 2 ↑ 5 3 − 8 4 / ∗ −
Spanning trees
⚫ Introduction
39
Spanning trees
Definition.
Let G be a simple graph. A spanning tree of
G is a subgraph of G that is a tree
containing every vertex of G.
40
Spanning trees
41
Remov EdgesThat Form Simple Circuits.
Spanning trees
Q14. Find a spanning tree for each of these graphs.
a) K5 b) K4,4 c) K1,6
d) Q3 e) C5 f ) W5
THEOREM 1
A simple graph is connected if and only if it
has a spanning tree.
43
Depth-First Search
44
The edges selected by
depth-ﬁrst search of a
graph are called tree
edges.
All other edges are
called back edges.
45
Depth-First Search
Q15. Use depth-first search to find a spanning tree the following graph starting at node 1.
Assume that the vertices are ordered numerically.
46
Breadth-First Search
47
Breadth-First Search
Q15. Use breadth-first search to find a spanning tree the following graph starting at
node 1. Assume that the vertices are ordered numerically.
48
Minimum Spanning Trees
Which links should be made to ensure that there is a path

between any two computer centers so that the total cost of
the network is minimized?
➔ minimum spanning tree: a spanning tree that has the
smallest possible sum of weights of its edges.
49
Algorithms for Minimum Spanning
Trees
⚫ Prim’s algorithm (1957 by Robert Prim) (originally
discovered by Vojtech Jarník in1930).
⚫ Choosing any edge with smallest weight, putting it into
the spanning tree.
⚫ Add to the tree edges of minimum weight that are
incident to a vertex already in the tree, never forming a
simple circuit with those edges already in the tree.
⚫ Stop when n−1 edges have been added.
50
51
Kruskal’s algorithm (by Joseph
Kruskal in 1956)
⚫ Choose an edge in the graph with minimum weight.
⚫ Add edges with minimum weight that do not form a
simple circuit with those edges already chosen.
⚫ Stop after n−1 edges have been selected.
52
53
54
Minimum Spanning Trees
Q16. Use Prim’s and Kruskal’s algorithm to find a minimum spanning tree for the given
weighted graph.
55
Summary
⚫ Introduction to Trees
⚫ Applications of Trees
⚫ Tree Traversal
⚫ Spanning Trees
⚫ Minimum Spanning Trees

10-Trees (1) Huylm PDF

Uploaded by

Copyright:

Available Formats

10-Trees (1) Huylm PDF

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

10-Trees (1) Huylm PDF

Uploaded by

Copyright:

Available Formats

Chapter 10

Some Page 686

Full Full Full

Some terminologies on binary tree:

h=4 h=4 h=3

⚫ Binary Search Trees

⚫ There are 26 characters → We can use 8 bit

⚫ Construct a binary tree with a

⚫ Counting occurrences of characters in a text ➔

⚫ At a time, a vertex is visited

Q13. What is the value of each of these postfix expressions?

Which links should be made to ensure that there is a path

You might also like