Chapter 7

Data Structures
Chapter 07
8/28/2024 1
Data Structures- Chapter 7
❑ Binary Tree
– A tree is a nonlinear data structure used to represent data containing a
hierarchical relationship between elements.
– A tree in which each element may has 0-child , 1-child or maximum of
2-children.
– A Binary Tree T is defined as finite set of elements, called nodes, such
that:
a) T is empty (called the null tree or empty tree.)
b) T contains a distinguished node R, called the root of T, and the
remaining nodes of T form an ordered pair of disjoint binary trees T1
and T2.
8/28/2024 2
❑ Binary Tree
– If T does contain a root R, then the two trees T1 and T2 are called,
respectively, the left sub tree and right sub tree of R.
– If T1 is non empty, then its node is called the left successor of R;
similarly, if T2 is non empty, then its node is called the right successor
of R. The nodes with no successors are called the terminal nodes.
– The line drawn from a node N of T to a successor is called an edge, and
a sequence of consecutive edges is called a path. A terminal node is
called a leaves, and a path ending in a leaves is called a branch.
– The depth (or height) of a tree T is the maximum number of nodes in a
branch of T. This turns out to be 1 more than the largest level number
of T.
8/28/2024 3
❑ Binary Tree
8/28/2024 4
❑ Level of node & its generation
Each node in binary tree T is assigned a level number, as follows.
– The root R of the tree T is assigned the level number 0, and
– Every other node is assigned a level number which is 1 more than the
level number of its parent. Furthermore, those nodes with the same
level number are said to belong to the same generation.
8/28/2024 5
❑ Complete Binary Tree
– Consider a binary tree T. Each node of T can have at most two children.
– A tree is said to be complete if all its levels, except possibly the last,
have the maximum number of possible nodes, and if all the nodes at the
last level appear as far left as possible.
1
2 3
4 5 6 7
8 9 10 11 12 13 14 15
16 17 18 19 20 21 22 23 24 25 26
8/28/2024 Muhammad Imran Ali, Senior Lecturer, CSE, CBST 6

❑ Extended Binary Tree: 2-Tree
– A binary tree T is said to be a 2-tree or an extended binary tree if each
node N has either 0 or 2 children.
– In such a case, the nodes, with 2 children are called internal nodes, and
the node with 0 children are called external node.
8/28/2024 7
❑ General Tree
– A tree where a node can have any number of children / descendants is
called General Tree.
– A general tree (sometimes called a tree) is defined to be a nonempty
finite set T of elements, called nodes, such that:
1) T contains a distinguished element R, called the root of T

2) The remaining elements of T form an ordered collection of zero or
more disjoint trees: T1, T2, . . . . Tm.
– The trees T1, T2, . . . . Tm are called subtrees of the root R.
8/28/2024 8
❑ General Tree
A
B C D
E F G H J K
L M N
– The children are ordered from left to right.

– The root A has 3 children: B, C, and D.
– The node C has 3 children.
– Each of the nodes B and K has 2 children.
– Each of the nodes D and H has only 1 child.
– The nodes E, F, G, L, J, M, and N have no children.
8/28/2024 9
❑ Binary tree vs. General Tree
– A binary tree T/ is not a special case of a general tree T. Binary trees
and general trees are different objects. Two basic differences follows:
1) A binary tree T/ may be empty, but a general tree T is nonempty.
2) Suppose a node has only one child. Then the child is distinguished as a left
child or right child in a binary tree T/, but no such distinction exists in a
general tree T.
A A
– As binary trees, T1 and T2 are different,
since inT1, B is the left child of A, B B
but in T2, B is the right child of A
– As general trees, there is no difference C D C D
between T1 and T2. T1 T2
8/28/2024 10
❑ Forest
– A forest F is defined to be an ordered collection of zero or more

distinct trees.
– Clearly, if we delete the root R from a general tree T, then we obtain
the forest F consisting of the subtrees of R.
– Conversely, if F is a forest, then we may adjoin a node R to F to
form a general tree T where R is the root of T and the subtrees of R
consist of the original trees in F.
8/28/2024 11
❑ Representing Binary Trees in Memory
Let T be a binary tree. The first and usual way of representing binary
tree T in memory is called the link representation. The second way,
which uses a single array, called the sequential representation of T.
Linked Representation of Binary Trees:

