Com S 311 Section B Introduction to the Design and Analysis of Algorithms
Lecture One for Week 4
Xiaoqiu (See-ow-chew) Huang
Iowa State University
February 16, 2021
Binary Trees
A binary tree is either empty or consists of a root tree, a left binary tree, and a right binary tree.
Each node has at most two children. A leaf node has no children.
The root node has no parent, where every other node has one parent.
Example
to left child
/ \ to right child
\
4 (root) A binary tree /\
/ 72
/\\ /\\ 136
/ \ (leaf) / /\/
895 (leaf) (leaf) (leaf)
Each parent is above its children.
Binary Trees
An edge refers to the link from the parent to the child.
A path is a sequence of nodes with each pair of adjacent nodes connected by an edge.
The length of a path is the number of edges in the path.
The height of a node is the length of the path from the node to its furthest leaf.
The height of a tree is the height of its root.
Full Binary Trees
The depth of a node, also referred to as the level of a node, is the length of the path from the root to the node.
A full binary tree is a binary tree in which every leaf node has the same depth and every non-leaf node (internal node) has exactly two children.
A full binary tree of depth d has a total of 2d+1 − 1 nodes.
4 A full binary tree /\
/\ /\
72 /\ /\
/\/\ 9653
/\ /\ /\ /\ /\/\/\/\ 1 10 8 11121413 15
The tree of depth 3 has a total of
2^{3+1} – 1 = 15 nodes.
Inductive Proof
In a tree of depth 0, the number of nodes is 20+1 − 1 = 1.
In a tree of depth 1, the number of nodes is 21+1 − 1 = 4 − 1 = 3.
In a tree of depth 2, the number of nodes is 22+1 − 1 = 8 − 1 = 7.
Assume that a full binary tree of depth d − 1 has 2d −1+1 − 1 nodes.
A full binary tree of depth d consists of a root node, a left full binary tree of depth d − 1, a right full binary tree of depth d − 1.
Then the total number of nodes in the full binary tree of depth d is 2d−1+1 −1+2d−1+1 −1+1 = 2d +2d −1 = 2d+1 −1.
Complete Binary Trees
A binary tree is complete if it is full through the next-to-lowest level and all of the leaves at the lowest level are as far to the left as possible.
4 A complete binary tree /\
/\ /\
72 /\ /\
/\/\ 9653
/\ /\ / /\/\/
1 108 1714
4 An incomplete binary tree
/\ /\ /\
72 \/
\/ 65
Complete Binary Trees
It is possible to store a complete binary tree in an array.
A complete binary tree is stored in an array A[1..A.length] such that array indexes are used to find the children of a node.
The root of the tree is at index 1. For a node at index i, we can easily obtain the indices of its parent, left child, and right child: PARENT(i)
1. return ⌊i/2⌋
LEFT(i )
1. return 2 ∗ i
RIGHT(i )
1. return 2∗i +1
Example
4 A complete binary tree /\
/\ /\
72 /\ /\
/\/\ 9653
/\ /\ / /\/\/
1 108 1714
ArrayContents 47296531108 1714 ArrayIndex 12345678 9101112
Node Left child
Label 4 7
Index 1 2*1 = 2
Right child Parent
2 None
2*1+1 = 3
Label9 1 10 7 Index 4 2*4 = 8 2*4+1 = 9 4/2 = 2
Heaps
Heaps are used in a sorting algorithm and a priority queue data structure.
A heap is a complete binary tree stored in an array A[1..A. heap-size], where 0 ≤ A. leap-size ≤ A.length.
1. In a max heap, for every node i other than the root, A[PARENT(i)] ≥ A[i],
that is, the element of a node is less than or equal to the element of its parent. Thus, the root element is a largest element.
2. A min heap is the opposite: for every node i other than the root, A[PARENT(i)] ≤ A[i].
Thus, the root element is a smallest element.
Example of a Max Heap of Size 10
On any path from the root to a leaf, the
elements are in non-increasing order.
Array: 50 45 35 40 25 20 30 15 10 5
Index: 1 2 3 4 5 6 7 8 9 10
50 A max heap /\
/\ /\ 45 35
/\ /\ /\/\ 40 25 20 30
/\/ /\/
15 10 5
Height of a Heap of size n
We show that an n-element heap has height ⌊lg n⌋.
The maximum number of nodes in a complete tree of height h is 2h+1 − 1.
The maximum number of nodes in a complete tree of height h − 1 is
2h − 1.
The minimum number of nodes in a complete tree of height h is 2h −1+1.
For an n-element heap of height h, we have 2h ≤n<2h+1.
h ≤ lg n < h + 1.
Note that h is an integer. So h = ⌊lg n⌋.
Determine the number of leaves in a 9-element heap.
For n = 9, the node with value 25 at index 5
(= 1 + floor(9/2)) is the first leaf node in the array;
it has no child, LEFT(5) = 2 * 5 = 10 > 9 = n.
50 A max heap /\
/\ /\ 45 35
/\ /\ /\/\ 40 25 20 30
/\ /\ 15 10
The Number of leaves in a Heap of size n
The number of non-leaf nodes in an n-element heap is ⌊n/2⌋, and the number of leaf nodes is ⌈n/2⌉, at indices
⌊n/2⌋ + 1, ⌊n/2⌋ + 2, …, n.
Consider the index of the first leaf node, i.e. ⌊n/2⌋ + 1. For this node, we check on the index of its left child:
LEFT(⌊n/2⌋ + 1) = 2(⌊n/2⌋ + 1)
> 2((n/2 − 1) + 1) = 2(n/2) = n.
That is, LEFT(⌊n/2⌋ + 1) is greater than the size of the heap. Thus node at index ⌊n/2⌋ + 1 is a leaf, and so are nodes after this index.
50 A max heap of size 17 /\
/\ /\ 45 35
/\ /\ /\/\
40 25 20 30 /\ /\ /\/\ /\/\/\/\ 15105 2015 55 10
/\ /\ 10 5
No. of nodes of height 0 (leaf nodes): ceiling(17/2) = 9
No. of nodes of height >= 1: floor(17/2) = 8
No. of nodes of height 1: ceiling(8/2) = 4
No. of nodes of height >= 2: floor(8/2) = 4
Obtained by removing all leaf nodes in the previous tree.
50 A max heap of size 8 /\
/\ /\ 45 35
/\ /\ /\/\ 40 25 20 30
/ /
15
No. of nodes of height 0 (leaf nodes): ceiling(8/2) = 4
No. of nodes of height >= 1: floor(8/2) = 4
No. of nodes of height 1: ceiling(4/2) = 2
No. of nodes of height >= 2: floor(4/2) = 2
Obtained by removing all leaf nodes in the previous tree.
/ /
40
50 /\ /\ /\
45
A max heap of size 4
35
No. of nodes of height 0 (leaf nodes): ceiling(4/2) = 2
No. of nodes of height >= 1: floor(4/2) = 2
No. of nodes of height 1: ceiling(2/2) = 1
No. of nodes of height >= 2: floor(2/2) = 1
Obtained by removing all leaf nodes in the previous tree.
50 A max heap of size 2
/
/ /
45
No. of nodes of height 0 (leaf nodes): ceiling(2/2) = 1
No. of nodes of height >= 1: floor(2/2) = 1
No. of nodes of height 1: ceiling(1/2) = 1
No. of nodes of height >= 2: floor(1/2) = 0
Number of Nodes of any Height h in a Heap of Size n By using the above observation repeatedly, we justify that a heap
of size n > 0 has at most n/2h+1 nodes of any height h. Consider h = 0. The number of nodes of height 0 is the number of
leaf nodes, which is ⌈n/2⌉ = n/20+1.
The number of nodes of height ≥ 1 is ⌊n/2⌋.
The number of nodes of height 1 is ⌈⌊n/2⌋/2⌉ ≤ n/21+1. The number of nodes of height ≥ 2 is ⌊⌊n/2⌋/2⌋ = n/22. In general, the number of nodes of height ≥ h is n/2h, and the number of nodes of height h is n/2h/2 ≤ n/2h+1.