微信客服：xiaoxionga100
微信客服：ITCS521
EC504-无代写
时间：2023-05-09
EC504 Homework 3
Nicholas Sacco
October 26, 2022
Problem 1
Determine whether the following statements are true or false, and briefly explain why:
1A
If doubling the size ( → 2) causes the execute time () of an algorithm to increase by a factor of 4,
then () ∈ (4).
False. Assume that () ∈ (4). Then by definition:
∃, 0 .. () ≤ 4 ∀ ≥ 0
Assume we operate in the asymptotic region, that is ≥ 0; then () ≤ 4. If we double the input
size from → 2, then per the asymptotic bound:
(2) ≤ 4(2) =⇒ (2) ≤ 8
But we also assumed that doubling the input size from → 2 quadruples the run time:
(2) = 4 () =⇒ (2) ≤ 16
Thus, by doubling the input size from → 2, it is possible to violate the (4) asymptotic bound;
therefore, by contradiction, () ∉ (4).
1B
The height of a binary tree is the maximum number of edges from the root to any leaf path. The maximum
number of nodes in a binary tree of height ℎ is 2ℎ+1 − 1.
True. Let (ℎ) = 2ℎ+1 − 1 be the maximum number of nodes found in a binary tree of height ℎ. Use proof
by induction to prove the claim.
Base case: ℎ = 0. If a tree has height ℎ = 0, then it consists just of the root node. Evaluating the above
equation:
(0) = 21 − 1 = 2 − 1 =⇒ (0) = 1
The base case holds, so we can proceed with the induction step.
Induction step: Assume the claim holds for ℎ, namely the maximum number of nodes in a binary tree
of height ℎ is (ℎ) = 2ℎ+1 − 1. Show that if the claim holds for ℎ, then it must hold for ℎ + 1.
Assume we start with a full binary tree of height ℎ. The ℎTH level of a binary tree can hold a maximum
of 2ℎ nodes; to build a full binary tree of height ℎ + 1, all we have to do is add two child nodes to each leaf
node in the existing height ℎ binary tree. Since there are 2ℎ leaf nodes in a height ℎ binary tree, we need to
1
add 2ℎ × 2 = 2ℎ+1 nodes to build a binary tree of height ℎ + 1 with the maximum number of nodes. By the
induction hypothesis, there are (ℎ) = 2ℎ+1 − 1 total nodes in the height ℎ binary tree. Thus, in the height
ℎ + 1 binary tree, the maximum number of nodes is given by:
(ℎ + 1) = (ℎ) + 2ℎ+1 =
(
2ℎ+1 − 1
)
+ 2ℎ+1 = 2 × 2ℎ+1 − 1 = 2ℎ+2 − 1
Thus, (ℎ + 1) = 2ℎ+2 − 1, and the induction step holds. Thus, we have proven by induction that the
maximum number of nodes in a binary tree of height ℎ is (ℎ) = 2ℎ+1 − 1.
1C
In a binary search tree with no repeated keys, deleting the node with key , followed by deleting the node
with key , will result in the same search tree as deleting the node with key , then deleting the node with
key .
False. We discussed this problem in class today - Dr. Brower mentioned there is a counter-example that
looked like one of the following:
I haven’t been able to quite work out the counterexample.
1D
Inserting numbers 1 . . . into a binary min-heap in that order will take () time.
True. Inserting any sequence of distinct integers into a binary min-heap is accomplished in () time; we
use the array as is, and then heapify the tree bottom-to-top.
2
1E
The second smallest element in a binary min-heap with all elements with distinct values will always be a
child of the root.
True. Let be the smallest element in the binary min-heap (i.e., the root) and let
∗ be the second
smallest element in the binary min-heap. Thus <
∗ < for all other elements in the heap. Assume
∗ is not already a child of the root node. The binary min-heap requires that parent nodes are smaller in
value than their child nodes: < 1 , < 2 . If
∗ is not already a child of the root node, it must be
somewhere else in the rest of the tree: assume ∗ is a child node to node ′ . By construction, ′ > ∗; thus
the min-heap property is violated. To restore the requirement, ∗ must “bubble up” the tree, eventually
settling as a child of the root node: <
∗. Thus, the second smallest element in a binary min-heap with
distinct values will always be a child of the root node.
3
Problem 2
This exercise is to learn binary search tree operations:
2A
Draw the sequence of binary search trees which results from inserting the following values in left-to-right
order, assuming no balancing:
15, 10, 31, 25, 34, 56, 78, 12, 14, 13
15
Figure 1: Insert 15 as Root
15
10
Figure 2: Inserting 10: 10 < 15, Insert Left.
15
10 31
Figure 3: Inserting 31: 31 > 15, Insert Right.
4
15
10 31
25
Figure 4: Inserting 25: 25 > 15, Move right. 25 < 31, Insert left.
15
10 31
25 34
Figure 5: Inserting 34: 34 > 15, Move right. 34 > 31, Insert right.
15
10 31
25 34
56
Figure 6: Inserting 56: 56 > 15, Move right. 56 > 31, Move right. 56 > 34, Insert right.
5
15
10 31
25 34
56
78
Figure 7: Inserting 78: 78 > 15, Move right. 78 > 31, Move right. 78 > 34, Move right. 78 > 56, Insert right.
15
10 31
25 34
56
78
12
Figure 8: Inserting 12: 12 < 15, Move left. 12 > 10, Insert right.
6
15
10 31
25 34
56
78
12
14
Figure 9: Inserting 14: 14 < 15, Move left. 14 > 10, Move right. 14 > 12, Insert right.
15
10 31
25 34
56
78
12
14
13
Figure 10: Inserting 13: 13 < 15, Move left. 13 > 10, Move right. 13 > 12, Move right. 13 < 14, Insert left.
2B
Starting from the tree at the end of the previous part, draw the sequence that results from deleting the
following nodes in left-to-right order:
7
15, 31, 12, 14
We start with the complete tree:
15
10 31
25 34
56
78
12
14
13
Figure 11: Full Tree
To delete 15, we note that it has two child nodes, and thus we must use the rotation scheme. Let = 15,
= , ℓ = 10, = 31, = 25, and = . The rotation scheme proceeds as follows:
1. Move the sub-tree rooted at to .
2. Set to be the parent of .
3. Set to be the parent of . (Here, = because we are deleting the root node - we must replace
it with another node to maintain the tree.)
4. Set to be the parent of ℓ.
5. Clear the pointers associated with node - it is now deleted from the BST.
Following this procedure, we arrive at the tree:
8
25
10 31
34
56
78
12
14
13
Figure 12: Delete 15: Set 25 (the successor to 15) to be the parent of the left and right subtrees rooted at
10 and 31 respectively.
To delete 31, we note that it now has a single child node; thus we just need to adjust the pointers to
move the remaining nodes to their correct locations in the BST:
25
10 34
56
78
12
14
13
Figure 13: Delete 31: Since there is only one child node, we just need to adjust pointers to move the subtree
rooted at 34 up a level to maintain the BST property.
To delete 12, we note that it has a single child node; thus we just need to repeat the same process as
above: adjust the pointers to move the remaining nodes to their correct locations in the BST:
9
25
10 34
56
78
14
13
Figure 14: Delete 12: Since there is only one child node, we just need to adjust pointers to move the subtree
rooted at 14 up a level to maintain the BST property.
To delete 14, we note that it has a single child node; thus we just need to repeat the same process as
above: adjust the pointers to move the remaining nodes to their correct locations in the BST:
25
10 34
56
78
13
Figure 15: Delete 14: Since there is only one child node, we just need to adjust pointers to move the subtree
rooted at 13 up a level to maintain the BST property.
2C
After deleting them, draw the sequence of reinserting left-to-right in reverse order:
14, 12, 31, 15
into the tree, and comment on the result.
10
25
10 34
56
78
13
14
Figure 16: Inserting 14: 14 < 25, Move left. 14 > 10, Move right. 14 > 13, Insert right.
25
10 34
56
78
13
1412
Figure 17: Inserting 12: 12 < 25, Move left. 12 > 10, Move right. 12 < 13, Insert left.
11
25
10 34
56
78
13
1412
31
Figure 18: Inserting 31: 31 > 25, Move right. 31 < 24, Insert left.
25
10 34
56
78
13
1412
31
15
Figure 19: Inserting 15: 15 < 25, Move left. 15 > 10, Move right. 15 > 13, Move right. 15 > 14, Insert right.
The tree is clearly different than the original starting tree at the end of problem 2A. In general, it does
not appear that deleting a set of nodes and inserting them back in reverse order recovers the original tree.
12
Problem 3
Problem 3A: Exercises 6.1-3, 6.1-4, 6.1-6, 6.3-3
Exercise 6.1-3
Show that in any sub-tree of a max-heap, the root of the sub-tree contains the largest value occurring
anywhere in that sub-tree.
Let = {[] : ∈ []} be an -element max-heap with nodes = 1, 2, . . . . Let () be the parent to
node . A max-heap satisfies the following properties:
• The root node [1] contains the largest element in the heap. The root node has no parent node:
() = .
• Consider non-root node , ≠ 1. The max-heap property is described as follows: [()] ≥ [].
The max-heap property holds for all non-root nodes.
Since is a valid max-heap, the max-heap property will hold for all non-root nodes = 2, 3, . . . ;
namely, [()] ≥ [] ∀ ≥ 2. Let 1 be set of all paths we could traverse starting at the root of the sub-tree
and stopping at a leaf node. Since the max-heap property guarantees that [()] ≥ [], if we traverse
along nodes in path =
(
[1] 2 3 . . . ℓ
)
of length ℓ, we construct the partial ordering:
[1] ≥ 2 ≥ 3 ≥ . . . ≥ ℓ
Thus, pick any node ∗ as the root of subtree ∗ . Let ∗ be the set of all paths we could traverse starting
at node ∗ and stopping at a leaf node. Since we are not changing the number of nodes in tree , every path
′ ∈ ∗ must be a sub-path of some path ∈ 1. Since path ∈ 1 corresponds to the partial ordering:
[1] ≥ 2 ≥ 3 ≥ . . . ≥ ℓ
And path ′ =
(
[∗] ′2 ′3 . . . ℓ′
) ∈ ∗ of length ℓ′ is a subset of such a path, ′ must also correspond to
a partial ordering:
[∗] ≥ ′2 ≥ ′3 ≥ . . . ≥ ′ℓ′
Thus, the max-heap property is preserved even if we look at a sub-tree ∗ ⊆ ; thus, the root ∗ of any
subtree ∗ must contain the largest value in that subtree.
Exercise 6.1-4
Where in a max-heap might the smallest element reside, assuming that all elements are distinct?
The smallest element in a max-heap with all distinct elements must reside at a leaf node. Let be the
minimum element in the max-heap; by definition, < for all elements in the max-heap. Recall that
max-heap property - for node all nodes ≥ 2 (i.e., all non-root nodes), [()] > []; in other words, the
parent every non-root node of is larger than node itself. Assume that was located at non-leaf node
: [ ] = . Let node contain element : [] = . Let node be the parent to node . Since
() = , For the max-heap property to hold, we require that [()] > [] ⇐⇒ [ ] > []. But we
have assumed that was located at node , while some other distinct element > was located at
node . Thus, the max-heap property is not satisfied, since ≯ by definition. Thus, cannot be
found on a non-leaf node in a max-heap; it must be found at a leaf node where it has no child nodes.
13
Exercise 6.1-6
Is the array with values:
23, 17, 14, 6, 13, 10, 1, 5, 7, 12
a max heap?
It is much easier to analyze the structure graphically:
23
17 14
6 13 10 1
5 7 12
Recall the max-heap property: for non-root node with parent node (), we require [()] ≥ []. We see
that node 7 has parent 6; thus the max-heap property is violated. Thus this structure is NOT a max-heap.
Exercise 6.3-3
Show that there are at most: ⌈
2ℎ+1
⌉
nodes of height ℎ in any -element heap.
First, assume that = 2 − 1 ∈ N, ≥ 1. If we construct a binary heap with these elements, the
resulting tree is a perfect binary tree. In a perfect binary tree with 2 − 1 elements, the number of nodes
of height ℎ is easy to calculate, since the sum of the height and depth of nodes in the tree are constant:
ℎ + = − 1. At depth , there are () = 2 nodes; using the height-depth invariant, the number of nodes
of height ℎ in a perfect binary tree with 2 − 1 elements is given as:
2−1 (ℎ) = 2 = 2−ℎ−1 = 2
2ℎ+1
=
⌈
2 − 1
2ℎ+1
⌉
∴ 2−1 (ℎ) =
⌈
2ℎ+1
⌉
14
Now, let’s assume that = 2 < 2 − 1, ∈ N, ≥ 1, such that ⌈⌉ = ; that is, 2 is the first power of
2 greater than . Since we are constructing a heap, we completely fill a level with elements before inserting
elements in the next level; thus, since < 2 − 1, there will be several missing nodes in the last level of the
perfect binary tree, as illustrated in the example below:
1
2 3
4 5 6 7
8 9 10 11 12 13 14 15
Figure 20: Binary heap with = 10 elements (Nodes 1 - 10) compared to perfect binary heap with =
24 − 1 = 15 elements (Nodes 1 - 15). Nodes 11 - 15 are found in the perfect binary tree, but not in the heap
with 10 elements.
To recover the -element heap from the 2−1 element perfect tree, we just need to delete extra leaf nodes in
the last row of the perfect tree. Let 0 be the number of deleted nodes of height 0. By definition, the height
ℎ of a node is the longest path to a leaf node. If we delete 0 leaf nodes, each of height 0, then ⌊0/2⌋ parent
nodes, previously of height 1, become new leaf nodes of height 0. Thus, the number of nodes of height ℎ = 0
in the -element heap is given as:
(0) = 2−1 (0) − 0 +
⌊ 0
2
⌋
∴ (0) ≤ 2−1 (0)
15
12 3
4 5 6 7
8 9 10
Figure 21: Binary heap with = 10 elements (Nodes 1 - 10) after deleting the extra nodes. Nodes 6 and 7,
which were previously parent nodes of height ℎ = 1, are now leaf nodes of height ℎ = 0.
But this change propagates up the tree! In the perfect tree, there were originally 2−1 (1) nodes of height
1. Let 1 be the number of nodes, originally of height 1, but are now height 0. After updating the height of
1 nodes, ⌊1/2⌋ parent nodes, originally of height 2, are now one level closer to the leaves, and thus become
nodes of height 1. Thus, the number of nodes of height ℎ = 1 in the -element heap is given as:
(1) = 2−1 (1) − 1 +
⌊ 1
2
⌋
∴ (1) ≤ 2−1 (1)
Without loss of generality, we can repeat this argument up the entire tree. Since we have already
computed 2−1 (ℎ):
2−1 (ℎ) =
⌈
2ℎ+1
⌉
And we can upper bound (ℎ) with 2−1 (ℎ) for each height ℎ, we have that:
(ℎ) ≤
⌈
2ℎ+1
⌉
□
Problem 3B: Exercises 12.3-2, 12.3-3, 12.3-4, B.5-4
Exercise 12.3-2
Suppose that we construct a binary search tree by repeatedly inserting distinct values into the tree. Argue
that the number of nodes examined in searching for a value in the tree is one plus the number of of nodes
examined when the value was first inserted into the tree.
16
Let be the number of nodes examined when inserting node into the binary search tree. Let be the
set of nodes visited when inserting node into the binary search tree. Every time a node is visited, add it
to . To insert node into the binary search tree, we start at the root node. Append the root node to
, and perform the comparison to determine which side of the subtree to place . Move to the next node
accordingly; say we move to node 2. Then, we append 2 to the node list , and perform the comparison
to determine which side of the subtree rooted at node 2 to place . This process until we finally place - we
will have examined nodes = {, 2, 3 . . . }, where | | = , to determine the proper location of
in the binary search tree. Some time later, we wish to search for node in the binary search tree. Let ′ be
the set of nodes visited when searching for in the binary search tree. We start the search at the root node.
Append the root to ′ , and perform the comparison to determine which side of the subtree is located.
Move to the next node accordingly; we will move to node 2, the same node we moved to when looking for
the location to place ! We perform the comparison again, moving to node 3. At node 3, we append it to
′ and continue. We will traverse the same nodes: , 2, 3, . . . . At , we perform the comparison,
which moves us to node ∗, which contains . Once at ∗, we must perform the last comparison to confirm
we have found ; thus, we must evaluate ′ = |′ | = | ∪ ∗ | = + 1. Thus, when searching for , we must
examine + 1 nodes.
Exercise 12.3-3
We can sort a given set of numbers by first building a binary search tree containing these numbers (using
TREE-INSERT repeatedly to insert the numbers one by one) and then printing the numbers by an in-order
tree walk. What are the worst-case and best-case running times for this sorting algorithm?
Let () be the time required to print out the contents of any -element binary search tree. By using the
recursive definition of the in-order-print function, we have that () = Θ() for any -element binary search
tree. The most significant portion of the proposed sorting algorithm is the time required to build the binary
search tree by inserting the elements into the tree one-by-one. In the many tree-based structures we have
studied so far, we have seen that insertion operations require time that scales with the height of the tree.
In the best-case insertion, the elements that are inserted into the binary search tree form a perfect binary
tree with height Θ(lg ). Inserting a new element into an existing tree of height Θ(lg ) requires traversal
down a path of length Θ(lg ). Thus, building a binary search tree by inserting elements one-by-one takes
() = Θ( lg ) time in the best-case insertion. In the worse-case insertion, then elements that are inserted
into the binary search tree form a linked list with height Θ() - this occurs if the elements are already
sorted. Inserting a new element into an existing linked list of height Θ() requires traversal down a path of
length Θ(). Thus, building a binary search tree by inserting elements one-by-one takes () = Θ(2)
time in the worst-case insertion. Thus, the total time for the sorting algorithm is:
() =
{
() + () = Θ( lg ) + Θ() = Θ( lg ),
() + () = Θ(2) + Θ() = Θ(2),
Exercise 12.3-4
Is the operation of deletion ”commutative” in the sense that deleting and then from a binary search tree
leaves the same tree as deleting then ? Argue why it is or give a counterexample.
See problem 1C, this is the same question.
Exercise B.5-4
Use induction to show that a nonempty binary tree with nodes has height at least ⌊lg ⌋.
17
Base case: Let = 1. Since the binary tree consists of just 1 node, it must have height 0; thus (1) = 0.
Using the equation () ≥ ⌊lg ⌋:
(1) ≥ ⌊lg 1⌋ =⇒ (1) ≥ 0
Thus, the base case holds and we can proceed with the rest of the induction.
Induction step: Assume () ≥ ⌊lg ⌋; show that if this holds, then ( + 1) ≥ ⌊lg + 1⌋.
Recall the definition of the height of a binary tree: the height is the length of the longest path from
the root node to a leaf node. Thus, there are two extreme ways of organizing a binary tree with nodes -
a linked list of height − 1, and a complete binary tree of height ≈ lg (We will be more precise with the
scaling later). Thus, we can bound the height () of any tree with nodes as:
lg ⪅ () ≤ − 1
Let 2−1 ≤ ≤ 2 − 2. In other words, = 2 , ∈ [ − 1, ) By the induction hypothesis:
() ≥ ⌊lg ⌋ = ⌊lg 2⌋ = ⌊⌋ = − 1
Thus, () ≥ − 1. To get + 1 elements in the tree, we add one more node. Assume we can place it
such that ( + 1) = (). Thus is possible since we cannot form a perfect tree with ∈ [2−1, 2 − 2]
elements; thus, we can always form a tree where adding an additional node does not change the height of
the tree. Thus, ( + 1) ≥ − 1. Since = 2 , we can write + 1 = 2 for some > , ∈ [2−1, 2 − 2].
Thus:
⌊lg + 1⌋ = ⌊lg 2⌋ = ⌊⌋ = − 1
.
Since ( + 1) ≥ − 1, we can write:
( + 1) ≥ − 1 = ⌊lg + 1⌋ =⇒ ( + 1) ≥ ⌊lg + 1⌋
Now assume = 2 − 1; in other words, we can form a perfect tree with elements; the minimum height
of an element tree is the same: () ≥ − 1. Now, when we add one more element, the height of the
perfect binary tree must increase; thus ( + 1) ≥ () + 1 = ( − 1) + 1 =⇒ ( + 1). But:
+ 1 = (2 − 1) + 1 = 2 =⇒ ⌊lg + 1⌋ = ⌊lg 2⌋ =
Therefore, ( + 1) ≥ ⌊lg + 1⌋. Since ( + 1) ≤ ⌊lg + 1⌋ in both scenarios, the induction step holds.
Thus, by induction, we have shown that the minimum height of a binary tree with nodes is () ≥ ⌊lg ⌋.
18
Problem 4
Determine whether the following statements are true or false, and briefly explain why:
4A
A heapsort algorithm for a given list first forms a max-heap with the elements in that list, then extracts
the elements of the heap one by one from the top. This algorithm will sort a list of elements in time of
(log ).
False. Heapsort has a run-time of ( log ) - each element must roughly travel a path of length (log )
for the max heap to be maintained after each iteration. Since there are elements to sort, heapsort takes
( log ) time to sort elements.
4B
A connected, undirected, acyclic graph with nodes and − 1 edges is a tree.
True. A tree is defined as a connected, undirected, acylic graph; if there are nodes in the tree and the
entire structure is connected, then there must be − 1 edges.
4C
A binary heap of elements is a full binary tree for all possible values of .
False. A full binary tree is one where each node has either 0 or 2 child nodes. A binary heap with elements,
while always complete (meaning it is filled consecutively), does not have to be full; it is possible for a node
to have just one child node, as shown in the counterexample below:
4
10 5
12
4D
The following tree is a valid min-heap:
19
410
12 14
5
True. A min-heap satisfies the min-heap property: [()] ≤ [] ∀ ≥ 2. In other words, the parent of
non-root node must be smaller than node . Each node in the above tree satisfies the min-heap property,
so the above tree is a valid min-heap.
4E
The following tree can appear in a binomial min-heap:
4
10
12 14
5
False. A binomial heap order contains binary trees that have depths following the binomial coefficients
found in Pascal’s triangle; thus, the depths should take the form 1, 2, 1. However, in the given heap, we see
the depths take the form 1, 2, 2, which are not the binomial coefficients. Thus, this tree cannot appear in
a binomail min-heap.
4F
Given an array of positive integers [], maximizing ∑ · [] over permutations of the array requires sorting
[] in assigning order.
True. Sorting is just a special case of the optimization problem:
max
∑︁
· []
Thus, if we want to find the above maximum, all we really need to do is just sort the array - we will find
the maximum sum, no special optimization techniques required.
20
Problem 5
Given the following list of elements:
35, 22, 11, 98, 55, 66, 77, 80, 85, 90, 95
5A
Draw the sequence of binary min-heaps which results from inserting the following values in the order in
which they appear into an empty heap.
The min-heap satisfies the min-heap property: [()] ≤ ∀ ≥ 2. To build the min-heap, we first start
by throwing every element into the binary heap, ignoring the min-heap property:
35
22
98
80 85
55
90 95
11
66 77
Figure 22: Starting min-heap
Then we run the heapify algorithm, “bubbling” low-value nodes to the top of the heap by swapping node
with its parent node () if [()] > []. The incremental binary heaps are shown in the figures below:
35
22
98
80 85
55
90 95
11
66 77
35
22
80
98 85
55
90 95
11
66 77
Figure 23: Node 77 - no child nodes, pass. Node 66 - no child nodes, pass. Node 55: 55 < 90 and 55 < 95,
min-heap property holds, no swaps necessary. Node 98: 98 > 80 and 98 > 85, swap node 98 with node 80,
the smaller of the two child nodes.
21
35
22
80
98 85
55
90 95
11
66 77
11
22
80
98 85
55
90 95
35
66 77
Figure 24: Node 11: 11 < 66 and 11 < 77, min-heap property holds, no swaps necessary. Node 22: 22 < 80
and 20 < 55, min-heap property holds, no swaps necessary. Node 35: 35 > 22 and 35 > 11, swap node 35
with node 11, the smaller of the two child nodes.
The final min heap is shown below:
11
22
80
98 85
55
90 95
35
66 77
Figure 25: Final min-heap - the min-heap property holds for all nodes.
5B
Compare this answer with inserting them into the BST tree.
35
Figure 26: Insert 35 as Root
22
35
22
Figure 27: Inserting 22: 22 < 35, Insert left.
35
22
11
Figure 28: Inserting 11: 11 < 35, Move left. 11 < 22, Insert left.
35
22
11
98
Figure 29: Inserting 98: 98 > 35, Insert right.
35
22
11
98
55
Figure 30: Inserting 55: 55 > 35, Move right. 55 < 98, Insert left.
23
35
22
11
98
55
66
Figure 31: Inserting 66: 66 > 35, Move right. 66 < 98, Move left. 66 > 55, Insert right.
35
22
11
98
55
66
77
Figure 32: Inserting 77: 77 > 35, Move right. 77 < 98, Move left. 77 > 55, Move right. 77 > 66, Insert right.
24
35
22
11
98
55
66
77
80
Figure 33: Inserting 80: 80 > 35, Move right. 80 < 98, Move left. 80 > 55, Move right. 80 > 66, Move right.
80 > 77, Insert right.
35
22
11
98
55
66
77
80
85
Figure 34: Inserting 85: 85 > 35, Move right. 85 < 98, Move left. 85 > 55, Move right. 85 > 66, Move right.
85 > 77, Move right. 85 > 80, Insert right.
25
35
22
11
98
55
66
77
80
85
90
Figure 35: Inserting 90: 90 > 35, Move right. 90 < 98, Move left. 90 > 55, Move right. 90 > 66, Move right.
90 > 77, Move right. 90 > 80, Move right. 90 > 85, Insert right.
26
35
22
11
98
55
66
77
80
85
90
95
Figure 36: Inserting 95: 95 > 35, Move right. 95 < 98, Move left. 95 > 55, Move right. 95 > 66, Move right.
95 > 77, Move right. 95 > 80, Move right. 95 > 85, Move right. 95 > 90, Insert right.
A binary search tree is a relatively poor data structure for this particular set of data given that most of
the elements already appear in sorted order, resulting in a highly unbalanced tree.
5C
Compare this answer with inserting them into the AVL tree.
We can improve the balance in the structure by using the AVL tree which imposes the following property
on each node in the tree. Let () and () be the left subtree rooted at node and the right subtree
rooted at node respectively. Let () and () be the height of left subtree () and right subtree ()
respectively. The AVL property requires:
| () − () | ≤ 1 ∀
Maintaining this property requires careful balancing via single rotations and double rotations, as illus-
trated by the four cases below:
27
Figure 37: AVL Single Rotation
Figure 38: AVL RL Double Rotation
Figure 39: AVL LR Double Rotation
28
35 (0)
Figure 40: Insert 35 as Root. There are no child nodes, so the AVL property is maintained.
35 (1)
22 (0)
Figure 41: Insert 22: 22 < 35, Insert left. The AVL property is maintained for each node in the tree, so no
need to rebalance.
35 (2)
22 (1)
11 (0)
22 (1)
11 (0) 35 (0)
Figure 42: Insert 11: 11 < 35, Move left. 11 < 22, Insert left. The AVL property is violated for node 35; this
format fits the case of a single rotation with 1 = 22, 2 = 35, = 11, = , and = . After
performing the single rotation, we obtain the tree on the right, which maintains the AVL property.
22 (1)
11 (0) 35 (1)
98 (0)
Figure 43: Insert 98: 98 > 22, Move right. 98 > 35, Insert right. The AVL property is maintained for each
node in the tree, so no need to rebalance.
29
22 (2)
11 (0) 35 (2)
98 (1)
55 (0)
22 (1)
11 (0) 55 (0)
35 (0) 98 (0)
Figure 44: Insert 55: 55 > 22, Move right. 55 > 35, Move right. 55 < 98, Insert left. The AVL property is
violated for node 35; this format fits the case of a double rotation with 1 = 98, 2 = 55, 3 = 35, = ,
= , = , and = . After performing the double rotation, we obtain the tree on the
right, which maintains the AVL property.
30
22 (2)
11 (0) 55 (1)
35 (0) 98 (1)
66 (0)
55 (0)
22 (0) 98 (1)
11 (0) 35 (0) 66 (0)
Figure 45: Insert 66: 66 > 22, Move right. 66 > 55, Move right. 66 < 98, Insert left. The AVL property
is violated for node 22; this format fits the case of a single rotation with 1 = 22, 2 = 55, = 11, = 35,
and = 98. After performing the single rotation, we obtain the tree on the right, which maintains the AVL
property.
31
55 (1)
22 (0) 98 (2)
11 (0) 35 (0) 66 (1)
77 (0)
55 (0)
22 (0) 77 (0)
11 (0) 35 (0) 66 (0) 98 (0)
Figure 46: Insert 77: 77 > 66, Move right. 77 < 98, Move left. 77 > 66, Insert right. The AVL property is
violated for node 98; this format fits the case of a double rotation with 1 = 66, 2 = 77, 3 = 98, = ,
= , = and = . After performing the single rotation, we obtain the tree on the
right, which maintains the AVL property.
32
55 (1)
22 (0) 77 (1)
11 (0) 35 (0)
66 (0) 98 (1)
80 (0)
Figure 47: Insert 80: 80 > 55, Move right. 80 > 77, Move right. 80 < 98, Insert left. The AVL property is
maintained for each node in the tree, so no need to rebalance.
33
55 (2)
22 (0) 77 (2)
11 (0) 35 (0)
66 (0) 98 (2)
80 (1)
85 (0)
55 (1)
22 (0) 77 (1)
11 (0) 35 (0) 66 (0) 85 (0)
80 (0) 98 (0)
Figure 48: Insert 85: 85 > 55, Move right. 85 > 77, Move right. 85 < 98, Move left. 85 > 80, Insert right.
The AVL property is violated for node 98; this format fits the case of a double rotation with 1 = 80, 2 = 85,
3 = 98, = , = , = and = . After performing the single rotation, we obtain
the tree on the right, which maintains the AVL property.
34
55 (2)
22 (0) 77 (2)
11 (0) 35 (0) 66 (0) 85 (1)
80 (0) 98 (1)
90 (0)
55 (1)
22 (0) 85 (0)
11 (0) 35 (0)
77 (0) 98 (1)
66 (0) 80 (0) 90 (0)
Figure 49: Insert 90: 90 > 55, Move right. 90 > 77, Move right. 90 > 85, Move right. 90 < 98, Insert left.
The AVL property is violated for node 77; this format fits the case of a single rotation with 1 = 77, 2 = 85,
= 66, = 80, and = 98. After performing the single rotation, we obtain the tree on the right, which
maintains the AVL property.
35
55 (2)
22 (0) 85 (1)
11 (0) 35 (0)
77 (0) 98 (2)
66 (0) 80 (0) 90 (1)
95 (0)
55 (1)
22 (0) 85 (0)
11 (0) 35 (0)
77 (0) 95 (0)
66 (0) 80 (0) 90 (0) 98 (0)
Figure 50: Insert 95: 95 > 55, Move right. 95 > 85, Move right. 95 < 98, Move left. 95 > 90, Insert right.
The AVL property is violated for node 98; this format fits the case of a double rotation with 1 = 90, 2 = 95,
3 = 98, = , = , = and = . After performing the double rotation, we
obtain the tree on the right, which maintains the AVL property.
As shown above, the AVL tree is signficantly more balanced than the binary search tree!
36
Problem 6
You are interested in compression. Given a file with characters, you want to find the binary code which
satisfies the prefix property (no conflicts) and which minimizes the number of bits required. As an example,
consider an alphabet with 8 symbols, with relative weights (frequency) of appearance in an average text file
given below:
alphabet A L G O R I T H
weights 68 20 5 30 18 15 19 12
6A
Determine the Huffman code by constructing a tree with minimum external path length:
∑︁
=1
(Arrange tree with smaller weights to the left)
At each round, select the two smallest weights 1, 2 , 1 ≤ 2, build tree with parent 12 = 1 + 2, left
child 1, and right child 2. Put symbol 12 back into the weight table for the next iteration.
alphabet A L G O R I T H
weights 68 20 5 30 18 15 19 12
17
5:G 12:H
alphabet A L O R I T GH
weights 68 20 30 18 15 19 17
alphabet A L O R I T GH
weights 68 20 30 18 15 19 17
32
15:I 17
5:G 12:H
alphabet A L O R T IGH
weights 68 20 30 18 19 32
37
alphabet A L O R T IGH
weights 68 20 30 18 19 32
32
15:I 17
5:G 12:H
37
18:R 19:T
alphabet A L O RT IGH
weights 68 20 30 37 32
alphabet A L O RT IGH
weights 68 20 30 37 32
32
15:I 17
5:G 12:H
37
18:R 19:T
50
20:L 30:O
alphabet A LO RT IGH
weights 68 50 37 32
alphabet A LO RT IGH
weights 68 50 37 32
69
32 37
15:I 17
5:G 12:H
18:R 19:T
50
20:L 30:O
38
alphabet A LO RTIGH
weights 68 50 69
alphabet A LO RTIGH
weights 68 50 69
69
32 37
15:I 17
5:G 12:H
18:R 19:T
118
50 68:A
20:L 30:O
alphabet ALO RTIGH
weights 118 69
alphabet ALO RTIGH
weights 118 69
187
69
32 37
15:I 17
5:G 12:H
18:R 19:T
118
50 68:A
20:L 30:O
39
6B
Identify the code for each letter and list the number of bits for each letter and compute the average number
of bits per symbol in this code. Is it less than 3?
With the Huffman tree completed in 6A, we can add bit assignments:
187
69
32 37
15:I 17
5:G 12:H
18:R 19:T
118
50 68:A
20:L 30:O
0 1
0 1
0 1 0 1
0 1
0 1
0 1
The corresponding Huffman Code is shown in the table below:
Symbol Weight Code Number of Bits Probability = /
A 68 11 2 68/187
L 20 100 3 20/187
G 5 0010 4 5/187
O 30 101 3 30/187
R 18 010 3 18/187
I 15 000 3 15/187
T 19 011 3 19/187
H 12 0011 4 12/187
To compute the average bits per symbol, we use:
=
| |∑︁
=1
where | | is the size of the source alphabet, is the number of bits encoding symbol from the alphabet,
and is the probability of symbol appearing. Thus:
=
| |∑︁
=1
=
1
8∑︁
=1
=
1
187
[2(68) + 3(20) + 4(5) + 3(30) + 3(18) + 3(15) + 3(19) + 4(12)]
40
∴ = 2.727
As expected, the average number of bits required for representing each symbol in the alphabet is less than
3, at ≈ 2.727. The compression ratio, while optimal for this alphabet, is not particularly low given
that many of the symbols occur with almost uniform frequency, thus limiting the possible space savings we
could achieve using compression.
6C
Give an example of weights for these 8 symbols that would saturate 3 bits per letter. What would the
Huffman tree look like? Is a Huffman code tree always a full tree?
If every symbol had uniform weights ( = 1) for all symbols in the alphabet, then the average bits per
symbol would saturate at 3 bits per symbol. This is equivalent to a fixed-length encoding scheme (i.e.
ASCII), which uses the same number of bits to represent each symbol, regardless of frequency. The Huffman
tree is shown below:
8
4 4
2 2 2 2
1:A 1:L 1:G 1:O 1:R 1:I 1:T 1:H
0 1
0 1 0 1
0 1 0 1 0 1 0 1
A Huffman code will always produce a full tree; a full binary tree is a tree where every node has either
0 or 2 child nodes. At each round, there are three possible actions to take:
1. 1 and 2 are single elements, not trees. We join them together to form a subtree with parent node
12, left child node 1, and right child node 2. The subtree is full, since the new node 12 has exactly
2 child nodes and 1 and 2 are both leaf nodes with 0 child nodes.
2. 1 is a single element, but 2 is a sub-tree. We join them to form a new subtree with parent node
12, left child node 1, and right child node 2. Node 12 has exactly 2 child nodes - 1 and 2.
Node 1 is a leaf node, so it has 0 child nodes. 2 is the root of a sub-tree that could only have been
created by following Case 1 at some point in the algorithm; thus, the sub-tree rooted at 2 must be a
full tree. Therefore, the overall sub-tree must be a full tree.
3. 1 and 2 are both subtrees. We join them together to form a subtree with parent node 12, left child
nodes 1, and right child node 2. Node 12 has exactly 2 child nodes - 1 and 2, both of which are
roots of subtrees. However, both 1 and 2 are roots of subtrees that could only have been created
41
by following Case 1 or Case 2 at some point in the algorithm; thus both sub-trees rooted at 1 and
2 respectively must be full trees. Therefore, the overall sub-tree must be a full tree.
Therefore, a Huffman code will always produce a full binary tree.
42
Problem 7
Given the following list of = 10 elements:
28 14 7 4 6 30 36 33 10 40
7A
Insert them sequentially into a BST (Binary Search Tree). Compute the total height () and the total
depth (), where is the height of the root. (Note the height of a node is the longest path length to a
leaf whereas its depth is its unique distance from the root).
28
Figure 51: Insert 28 as Root
28
14
Figure 52: Insert 14: 14 < 28, Insert left.
28
14
7
Figure 53: Insert 7: 7 < 28, Move left. 7 < 14, Insert left.
43
28
14
7
4
Figure 54: Insert 4: 4 < 28, Move left. 4 < 14, Move left. 4 < 7, Insert left.
28
14
7
4
6
Figure 55: Insert 6: 6 < 28, Move left. 6 < 14, Move left. 6 < 7, Move left. 6 > 4, Insert right.
44
28
14
7
4
6
30
Figure 56: Insert 30: 30 > 28, Insert right.
28
14
7
4
6
30
36
Figure 57: Insert 36: 36 > 28, Move right. 36 > 30, Insert right.
45
28
14
7
4
6
30
36
33
Figure 58: Insert 33: 33 > 28, Move right. 33 > 30, Move right. 33 < 36, Insert left.
28
14
7
4
6
30
36
3310
Figure 59: Insert 10: 10 < 28, Move left. 10 < 14, Move left. 10 > 7, Insert right.
46
28
14
7
4
6
30
36
3310 40
Figure 60: Insert 40: 40 > 28, Move right. 40 > 30, Move right. 40 > 36, Insert right.
7B
Find , (), () and check the sum rule:
() + () ≤
The following table summarizes the height and depth information of each node using the definitions
described in 7A:
Node ℎ
28 4 0
14 3 1
30 2 1
7 2 2
36 1 2
4 1 3
10 0 3
33 0 3
40 0 3
6 0 4
By definition, is the height of the root node - looking at the table, we see that = 4. There are = 10
nodes in the tree. We can compute () and () as follows:
() =
∑︁
=1
ℎ , () =
∑︁
=1
where ℎ and is the height of node and depth of node respectively.
Thus, computing the total height and total depth, we find: () = 13, () = 22
We can check the sum rule:
() + () ≤ ⇐⇒ 13 + 22 ≤ 40 =⇒ 35 ≤ 40 ✓
47
7C
Insert them sequentially into an empty AVL tree, restoring the AVL property after each insertion. Show the
AVL tree which results after each insertion and name the type of rotation (RR or LL zig-zig or RL or LR
zig-zag).
28 (0)
Figure 61: Insert 28 as Root. There are no child nodes, so the AVL property is maintained.
28 (1)
14 (0)
Figure 62: Insert 14: 14 < 28, Insert left. The AVL property is maintained for each node in the tree, so no
need to rebalance.
28 (2)
14 (1)
7 (0)
14 (0)
7 (0) 28 (0)
Figure 63: Insert 7: 7 < 28, Move left. 7 < 14, Insert left. The AVL property is violated for node 28; this
format fits the case of a left-left single rotation with 1 = 14, 2 = 28, = 7, = , and = .
After performing the single rotation, we obtain the tree on the right, which maintains the AVL property.
48
14 (1)
7 (1) 28 (0)
4 (0)
Figure 64: Insert 4: 4 < 14, Move left. 4 < 7, Insert left. The AVL property is maintained for each node in
the tree, so no need to rebalance.
14 (2)
7 (2) 28 (0)
4 (1)
6 (0)
14 (1)
6 (0) 28 (0)
4 (0) 7 (0)
Figure 65: Insert 6: 6 < 14, Move left. 6 < 7, Move left. 6 > 4, Insert right. he AVL property is violated
for node 7; this format fits the case of a left-right double rotation with 1 = 4, 2 = 6, 3 = 7, = ,
= , = , and = . After performing the double rotation, we obtain the tree on the
right, which maintains the AVL property.
14 (0)
6 (0) 28 (1)
4 (0) 7 (0) 30 (0)
Figure 66: Insert 30: 30 > 14, Move right. 30 > 28, Insert right. The AVL property is maintained for each
node in the tree, so no need to rebalance.
49
14 (1)
6 (0) 28 (2)
4 (0) 7 (0) 30 (1)
36 (0)
14 (0)
6 (0) 30 (0)
4 (0) 7 (0) 28 (0) 36 (0)
Figure 67: Insert 30: 30 > 14, Move right. 30 > 28, Insert right. The AVL property is violated for node
28; this format fits the case of a right-right single rotation with 1 = 28, 2 = 30, = , = ,
and = 36. After performing the single rotation, we obtain the tree on the right, which maintains the AVL
property.
14 (1)
6 (0) 30 (1)
4 (0) 7 (0) 28 (0) 36 (1)
33 (0)
Figure 68: Insert 33. 33 > 14, Move right. 33 > 30, Move right. 33 < 36, Insert left. The AVL property is
maintained for each node in the tree, so no need to rebalance.
50
14 (0)
6 (1) 30 (1)
4 (0) 7 (1) 28 (0) 36 (1)
33 (0)10 (0)
Figure 69: Insert 10. 10 < 14, Move left. 10 > 6, Move right. 10 > 7, Insert right. The AVL property is
maintained for each node in the tree, so no need to rebalance.
14 (0)
6 (1) 30 (1)
4 (0) 7 (1) 28 (0) 36 (0)
33 (0)10 (0) 40 (0)
Figure 70: Insert 40. 40 > 14, Move right. 40 > 30, Move right. 40 > 36, Insert right. The AVL property is
maintained for each node in the tree, so no need to rebalance.
7D
Has the final AVL tree decreased the total height () and the total depth ()? What are the new
values? What is the new value of () + ()?
The following table summarizes the height and depth information of each node using the definitions
described in 7A:
51
Node ℎ
14 3 0
6 2 1
30 2 1
4 0 2
7 1 2
28 0 2
36 1 2
10 0 3
33 0 3
40 0 3
Using the () and () equations above, we compute the new total height and new total depth as:
() = 9 () = 19. Using the AVL tree, we managed to decrease both the total height and total depth;
the sum is given as () + () = 27.
Nicholas Sacco
October 26, 2022
Problem 1
Determine whether the following statements are true or false, and briefly explain why:
1A
If doubling the size ( → 2) causes the execute time () of an algorithm to increase by a factor of 4,
then () ∈ (4).
False. Assume that () ∈ (4). Then by definition:
∃, 0 .. () ≤ 4 ∀ ≥ 0
Assume we operate in the asymptotic region, that is ≥ 0; then () ≤ 4. If we double the input
size from → 2, then per the asymptotic bound:
(2) ≤ 4(2) =⇒ (2) ≤ 8
But we also assumed that doubling the input size from → 2 quadruples the run time:
(2) = 4 () =⇒ (2) ≤ 16
Thus, by doubling the input size from → 2, it is possible to violate the (4) asymptotic bound;
therefore, by contradiction, () ∉ (4).
1B
The height of a binary tree is the maximum number of edges from the root to any leaf path. The maximum
number of nodes in a binary tree of height ℎ is 2ℎ+1 − 1.
True. Let (ℎ) = 2ℎ+1 − 1 be the maximum number of nodes found in a binary tree of height ℎ. Use proof
by induction to prove the claim.
Base case: ℎ = 0. If a tree has height ℎ = 0, then it consists just of the root node. Evaluating the above
equation:
(0) = 21 − 1 = 2 − 1 =⇒ (0) = 1
The base case holds, so we can proceed with the induction step.
Induction step: Assume the claim holds for ℎ, namely the maximum number of nodes in a binary tree
of height ℎ is (ℎ) = 2ℎ+1 − 1. Show that if the claim holds for ℎ, then it must hold for ℎ + 1.
Assume we start with a full binary tree of height ℎ. The ℎTH level of a binary tree can hold a maximum
of 2ℎ nodes; to build a full binary tree of height ℎ + 1, all we have to do is add two child nodes to each leaf
node in the existing height ℎ binary tree. Since there are 2ℎ leaf nodes in a height ℎ binary tree, we need to
1
add 2ℎ × 2 = 2ℎ+1 nodes to build a binary tree of height ℎ + 1 with the maximum number of nodes. By the
induction hypothesis, there are (ℎ) = 2ℎ+1 − 1 total nodes in the height ℎ binary tree. Thus, in the height
ℎ + 1 binary tree, the maximum number of nodes is given by:
(ℎ + 1) = (ℎ) + 2ℎ+1 =
(
2ℎ+1 − 1
)
+ 2ℎ+1 = 2 × 2ℎ+1 − 1 = 2ℎ+2 − 1
Thus, (ℎ + 1) = 2ℎ+2 − 1, and the induction step holds. Thus, we have proven by induction that the
maximum number of nodes in a binary tree of height ℎ is (ℎ) = 2ℎ+1 − 1.
1C
In a binary search tree with no repeated keys, deleting the node with key , followed by deleting the node
with key , will result in the same search tree as deleting the node with key , then deleting the node with
key .
False. We discussed this problem in class today - Dr. Brower mentioned there is a counter-example that
looked like one of the following:
I haven’t been able to quite work out the counterexample.
1D
Inserting numbers 1 . . . into a binary min-heap in that order will take () time.
True. Inserting any sequence of distinct integers into a binary min-heap is accomplished in () time; we
use the array as is, and then heapify the tree bottom-to-top.
2
1E
The second smallest element in a binary min-heap with all elements with distinct values will always be a
child of the root.
True. Let be the smallest element in the binary min-heap (i.e., the root) and let
∗ be the second
smallest element in the binary min-heap. Thus <
∗ < for all other elements in the heap. Assume
∗ is not already a child of the root node. The binary min-heap requires that parent nodes are smaller in
value than their child nodes: < 1 , < 2 . If
∗ is not already a child of the root node, it must be
somewhere else in the rest of the tree: assume ∗ is a child node to node ′ . By construction, ′ > ∗; thus
the min-heap property is violated. To restore the requirement, ∗ must “bubble up” the tree, eventually
settling as a child of the root node: <
∗. Thus, the second smallest element in a binary min-heap with
distinct values will always be a child of the root node.
3
Problem 2
This exercise is to learn binary search tree operations:
2A
Draw the sequence of binary search trees which results from inserting the following values in left-to-right
order, assuming no balancing:
15, 10, 31, 25, 34, 56, 78, 12, 14, 13
15
Figure 1: Insert 15 as Root
15
10
Figure 2: Inserting 10: 10 < 15, Insert Left.
15
10 31
Figure 3: Inserting 31: 31 > 15, Insert Right.
4
15
10 31
25
Figure 4: Inserting 25: 25 > 15, Move right. 25 < 31, Insert left.
15
10 31
25 34
Figure 5: Inserting 34: 34 > 15, Move right. 34 > 31, Insert right.
15
10 31
25 34
56
Figure 6: Inserting 56: 56 > 15, Move right. 56 > 31, Move right. 56 > 34, Insert right.
5
15
10 31
25 34
56
78
Figure 7: Inserting 78: 78 > 15, Move right. 78 > 31, Move right. 78 > 34, Move right. 78 > 56, Insert right.
15
10 31
25 34
56
78
12
Figure 8: Inserting 12: 12 < 15, Move left. 12 > 10, Insert right.
6
15
10 31
25 34
56
78
12
14
Figure 9: Inserting 14: 14 < 15, Move left. 14 > 10, Move right. 14 > 12, Insert right.
15
10 31
25 34
56
78
12
14
13
Figure 10: Inserting 13: 13 < 15, Move left. 13 > 10, Move right. 13 > 12, Move right. 13 < 14, Insert left.
2B
Starting from the tree at the end of the previous part, draw the sequence that results from deleting the
following nodes in left-to-right order:
7
15, 31, 12, 14
We start with the complete tree:
15
10 31
25 34
56
78
12
14
13
Figure 11: Full Tree
To delete 15, we note that it has two child nodes, and thus we must use the rotation scheme. Let = 15,
= , ℓ = 10, = 31, = 25, and = . The rotation scheme proceeds as follows:
1. Move the sub-tree rooted at to .
2. Set to be the parent of .
3. Set to be the parent of . (Here, = because we are deleting the root node - we must replace
it with another node to maintain the tree.)
4. Set to be the parent of ℓ.
5. Clear the pointers associated with node - it is now deleted from the BST.
Following this procedure, we arrive at the tree:
8
25
10 31
34
56
78
12
14
13
Figure 12: Delete 15: Set 25 (the successor to 15) to be the parent of the left and right subtrees rooted at
10 and 31 respectively.
To delete 31, we note that it now has a single child node; thus we just need to adjust the pointers to
move the remaining nodes to their correct locations in the BST:
25
10 34
56
78
12
14
13
Figure 13: Delete 31: Since there is only one child node, we just need to adjust pointers to move the subtree
rooted at 34 up a level to maintain the BST property.
To delete 12, we note that it has a single child node; thus we just need to repeat the same process as
above: adjust the pointers to move the remaining nodes to their correct locations in the BST:
9
25
10 34
56
78
14
13
Figure 14: Delete 12: Since there is only one child node, we just need to adjust pointers to move the subtree
rooted at 14 up a level to maintain the BST property.
To delete 14, we note that it has a single child node; thus we just need to repeat the same process as
above: adjust the pointers to move the remaining nodes to their correct locations in the BST:
25
10 34
56
78
13
Figure 15: Delete 14: Since there is only one child node, we just need to adjust pointers to move the subtree
rooted at 13 up a level to maintain the BST property.
2C
After deleting them, draw the sequence of reinserting left-to-right in reverse order:
14, 12, 31, 15
into the tree, and comment on the result.
10
25
10 34
56
78
13
14
Figure 16: Inserting 14: 14 < 25, Move left. 14 > 10, Move right. 14 > 13, Insert right.
25
10 34
56
78
13
1412
Figure 17: Inserting 12: 12 < 25, Move left. 12 > 10, Move right. 12 < 13, Insert left.
11
25
10 34
56
78
13
1412
31
Figure 18: Inserting 31: 31 > 25, Move right. 31 < 24, Insert left.
25
10 34
56
78
13
1412
31
15
Figure 19: Inserting 15: 15 < 25, Move left. 15 > 10, Move right. 15 > 13, Move right. 15 > 14, Insert right.
The tree is clearly different than the original starting tree at the end of problem 2A. In general, it does
not appear that deleting a set of nodes and inserting them back in reverse order recovers the original tree.
12
Problem 3
Problem 3A: Exercises 6.1-3, 6.1-4, 6.1-6, 6.3-3
Exercise 6.1-3
Show that in any sub-tree of a max-heap, the root of the sub-tree contains the largest value occurring
anywhere in that sub-tree.
Let = {[] : ∈ []} be an -element max-heap with nodes = 1, 2, . . . . Let () be the parent to
node . A max-heap satisfies the following properties:
• The root node [1] contains the largest element in the heap. The root node has no parent node:
() = .
• Consider non-root node , ≠ 1. The max-heap property is described as follows: [()] ≥ [].
The max-heap property holds for all non-root nodes.
Since is a valid max-heap, the max-heap property will hold for all non-root nodes = 2, 3, . . . ;
namely, [()] ≥ [] ∀ ≥ 2. Let 1 be set of all paths we could traverse starting at the root of the sub-tree
and stopping at a leaf node. Since the max-heap property guarantees that [()] ≥ [], if we traverse
along nodes in path =
(
[1] 2 3 . . . ℓ
)
of length ℓ, we construct the partial ordering:
[1] ≥ 2 ≥ 3 ≥ . . . ≥ ℓ
Thus, pick any node ∗ as the root of subtree ∗ . Let ∗ be the set of all paths we could traverse starting
at node ∗ and stopping at a leaf node. Since we are not changing the number of nodes in tree , every path
′ ∈ ∗ must be a sub-path of some path ∈ 1. Since path ∈ 1 corresponds to the partial ordering:
[1] ≥ 2 ≥ 3 ≥ . . . ≥ ℓ
And path ′ =
(
[∗] ′2 ′3 . . . ℓ′
) ∈ ∗ of length ℓ′ is a subset of such a path, ′ must also correspond to
a partial ordering:
[∗] ≥ ′2 ≥ ′3 ≥ . . . ≥ ′ℓ′
Thus, the max-heap property is preserved even if we look at a sub-tree ∗ ⊆ ; thus, the root ∗ of any
subtree ∗ must contain the largest value in that subtree.
Exercise 6.1-4
Where in a max-heap might the smallest element reside, assuming that all elements are distinct?
The smallest element in a max-heap with all distinct elements must reside at a leaf node. Let be the
minimum element in the max-heap; by definition, < for all elements in the max-heap. Recall that
max-heap property - for node all nodes ≥ 2 (i.e., all non-root nodes), [()] > []; in other words, the
parent every non-root node of is larger than node itself. Assume that was located at non-leaf node
: [ ] = . Let node contain element : [] = . Let node be the parent to node . Since
() = , For the max-heap property to hold, we require that [()] > [] ⇐⇒ [ ] > []. But we
have assumed that was located at node , while some other distinct element > was located at
node . Thus, the max-heap property is not satisfied, since ≯ by definition. Thus, cannot be
found on a non-leaf node in a max-heap; it must be found at a leaf node where it has no child nodes.
13
Exercise 6.1-6
Is the array with values:
23, 17, 14, 6, 13, 10, 1, 5, 7, 12
a max heap?
It is much easier to analyze the structure graphically:
23
17 14
6 13 10 1
5 7 12
Recall the max-heap property: for non-root node with parent node (), we require [()] ≥ []. We see
that node 7 has parent 6; thus the max-heap property is violated. Thus this structure is NOT a max-heap.
Exercise 6.3-3
Show that there are at most: ⌈
2ℎ+1
⌉
nodes of height ℎ in any -element heap.
First, assume that = 2 − 1 ∈ N, ≥ 1. If we construct a binary heap with these elements, the
resulting tree is a perfect binary tree. In a perfect binary tree with 2 − 1 elements, the number of nodes
of height ℎ is easy to calculate, since the sum of the height and depth of nodes in the tree are constant:
ℎ + = − 1. At depth , there are () = 2 nodes; using the height-depth invariant, the number of nodes
of height ℎ in a perfect binary tree with 2 − 1 elements is given as:
2−1 (ℎ) = 2 = 2−ℎ−1 = 2
2ℎ+1
=
⌈
2 − 1
2ℎ+1
⌉
∴ 2−1 (ℎ) =
⌈
2ℎ+1
⌉
14
Now, let’s assume that = 2 < 2 − 1, ∈ N, ≥ 1, such that ⌈⌉ = ; that is, 2 is the first power of
2 greater than . Since we are constructing a heap, we completely fill a level with elements before inserting
elements in the next level; thus, since < 2 − 1, there will be several missing nodes in the last level of the
perfect binary tree, as illustrated in the example below:
1
2 3
4 5 6 7
8 9 10 11 12 13 14 15
Figure 20: Binary heap with = 10 elements (Nodes 1 - 10) compared to perfect binary heap with =
24 − 1 = 15 elements (Nodes 1 - 15). Nodes 11 - 15 are found in the perfect binary tree, but not in the heap
with 10 elements.
To recover the -element heap from the 2−1 element perfect tree, we just need to delete extra leaf nodes in
the last row of the perfect tree. Let 0 be the number of deleted nodes of height 0. By definition, the height
ℎ of a node is the longest path to a leaf node. If we delete 0 leaf nodes, each of height 0, then ⌊0/2⌋ parent
nodes, previously of height 1, become new leaf nodes of height 0. Thus, the number of nodes of height ℎ = 0
in the -element heap is given as:
(0) = 2−1 (0) − 0 +
⌊ 0
2
⌋
∴ (0) ≤ 2−1 (0)
15
12 3
4 5 6 7
8 9 10
Figure 21: Binary heap with = 10 elements (Nodes 1 - 10) after deleting the extra nodes. Nodes 6 and 7,
which were previously parent nodes of height ℎ = 1, are now leaf nodes of height ℎ = 0.
But this change propagates up the tree! In the perfect tree, there were originally 2−1 (1) nodes of height
1. Let 1 be the number of nodes, originally of height 1, but are now height 0. After updating the height of
1 nodes, ⌊1/2⌋ parent nodes, originally of height 2, are now one level closer to the leaves, and thus become
nodes of height 1. Thus, the number of nodes of height ℎ = 1 in the -element heap is given as:
(1) = 2−1 (1) − 1 +
⌊ 1
2
⌋
∴ (1) ≤ 2−1 (1)
Without loss of generality, we can repeat this argument up the entire tree. Since we have already
computed 2−1 (ℎ):
2−1 (ℎ) =
⌈
2ℎ+1
⌉
And we can upper bound (ℎ) with 2−1 (ℎ) for each height ℎ, we have that:
(ℎ) ≤
⌈
2ℎ+1
⌉
□
Problem 3B: Exercises 12.3-2, 12.3-3, 12.3-4, B.5-4
Exercise 12.3-2
Suppose that we construct a binary search tree by repeatedly inserting distinct values into the tree. Argue
that the number of nodes examined in searching for a value in the tree is one plus the number of of nodes
examined when the value was first inserted into the tree.
16
Let be the number of nodes examined when inserting node into the binary search tree. Let be the
set of nodes visited when inserting node into the binary search tree. Every time a node is visited, add it
to . To insert node into the binary search tree, we start at the root node. Append the root node to
, and perform the comparison to determine which side of the subtree to place . Move to the next node
accordingly; say we move to node 2. Then, we append 2 to the node list , and perform the comparison
to determine which side of the subtree rooted at node 2 to place . This process until we finally place - we
will have examined nodes = {, 2, 3 . . . }, where | | = , to determine the proper location of
in the binary search tree. Some time later, we wish to search for node in the binary search tree. Let ′ be
the set of nodes visited when searching for in the binary search tree. We start the search at the root node.
Append the root to ′ , and perform the comparison to determine which side of the subtree is located.
Move to the next node accordingly; we will move to node 2, the same node we moved to when looking for
the location to place ! We perform the comparison again, moving to node 3. At node 3, we append it to
′ and continue. We will traverse the same nodes: , 2, 3, . . . . At , we perform the comparison,
which moves us to node ∗, which contains . Once at ∗, we must perform the last comparison to confirm
we have found ; thus, we must evaluate ′ = |′ | = | ∪ ∗ | = + 1. Thus, when searching for , we must
examine + 1 nodes.
Exercise 12.3-3
We can sort a given set of numbers by first building a binary search tree containing these numbers (using
TREE-INSERT repeatedly to insert the numbers one by one) and then printing the numbers by an in-order
tree walk. What are the worst-case and best-case running times for this sorting algorithm?
Let () be the time required to print out the contents of any -element binary search tree. By using the
recursive definition of the in-order-print function, we have that () = Θ() for any -element binary search
tree. The most significant portion of the proposed sorting algorithm is the time required to build the binary
search tree by inserting the elements into the tree one-by-one. In the many tree-based structures we have
studied so far, we have seen that insertion operations require time that scales with the height of the tree.
In the best-case insertion, the elements that are inserted into the binary search tree form a perfect binary
tree with height Θ(lg ). Inserting a new element into an existing tree of height Θ(lg ) requires traversal
down a path of length Θ(lg ). Thus, building a binary search tree by inserting elements one-by-one takes
() = Θ( lg ) time in the best-case insertion. In the worse-case insertion, then elements that are inserted
into the binary search tree form a linked list with height Θ() - this occurs if the elements are already
sorted. Inserting a new element into an existing linked list of height Θ() requires traversal down a path of
length Θ(). Thus, building a binary search tree by inserting elements one-by-one takes () = Θ(2)
time in the worst-case insertion. Thus, the total time for the sorting algorithm is:
() =
{
() + () = Θ( lg ) + Θ() = Θ( lg ),
() + () = Θ(2) + Θ() = Θ(2),
Exercise 12.3-4
Is the operation of deletion ”commutative” in the sense that deleting and then from a binary search tree
leaves the same tree as deleting then ? Argue why it is or give a counterexample.
See problem 1C, this is the same question.
Exercise B.5-4
Use induction to show that a nonempty binary tree with nodes has height at least ⌊lg ⌋.
17
Base case: Let = 1. Since the binary tree consists of just 1 node, it must have height 0; thus (1) = 0.
Using the equation () ≥ ⌊lg ⌋:
(1) ≥ ⌊lg 1⌋ =⇒ (1) ≥ 0
Thus, the base case holds and we can proceed with the rest of the induction.
Induction step: Assume () ≥ ⌊lg ⌋; show that if this holds, then ( + 1) ≥ ⌊lg + 1⌋.
Recall the definition of the height of a binary tree: the height is the length of the longest path from
the root node to a leaf node. Thus, there are two extreme ways of organizing a binary tree with nodes -
a linked list of height − 1, and a complete binary tree of height ≈ lg (We will be more precise with the
scaling later). Thus, we can bound the height () of any tree with nodes as:
lg ⪅ () ≤ − 1
Let 2−1 ≤ ≤ 2 − 2. In other words, = 2 , ∈ [ − 1, ) By the induction hypothesis:
() ≥ ⌊lg ⌋ = ⌊lg 2⌋ = ⌊⌋ = − 1
Thus, () ≥ − 1. To get + 1 elements in the tree, we add one more node. Assume we can place it
such that ( + 1) = (). Thus is possible since we cannot form a perfect tree with ∈ [2−1, 2 − 2]
elements; thus, we can always form a tree where adding an additional node does not change the height of
the tree. Thus, ( + 1) ≥ − 1. Since = 2 , we can write + 1 = 2 for some > , ∈ [2−1, 2 − 2].
Thus:
⌊lg + 1⌋ = ⌊lg 2⌋ = ⌊⌋ = − 1
.
Since ( + 1) ≥ − 1, we can write:
( + 1) ≥ − 1 = ⌊lg + 1⌋ =⇒ ( + 1) ≥ ⌊lg + 1⌋
Now assume = 2 − 1; in other words, we can form a perfect tree with elements; the minimum height
of an element tree is the same: () ≥ − 1. Now, when we add one more element, the height of the
perfect binary tree must increase; thus ( + 1) ≥ () + 1 = ( − 1) + 1 =⇒ ( + 1). But:
+ 1 = (2 − 1) + 1 = 2 =⇒ ⌊lg + 1⌋ = ⌊lg 2⌋ =
Therefore, ( + 1) ≥ ⌊lg + 1⌋. Since ( + 1) ≤ ⌊lg + 1⌋ in both scenarios, the induction step holds.
Thus, by induction, we have shown that the minimum height of a binary tree with nodes is () ≥ ⌊lg ⌋.
18
Problem 4
Determine whether the following statements are true or false, and briefly explain why:
4A
A heapsort algorithm for a given list first forms a max-heap with the elements in that list, then extracts
the elements of the heap one by one from the top. This algorithm will sort a list of elements in time of
(log ).
False. Heapsort has a run-time of ( log ) - each element must roughly travel a path of length (log )
for the max heap to be maintained after each iteration. Since there are elements to sort, heapsort takes
( log ) time to sort elements.
4B
A connected, undirected, acyclic graph with nodes and − 1 edges is a tree.
True. A tree is defined as a connected, undirected, acylic graph; if there are nodes in the tree and the
entire structure is connected, then there must be − 1 edges.
4C
A binary heap of elements is a full binary tree for all possible values of .
False. A full binary tree is one where each node has either 0 or 2 child nodes. A binary heap with elements,
while always complete (meaning it is filled consecutively), does not have to be full; it is possible for a node
to have just one child node, as shown in the counterexample below:
4
10 5
12
4D
The following tree is a valid min-heap:
19
410
12 14
5
True. A min-heap satisfies the min-heap property: [()] ≤ [] ∀ ≥ 2. In other words, the parent of
non-root node must be smaller than node . Each node in the above tree satisfies the min-heap property,
so the above tree is a valid min-heap.
4E
The following tree can appear in a binomial min-heap:
4
10
12 14
5
False. A binomial heap order contains binary trees that have depths following the binomial coefficients
found in Pascal’s triangle; thus, the depths should take the form 1, 2, 1. However, in the given heap, we see
the depths take the form 1, 2, 2, which are not the binomial coefficients. Thus, this tree cannot appear in
a binomail min-heap.
4F
Given an array of positive integers [], maximizing ∑ · [] over permutations of the array requires sorting
[] in assigning order.
True. Sorting is just a special case of the optimization problem:
max
∑︁
· []
Thus, if we want to find the above maximum, all we really need to do is just sort the array - we will find
the maximum sum, no special optimization techniques required.
20
Problem 5
Given the following list of elements:
35, 22, 11, 98, 55, 66, 77, 80, 85, 90, 95
5A
Draw the sequence of binary min-heaps which results from inserting the following values in the order in
which they appear into an empty heap.
The min-heap satisfies the min-heap property: [()] ≤ ∀ ≥ 2. To build the min-heap, we first start
by throwing every element into the binary heap, ignoring the min-heap property:
35
22
98
80 85
55
90 95
11
66 77
Figure 22: Starting min-heap
Then we run the heapify algorithm, “bubbling” low-value nodes to the top of the heap by swapping node
with its parent node () if [()] > []. The incremental binary heaps are shown in the figures below:
35
22
98
80 85
55
90 95
11
66 77
35
22
80
98 85
55
90 95
11
66 77
Figure 23: Node 77 - no child nodes, pass. Node 66 - no child nodes, pass. Node 55: 55 < 90 and 55 < 95,
min-heap property holds, no swaps necessary. Node 98: 98 > 80 and 98 > 85, swap node 98 with node 80,
the smaller of the two child nodes.
21
35
22
80
98 85
55
90 95
11
66 77
11
22
80
98 85
55
90 95
35
66 77
Figure 24: Node 11: 11 < 66 and 11 < 77, min-heap property holds, no swaps necessary. Node 22: 22 < 80
and 20 < 55, min-heap property holds, no swaps necessary. Node 35: 35 > 22 and 35 > 11, swap node 35
with node 11, the smaller of the two child nodes.
The final min heap is shown below:
11
22
80
98 85
55
90 95
35
66 77
Figure 25: Final min-heap - the min-heap property holds for all nodes.
5B
Compare this answer with inserting them into the BST tree.
35
Figure 26: Insert 35 as Root
22
35
22
Figure 27: Inserting 22: 22 < 35, Insert left.
35
22
11
Figure 28: Inserting 11: 11 < 35, Move left. 11 < 22, Insert left.
35
22
11
98
Figure 29: Inserting 98: 98 > 35, Insert right.
35
22
11
98
55
Figure 30: Inserting 55: 55 > 35, Move right. 55 < 98, Insert left.
23
35
22
11
98
55
66
Figure 31: Inserting 66: 66 > 35, Move right. 66 < 98, Move left. 66 > 55, Insert right.
35
22
11
98
55
66
77
Figure 32: Inserting 77: 77 > 35, Move right. 77 < 98, Move left. 77 > 55, Move right. 77 > 66, Insert right.
24
35
22
11
98
55
66
77
80
Figure 33: Inserting 80: 80 > 35, Move right. 80 < 98, Move left. 80 > 55, Move right. 80 > 66, Move right.
80 > 77, Insert right.
35
22
11
98
55
66
77
80
85
Figure 34: Inserting 85: 85 > 35, Move right. 85 < 98, Move left. 85 > 55, Move right. 85 > 66, Move right.
85 > 77, Move right. 85 > 80, Insert right.
25
35
22
11
98
55
66
77
80
85
90
Figure 35: Inserting 90: 90 > 35, Move right. 90 < 98, Move left. 90 > 55, Move right. 90 > 66, Move right.
90 > 77, Move right. 90 > 80, Move right. 90 > 85, Insert right.
26
35
22
11
98
55
66
77
80
85
90
95
Figure 36: Inserting 95: 95 > 35, Move right. 95 < 98, Move left. 95 > 55, Move right. 95 > 66, Move right.
95 > 77, Move right. 95 > 80, Move right. 95 > 85, Move right. 95 > 90, Insert right.
A binary search tree is a relatively poor data structure for this particular set of data given that most of
the elements already appear in sorted order, resulting in a highly unbalanced tree.
5C
Compare this answer with inserting them into the AVL tree.
We can improve the balance in the structure by using the AVL tree which imposes the following property
on each node in the tree. Let () and () be the left subtree rooted at node and the right subtree
rooted at node respectively. Let () and () be the height of left subtree () and right subtree ()
respectively. The AVL property requires:
| () − () | ≤ 1 ∀
Maintaining this property requires careful balancing via single rotations and double rotations, as illus-
trated by the four cases below:
27
Figure 37: AVL Single Rotation
Figure 38: AVL RL Double Rotation
Figure 39: AVL LR Double Rotation
28
35 (0)
Figure 40: Insert 35 as Root. There are no child nodes, so the AVL property is maintained.
35 (1)
22 (0)
Figure 41: Insert 22: 22 < 35, Insert left. The AVL property is maintained for each node in the tree, so no
need to rebalance.
35 (2)
22 (1)
11 (0)
22 (1)
11 (0) 35 (0)
Figure 42: Insert 11: 11 < 35, Move left. 11 < 22, Insert left. The AVL property is violated for node 35; this
format fits the case of a single rotation with 1 = 22, 2 = 35, = 11, = , and = . After
performing the single rotation, we obtain the tree on the right, which maintains the AVL property.
22 (1)
11 (0) 35 (1)
98 (0)
Figure 43: Insert 98: 98 > 22, Move right. 98 > 35, Insert right. The AVL property is maintained for each
node in the tree, so no need to rebalance.
29
22 (2)
11 (0) 35 (2)
98 (1)
55 (0)
22 (1)
11 (0) 55 (0)
35 (0) 98 (0)
Figure 44: Insert 55: 55 > 22, Move right. 55 > 35, Move right. 55 < 98, Insert left. The AVL property is
violated for node 35; this format fits the case of a double rotation with 1 = 98, 2 = 55, 3 = 35, = ,
= , = , and = . After performing the double rotation, we obtain the tree on the
right, which maintains the AVL property.
30
22 (2)
11 (0) 55 (1)
35 (0) 98 (1)
66 (0)
55 (0)
22 (0) 98 (1)
11 (0) 35 (0) 66 (0)
Figure 45: Insert 66: 66 > 22, Move right. 66 > 55, Move right. 66 < 98, Insert left. The AVL property
is violated for node 22; this format fits the case of a single rotation with 1 = 22, 2 = 55, = 11, = 35,
and = 98. After performing the single rotation, we obtain the tree on the right, which maintains the AVL
property.
31
55 (1)
22 (0) 98 (2)
11 (0) 35 (0) 66 (1)
77 (0)
55 (0)
22 (0) 77 (0)
11 (0) 35 (0) 66 (0) 98 (0)
Figure 46: Insert 77: 77 > 66, Move right. 77 < 98, Move left. 77 > 66, Insert right. The AVL property is
violated for node 98; this format fits the case of a double rotation with 1 = 66, 2 = 77, 3 = 98, = ,
= , = and = . After performing the single rotation, we obtain the tree on the
right, which maintains the AVL property.
32
55 (1)
22 (0) 77 (1)
11 (0) 35 (0)
66 (0) 98 (1)
80 (0)
Figure 47: Insert 80: 80 > 55, Move right. 80 > 77, Move right. 80 < 98, Insert left. The AVL property is
maintained for each node in the tree, so no need to rebalance.
33
55 (2)
22 (0) 77 (2)
11 (0) 35 (0)
66 (0) 98 (2)
80 (1)
85 (0)
55 (1)
22 (0) 77 (1)
11 (0) 35 (0) 66 (0) 85 (0)
80 (0) 98 (0)
Figure 48: Insert 85: 85 > 55, Move right. 85 > 77, Move right. 85 < 98, Move left. 85 > 80, Insert right.
The AVL property is violated for node 98; this format fits the case of a double rotation with 1 = 80, 2 = 85,
3 = 98, = , = , = and = . After performing the single rotation, we obtain
the tree on the right, which maintains the AVL property.
34
55 (2)
22 (0) 77 (2)
11 (0) 35 (0) 66 (0) 85 (1)
80 (0) 98 (1)
90 (0)
55 (1)
22 (0) 85 (0)
11 (0) 35 (0)
77 (0) 98 (1)
66 (0) 80 (0) 90 (0)
Figure 49: Insert 90: 90 > 55, Move right. 90 > 77, Move right. 90 > 85, Move right. 90 < 98, Insert left.
The AVL property is violated for node 77; this format fits the case of a single rotation with 1 = 77, 2 = 85,
= 66, = 80, and = 98. After performing the single rotation, we obtain the tree on the right, which
maintains the AVL property.
35
55 (2)
22 (0) 85 (1)
11 (0) 35 (0)
77 (0) 98 (2)
66 (0) 80 (0) 90 (1)
95 (0)
55 (1)
22 (0) 85 (0)
11 (0) 35 (0)
77 (0) 95 (0)
66 (0) 80 (0) 90 (0) 98 (0)
Figure 50: Insert 95: 95 > 55, Move right. 95 > 85, Move right. 95 < 98, Move left. 95 > 90, Insert right.
The AVL property is violated for node 98; this format fits the case of a double rotation with 1 = 90, 2 = 95,
3 = 98, = , = , = and = . After performing the double rotation, we
obtain the tree on the right, which maintains the AVL property.
As shown above, the AVL tree is signficantly more balanced than the binary search tree!
36
Problem 6
You are interested in compression. Given a file with characters, you want to find the binary code which
satisfies the prefix property (no conflicts) and which minimizes the number of bits required. As an example,
consider an alphabet with 8 symbols, with relative weights (frequency) of appearance in an average text file
given below:
alphabet A L G O R I T H
weights 68 20 5 30 18 15 19 12
6A
Determine the Huffman code by constructing a tree with minimum external path length:
∑︁
=1
(Arrange tree with smaller weights to the left)
At each round, select the two smallest weights 1, 2 , 1 ≤ 2, build tree with parent 12 = 1 + 2, left
child 1, and right child 2. Put symbol 12 back into the weight table for the next iteration.
alphabet A L G O R I T H
weights 68 20 5 30 18 15 19 12
17
5:G 12:H
alphabet A L O R I T GH
weights 68 20 30 18 15 19 17
alphabet A L O R I T GH
weights 68 20 30 18 15 19 17
32
15:I 17
5:G 12:H
alphabet A L O R T IGH
weights 68 20 30 18 19 32
37
alphabet A L O R T IGH
weights 68 20 30 18 19 32
32
15:I 17
5:G 12:H
37
18:R 19:T
alphabet A L O RT IGH
weights 68 20 30 37 32
alphabet A L O RT IGH
weights 68 20 30 37 32
32
15:I 17
5:G 12:H
37
18:R 19:T
50
20:L 30:O
alphabet A LO RT IGH
weights 68 50 37 32
alphabet A LO RT IGH
weights 68 50 37 32
69
32 37
15:I 17
5:G 12:H
18:R 19:T
50
20:L 30:O
38
alphabet A LO RTIGH
weights 68 50 69
alphabet A LO RTIGH
weights 68 50 69
69
32 37
15:I 17
5:G 12:H
18:R 19:T
118
50 68:A
20:L 30:O
alphabet ALO RTIGH
weights 118 69
alphabet ALO RTIGH
weights 118 69
187
69
32 37
15:I 17
5:G 12:H
18:R 19:T
118
50 68:A
20:L 30:O
39
6B
Identify the code for each letter and list the number of bits for each letter and compute the average number
of bits per symbol in this code. Is it less than 3?
With the Huffman tree completed in 6A, we can add bit assignments:
187
69
32 37
15:I 17
5:G 12:H
18:R 19:T
118
50 68:A
20:L 30:O
0 1
0 1
0 1 0 1
0 1
0 1
0 1
The corresponding Huffman Code is shown in the table below:
Symbol Weight Code Number of Bits Probability = /
A 68 11 2 68/187
L 20 100 3 20/187
G 5 0010 4 5/187
O 30 101 3 30/187
R 18 010 3 18/187
I 15 000 3 15/187
T 19 011 3 19/187
H 12 0011 4 12/187
To compute the average bits per symbol, we use:
=
| |∑︁
=1
where | | is the size of the source alphabet, is the number of bits encoding symbol from the alphabet,
and is the probability of symbol appearing. Thus:
=
| |∑︁
=1
=
1
8∑︁
=1
=
1
187
[2(68) + 3(20) + 4(5) + 3(30) + 3(18) + 3(15) + 3(19) + 4(12)]
40
∴ = 2.727
As expected, the average number of bits required for representing each symbol in the alphabet is less than
3, at ≈ 2.727. The compression ratio, while optimal for this alphabet, is not particularly low given
that many of the symbols occur with almost uniform frequency, thus limiting the possible space savings we
could achieve using compression.
6C
Give an example of weights for these 8 symbols that would saturate 3 bits per letter. What would the
Huffman tree look like? Is a Huffman code tree always a full tree?
If every symbol had uniform weights ( = 1) for all symbols in the alphabet, then the average bits per
symbol would saturate at 3 bits per symbol. This is equivalent to a fixed-length encoding scheme (i.e.
ASCII), which uses the same number of bits to represent each symbol, regardless of frequency. The Huffman
tree is shown below:
8
4 4
2 2 2 2
1:A 1:L 1:G 1:O 1:R 1:I 1:T 1:H
0 1
0 1 0 1
0 1 0 1 0 1 0 1
A Huffman code will always produce a full tree; a full binary tree is a tree where every node has either
0 or 2 child nodes. At each round, there are three possible actions to take:
1. 1 and 2 are single elements, not trees. We join them together to form a subtree with parent node
12, left child node 1, and right child node 2. The subtree is full, since the new node 12 has exactly
2 child nodes and 1 and 2 are both leaf nodes with 0 child nodes.
2. 1 is a single element, but 2 is a sub-tree. We join them to form a new subtree with parent node
12, left child node 1, and right child node 2. Node 12 has exactly 2 child nodes - 1 and 2.
Node 1 is a leaf node, so it has 0 child nodes. 2 is the root of a sub-tree that could only have been
created by following Case 1 at some point in the algorithm; thus, the sub-tree rooted at 2 must be a
full tree. Therefore, the overall sub-tree must be a full tree.
3. 1 and 2 are both subtrees. We join them together to form a subtree with parent node 12, left child
nodes 1, and right child node 2. Node 12 has exactly 2 child nodes - 1 and 2, both of which are
roots of subtrees. However, both 1 and 2 are roots of subtrees that could only have been created
41
by following Case 1 or Case 2 at some point in the algorithm; thus both sub-trees rooted at 1 and
2 respectively must be full trees. Therefore, the overall sub-tree must be a full tree.
Therefore, a Huffman code will always produce a full binary tree.
42
Problem 7
Given the following list of = 10 elements:
28 14 7 4 6 30 36 33 10 40
7A
Insert them sequentially into a BST (Binary Search Tree). Compute the total height () and the total
depth (), where is the height of the root. (Note the height of a node is the longest path length to a
leaf whereas its depth is its unique distance from the root).
28
Figure 51: Insert 28 as Root
28
14
Figure 52: Insert 14: 14 < 28, Insert left.
28
14
7
Figure 53: Insert 7: 7 < 28, Move left. 7 < 14, Insert left.
43
28
14
7
4
Figure 54: Insert 4: 4 < 28, Move left. 4 < 14, Move left. 4 < 7, Insert left.
28
14
7
4
6
Figure 55: Insert 6: 6 < 28, Move left. 6 < 14, Move left. 6 < 7, Move left. 6 > 4, Insert right.
44
28
14
7
4
6
30
Figure 56: Insert 30: 30 > 28, Insert right.
28
14
7
4
6
30
36
Figure 57: Insert 36: 36 > 28, Move right. 36 > 30, Insert right.
45
28
14
7
4
6
30
36
33
Figure 58: Insert 33: 33 > 28, Move right. 33 > 30, Move right. 33 < 36, Insert left.
28
14
7
4
6
30
36
3310
Figure 59: Insert 10: 10 < 28, Move left. 10 < 14, Move left. 10 > 7, Insert right.
46
28
14
7
4
6
30
36
3310 40
Figure 60: Insert 40: 40 > 28, Move right. 40 > 30, Move right. 40 > 36, Insert right.
7B
Find , (), () and check the sum rule:
() + () ≤
The following table summarizes the height and depth information of each node using the definitions
described in 7A:
Node ℎ
28 4 0
14 3 1
30 2 1
7 2 2
36 1 2
4 1 3
10 0 3
33 0 3
40 0 3
6 0 4
By definition, is the height of the root node - looking at the table, we see that = 4. There are = 10
nodes in the tree. We can compute () and () as follows:
() =
∑︁
=1
ℎ , () =
∑︁
=1
where ℎ and is the height of node and depth of node respectively.
Thus, computing the total height and total depth, we find: () = 13, () = 22
We can check the sum rule:
() + () ≤ ⇐⇒ 13 + 22 ≤ 40 =⇒ 35 ≤ 40 ✓
47
7C
Insert them sequentially into an empty AVL tree, restoring the AVL property after each insertion. Show the
AVL tree which results after each insertion and name the type of rotation (RR or LL zig-zig or RL or LR
zig-zag).
28 (0)
Figure 61: Insert 28 as Root. There are no child nodes, so the AVL property is maintained.
28 (1)
14 (0)
Figure 62: Insert 14: 14 < 28, Insert left. The AVL property is maintained for each node in the tree, so no
need to rebalance.
28 (2)
14 (1)
7 (0)
14 (0)
7 (0) 28 (0)
Figure 63: Insert 7: 7 < 28, Move left. 7 < 14, Insert left. The AVL property is violated for node 28; this
format fits the case of a left-left single rotation with 1 = 14, 2 = 28, = 7, = , and = .
After performing the single rotation, we obtain the tree on the right, which maintains the AVL property.
48
14 (1)
7 (1) 28 (0)
4 (0)
Figure 64: Insert 4: 4 < 14, Move left. 4 < 7, Insert left. The AVL property is maintained for each node in
the tree, so no need to rebalance.
14 (2)
7 (2) 28 (0)
4 (1)
6 (0)
14 (1)
6 (0) 28 (0)
4 (0) 7 (0)
Figure 65: Insert 6: 6 < 14, Move left. 6 < 7, Move left. 6 > 4, Insert right. he AVL property is violated
for node 7; this format fits the case of a left-right double rotation with 1 = 4, 2 = 6, 3 = 7, = ,
= , = , and = . After performing the double rotation, we obtain the tree on the
right, which maintains the AVL property.
14 (0)
6 (0) 28 (1)
4 (0) 7 (0) 30 (0)
Figure 66: Insert 30: 30 > 14, Move right. 30 > 28, Insert right. The AVL property is maintained for each
node in the tree, so no need to rebalance.
49
14 (1)
6 (0) 28 (2)
4 (0) 7 (0) 30 (1)
36 (0)
14 (0)
6 (0) 30 (0)
4 (0) 7 (0) 28 (0) 36 (0)
Figure 67: Insert 30: 30 > 14, Move right. 30 > 28, Insert right. The AVL property is violated for node
28; this format fits the case of a right-right single rotation with 1 = 28, 2 = 30, = , = ,
and = 36. After performing the single rotation, we obtain the tree on the right, which maintains the AVL
property.
14 (1)
6 (0) 30 (1)
4 (0) 7 (0) 28 (0) 36 (1)
33 (0)
Figure 68: Insert 33. 33 > 14, Move right. 33 > 30, Move right. 33 < 36, Insert left. The AVL property is
maintained for each node in the tree, so no need to rebalance.
50
14 (0)
6 (1) 30 (1)
4 (0) 7 (1) 28 (0) 36 (1)
33 (0)10 (0)
Figure 69: Insert 10. 10 < 14, Move left. 10 > 6, Move right. 10 > 7, Insert right. The AVL property is
maintained for each node in the tree, so no need to rebalance.
14 (0)
6 (1) 30 (1)
4 (0) 7 (1) 28 (0) 36 (0)
33 (0)10 (0) 40 (0)
Figure 70: Insert 40. 40 > 14, Move right. 40 > 30, Move right. 40 > 36, Insert right. The AVL property is
maintained for each node in the tree, so no need to rebalance.
7D
Has the final AVL tree decreased the total height () and the total depth ()? What are the new
values? What is the new value of () + ()?
The following table summarizes the height and depth information of each node using the definitions
described in 7A:
51
Node ℎ
14 3 0
6 2 1
30 2 1
4 0 2
7 1 2
28 0 2
36 1 2
10 0 3
33 0 3
40 0 3
Using the () and () equations above, we compute the new total height and new total depth as:
() = 9 () = 19. Using the AVL tree, we managed to decrease both the total height and total depth;
the sum is given as () + () = 27.