Consider a binary tree T. T will be maintained in memory by means of a
linked representation which uses three parallel arrays, INFO, LEFT and
RIGHT, and a pointer variable ROOT as follows. First of all, each node
N of T will correspond to a location K such that:
(1) INFO [K] contains the data at the node N.
(2) LEFT [K] contains the location of the left child of node N.
(3) RIGHT [K] contains the location of the right child of node N.
8/28/2024 12
❑ Linked Representation of Binary Trees
– Furthermore, ROOT will contain the location of the root R of T.

– If any subtree is empty, then the corresponding pointer will contain
the null value.
– if the tree T itself is empty, then ROOT will contain the null value.
8/28/2024 13
❑ Linked Representation of Binary Trees
8/28/2024 14
❑ Sequential Representation of Binary Trees
Suppose T is binary tree that is complete or nearly complete. Then there
is an efficient way of maintaining T in memory called the sequential
representation of T. This representation uses only a single linear array
TREE as follows:
(a) The root R of T is sorted in TREE [1].

(b) If a node N occupies TREE [K], then its left child is stored in
TREE [2*K] and its right child is stored in TREE [2*K+1].
8/28/2024 15
❑ Sequential Representation of
Binary Trees
– The sequential representation
of the binary tee T in Fig. (a)
appears in Fig. (b).
– T requires 14 locations in the
array TREE even though T has
only 9 nodes.
– Accordingly, this sequential
representations is usually
inefficient unless, the binary
tree T is complete or nearly
complete.
8/28/2024 16
❑ Sequential Representation of Binary Trees
Advantages of linear representation:

1. Simplicity.
2. Given the location of the child (say, k), the location of the parent is
easy to determine (k / 2).
Disadvantages of linear representation:

1. Additions and deletions of nodes are inefficient, because of the data
movements in the array.
2. Space is wasted if the binary tree is not complete. That is, the linear
representation is useful if the number of missing nodes is small.
8/28/2024 17
❑ Traversing Binary Trees
There are three standard ways of traversing a binary tree T with root R.
These three algorithms, called preorder, inorder and postorder, are as
follows:
Preorder (Node-Left-Right NLR traversal):

(1) Process the root R.
A
(2) Traverse the left subtree of R in preorder.
(3) Traverse the right subtree of R in preorder. B C
Preorder traversal of the tree: D E F

A–B–D –E –C–F
8/28/2024 18
Inorder (Left-Node-Right LNR traversal):

(1) Traverse the left subtree of R in inorder.
(3) Traverse the right subtree of R in inorder.
Inorder traversal of the tree: A

D–B –E–A–C –F
B C
D E F
8/28/2024 19
Postorder (Left-Right-Node LRN traversal):

(1) Traverse the left subtree of R in postorder.
(2) Traverse the right subtree of R in postorder.
Postorder traversal of the tree:

A
D–E–B–F–C–A
B C
D E F
8/28/2024 20
❑ Example 7.7: Represent the following algebraic expression by means of a
binary tree:
[ a+ ( b - c ) ] * [ (d - e) / ( f + g – h ) ]
Find the preorder and postorder traversal of the tree.
Preorder traversal:
*+a-bc/-de-+fgh
Postorder traversal:
abc-+de-fg+h-/*
8/28/2024 21
❑ Binary Search Trees (BST)
Binary Search tree is a binary tree T in which each node N has the
following property:
The value at N is greater than every value in the left sub tree of N and
is less than or equal to every value in the right sub tree of N.
BST: This structure enables one to search for and find an element with an
average running time f(n) = O(log2n). It also enables one to easily insert
and delete elements.
Sorted Linear Array: Here one can search for and find an element with a
running time f(n)=O(log2n), but it is expensive to insert and delete
elements.
Linked List: Here one can easily insert and delete elements, but it is
expensive to search for and find an element, since one must use a linear
search with running time f(n) = O(n).
8/28/2024 22
❑ Example 7.15: Construct a binary search tree for the following numbers:
40, 60, 50, 33, 55, 11
8/28/2024 23
❑ Heap
Suppose H is a complete binary tree with n elements. Then H is called a
heap, or a maxheap, if each node N of H has the following property:
“The value at N is greater than or equal to the value at each of the
children of N.”
Accordingly, the value at N is greater than or equal to the value at any of
the descendants of N.
88
72 55
70 44 30 50
50 66 22 33 25
8/28/2024 24
❑ MinHeap
Suppose H is a complete binary tree with n elements. Then H is called a
minheap, if each node N of H has the following property:
“The value at N is less than or equal to the value at any of the children
of N.”
2
4 3
6 7 9 3
8 6
8/28/2024 25
❑ Heap
Heaps are used
1. to implement priority queues,
2. to implement the Heap sort algorithm.
❑ Insertion into a Heap

Suppose H is a heap with N elements, and suppose an ITEM of
information is given. We insert ITEM into the heap H as follows:
1. First adjoin ITEM at the end of H so that H is still a complete binary

tree, but not necessarily a heap.
2. Then let ITEM rise to its “appropriate place” in H so that H is finally
a heap.
8/28/2024 26
❑ Example 7.34: Construct a heap tree for the following numbers:
44, 30, 50, 22, 60, 55, 77, 55.
Solution:
Insert the numbers one after the other into an empty heap H.
44 44
ITEM = 44 30
ITEM = 30
8/28/2024 27
44, 30, 50, 22, 60, 55, 77, 55.
Solution:
44 50
30 50 30 44
ITEM = 50
8/28/2024 28
44, 30, 50, 22, 60, 55, 77, 55.
Solution:
50 50 50 60
30 44 30 44 60 44 50 44
22 22 60 22 30 22 30
ITEM = 22 ITEM = 60
8/28/2024 29
44, 30, 50, 22, 60, 55, 77, 55.
Solution:
60 60 60
50 44 50 55 50 55
22 30 55 22 30 44 22 30 44
ITEM = 55
8/28/2024 30
44, 30, 50, 22, 60, 55, 77, 55.
Solution:
60 60 77
50 55 50 77 50 60
22 30 44 77 22 30 44 55 22 30 44 55
ITEM = 77
8/28/2024 31
44, 30, 50, 22, 60, 55, 77, 55.
Solution:
77 77 77
50 60 50 60 55 60
22 30 44 55 55 30 44 55 50 30 44 55
55 22 22
ITEM = 55 Maxheap
8/28/2024 32
❑ Deleting the Root of a Heap
Suppose H is a heap with N elements, and suppose we want to delete the
root R of H. This is accomplished as follows:
1. Assign the root R to some variable ITEM.

2. Replace the deleted node R by the last node L of H so that H is still a
complete binary tree, but not necessarily a heap.
3. (Reheap) Let L sink to its “appropriate place” in H so that H is finally
a heap.
8/28/2024 33
Delete the root of the following heap:
77
55 60
50 30 44 55
22
22
Solution:
ITEM= 77 (Root of the Heap) 55 60
Replace the root by the last node 22
50 30 44 55
8/28/2024 34
Solution:
Now find the appropriate place of L in H.
22 60
55 60 55 22
50 30 44 55 50 30 44 55
60
55 55
50 30 44 22
8/28/2024 35
❑ Applications of Heaps
– Sort (heap sort)

– Machine scheduling
– Huffman codes
8/28/2024 36
❑ HeapSort
Suppose an array A with N elements is given. The heapsort algorithm to

sort A consists of the two following phases:
Phase A: Build a heap H out of the elements of A

Phase B: Repeatedly delete the root element of H.
Since the root of H always contains the largest node in H, Phase B deletes
the elements of A in decreasing order.
8/28/2024 37
❑ Algorithm 7.11: HEAPSORT(A, N)
An array A with N elements is given. This algorithm sorts the elements of A.

1. Repeat for J = 1 to N-1
Call INSHEAP (A, J, A[J+1])
[End of loop]
2. Repeat while N > 1
a) Call DELHEAP (A, N, ITEM)
b) Set A[N+1] = ITEM
[End of loop]
3. Exit
8/28/2024 38
❑ Complexity of HeapSort
HeapSort:
Worst case complexity of the heapsort algorithm:
f(n) = O(nlog2n)
Bubble Sort:
Complexity of the Bubble sort algorithm:
f(n) = O(n2)
Quick Sort:
Complexity of the Quick sort algorithm:
Average case: f(n) = O(nlog2n)
Worst case : f(n) = O(n2)
8/28/2024 39
❑ Path Lengths; Huffman’s Algorithm
– An extended binary tree or 2-tree is a binary tree T in which each node
has either 0 or 2 children.
– The nodes with 0 children are called external nodes.
– The nodes with 2 children are called internal nodes.
– The fig. shows a 2-tree where

the internal nodes are denoted by
circles and the external nodes are
denoted by squares.
8/28/2024 40
– For any 2-tree,
NE = No. of external nodes and
NI = No. of internal nodes
Then,
NE = NI + 1
For this 2-tree:

NI = 6
NE = 7
That is,
NE = NI + 1
8/28/2024 41
– An algorithm can be represented by a 2-tree T where the internal nodes
represent tests and the external nodes represent actions.
– Accordingly, the running time of the algorithm may depend on the
lengths of the paths in the tree.
External Path Length, LE:

– The sum of all path lengths summed over each path from the root R of
T to an external node.
LE = 2+2+3+4+4+3+3=21
8/28/2024 42
Internal Path Length, LI:

– The sum of all path lengths summed over each path from the root R of
T to an internal node.
LI = 0+1+1+2+3+2=9
Clearly,
LE = LI + 2n
Where n = No. of internal nodes
8/28/2024 43
Weighted Path Length, P:

– Suppose T is a 2-tree with n external nodes and suppose each of the
external node is assigned a (nonnegative) weight. The weighted path
length P of the tree T is defined to be the sum of the weighted path
lengths:
P = W1L1 + W2L2 + . . . + WnLn
Where Wi and Li denote,

respectively, the weight and
path length of an external
node Ni.
8/28/2024 44
❑ Example 7.36:
– Three 2-trees, each having external nodes with weights 2, 3, 5, and 11.
T1 T2 T3
2 11
2 3 5 11 11 5
3 5 2 3
– Weighted Path lengths of T1, T2, and T3:

P1 = 2.2 + 3.2 + 5.2 + 11.2 = 42
P2 = 11.2 + 3.3 + 5.3 + 2.1 = 48
P3 = 5.2 + 2.3 + 3.3 + 11.1 = 36
8/28/2024 45
❑ Example 7.36:
– Three 2-trees, each having external nodes with weights 2, 3, 5, and 11.
– Weighted Path lengths of T1, T2, and T3:
P1 = 2.2 + 3.2 + 5.2 + 11.2 = 42
P2 = 11.2 + 3.3 + 5.3 + 2.1 = 48
P3 = 5.2 + 2.3 + 3.3 + 11.1 = 36
– Different 2-trees, each having external nodes with weights 2, 3, 5, and 11

have different weighted path lengths.
– Now question is which tree will give a minimal weighted path length, P?
– Huffman tree is the solution.
8/28/2024 46
❑ Huffman Tree
– Huffman tree is a binary tree with minimum weighted external path

length for a given set of frequencies (weights).
– A Huffman tree is a binary tree of integers with two properties:

1. Each internal node is the sum of its children.
2. Its weighted external path length is minimal.
8/28/2024 47
❑ Huffman’s Algorithm
Suppose w1 and w2 are two minimum weights among the n given weights
w1, w2,…., wn. Find a tree T/ which gives a solution for the n-1 weights
w1 + w2, w3, w4,….., wn
Then, in the tree T/, replace the external node w1 + w2
by the subtree
w1 w2
The new 2-tree T is the desired solution.
8/28/2024 48
❑ Example 7.37: A, B, C, D, E, F, G and H are 8 data items and they are
assigned weights as follows:
Data item : A B C D E F G H
Weight : 22 5 11 19 2 11 25 5
Construct a Huffman tree using the above data and Huffman’s algorithm.
Solution: 22 5 11 19 2 11 25 5
(a) A B C D E F G H
22 11 7 19 11 25 5
(b) A C D F G H
2 5
E B
8/28/2024 49
❑ Example 7.37:
Solution: 22 11 19 11 25
(c) A C D 12 F G
5 7
H
2 5
E B
22 19 25
(d) A D 12 22 G
5 7 11 11
H F C
2 5
E B
8/28/2024 50
❑ Example 7.37:
Solution:
(e) 22 31 22 25
A G
12 19 11 11
D F C
5 7
H
2 5
E B
8/28/2024 51
❑ Example 7.37:
Solution:
(f) 31 44 25
G
12 19 22 22
D A
5 7 11 11
H F C
2 5
E B
8/28/2024 52
❑ Example 7.37:
Solution:
(g) 56 44
25 22 22
31
G A
19 11 11
12
D F C
5 7
H
2 5
E B
8/28/2024 53
❑ Example 7.37:
Solution: 100
(h)
44 56
22 22 25 31
A G
11 11 19
12
F C D
5 7
Building a Huffman tree H
Weighted Path Length:
2 5
P = 22.2+11.3+11.3+25.2+5.4+2.5+5.5+19.3 E B
= 272
8/28/2024 54
❑ Computer Implementation of Huffman’s Algorithm
8/28/2024 55
❑ Application to Coding
8/28/2024 56
❑ Huffman Codes
– Huffman code is a technique for compressing data.

– Huffman codes is a text compression method, which relies on the
relative frequency (i.e., the number of occurrences of a symbol) with
which different symbols appear in a text
– Uses extended binary trees
– Huffman tree is a binary tree with minimum weighted external path
length for a given set of frequencies (weights)
8/28/2024 57
❑ Huffman Coding
8/28/2024 58
❑ Huffman Coding
Initial sequence
Sorted by frequency
Combine lowest two

into sub-tree
Move it to correct
place
8/28/2024 59
❑ Huffman Coding
After shifting sub-tree

to its correct place ...
Combine next lowest

pair
Move sub-tree to
correct place
8/28/2024 60
❑ Huffman Coding
Move the new tree

to the correct place ...
Now the lowest two are the

“14” sub-tree and D
Combine and move to

correct place
8/28/2024 61
❑ Huffman Coding
Move the new tree

to the correct place ...
Now the lowest two are the

the “25” and “30” trees
Combine and move to

correct place
8/28/2024 62
❑ Huffman Coding
Combine
last two trees
8/28/2024 63
❑ Huffman Coding
Encoding: Concatenate the codewords representing each characters of the
file.
String Encoding:
TEA 10 00 010
SEA 011 00 010
TEN 10 00 110
8/28/2024 64

Chapter 7

Uploaded by

Copyright:

Available Formats

Chapter 7

Uploaded by

Document Information

Original Title

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

Chapter 7

Uploaded by

Copyright:

Available Formats

Data Structures

8/28/2024 Muhammad Imran Ali, Senior Lecturer, CSE, CBST 6

1) T contains a distinguished element R, called the root of T

– The trees T1, T2, . . . . Tm are called subtrees of the root R.

– The children are ordered from left to right.

– A forest F is defined to be an ordered collection of zero or more

Linked Representation of Binary Trees:

– Furthermore, ROOT will contain the location of the root R of T.

(a) The root R of T is sorted in TREE [1].

Advantages of linear representation:

Disadvantages of linear representation:

Preorder (Node-Left-Right NLR traversal):

Preorder traversal of the tree: D E F

Inorder (Left-Node-Right LNR traversal):

Inorder traversal of the tree: A

Postorder (Left-Right-Node LRN traversal):

Postorder traversal of the tree:

❑ Insertion into a Heap

1. First adjoin ITEM at the end of H so that H is still a complete binary

1. Assign the root R to some variable ITEM.

– Sort (heap sort)

Suppose an array A with N elements is given. The heapsort algorithm to

Phase A: Build a heap H out of the elements of A

An array A with N elements is given. This algorithm sorts the elements of A.

– The fig. shows a 2-tree where

For this 2-tree:

External Path Length, LE:

Internal Path Length, LI:

Where n = No. of internal nodes

Weighted Path Length, P:

Where Wi and Li denote,

– Weighted Path lengths of T1, T2, and T3:

– Different 2-trees, each having external nodes with weights 2, 3, 5, and 11

– Huffman tree is the solution.

– Huffman tree is a binary tree with minimum weighted external path

– A Huffman tree is a binary tree of integers with two properties:

The new 2-tree T is the desired solution.

– Huffman code is a technique for compressing data.

Combine lowest two

After shifting sub-tree

Combine next lowest

Move the new tree

Now the lowest two are the

Combine and move to

Move the new tree

Now the lowest two are the

Combine and move to

You might also like