Module 3
TRANSFORM-AND-CONQUER: Balanced Search Trees, Heaps and
Heapsort.
SPACE-TIME TRADEOFFS: Sorting by Counting: Comparison counting
sort, Input Enhancement in String Matching: Horspool’s Algorithm.
Transform and Conquer
• Transform and Conquer strategy is another important way to solve
various problems by transforming a given instance of a problem into
another instance of problem that is easier to solve.
Instance Simplification
Or
Problem’s
instance Representation Change Solution
Or
Problem Reduction
Fig : Transform and Conquer Strategy
Important Definitions
• Binary Tree : A binary tree is a tree in which outdegree of each node
is less than or equal to two i.e, each node in the tree can have 0, 1 or
2 children. An empty tree is also a binary tree.
Example: A
A A
B C B C B C
D E F G D D E
Complete Binary Tree : If the maximum level of a binary tree is i, and
the number of nodes at level i is equal to 2ⁱ, then the tree is said to be
complete binary tree.
Example: Level 0 ------------------------------ A ---------------------------------- Number of nodes at level 0 = 1 = 2⁰
Level 1 ------------------- B C --------------------Number of nodes at level 1= 2 = 2¹
Level 2 -------- D E F G ------ Number of nodes at level 2= 4 = 2²
Figure: Complete Binary Tree
Almost Complete Binary Tree
Heaps and Heapsort
• Definition of Heap: A heap is a complete binary tree or an almost
complete binary tree satisfying the parental dominance requirement
(i.e., each item in the tree should be greater than their children or each
item in the tree should be less than their children).
Thus, based on the parental dominance requirement, a heap can be
classified into two groups namely:
1. Ascending heap (min heap)
2. Descending heap (max heap)
Definition of Heap
Definition of Heap
Ascending heap (min heap): It is an almost complete binary tree such that an item
at any given node is less than or equal to the left child and right child. So, in an
ascending heap, the root node contains the least element and the elements in any
path from root to leaf will be in ascending order.
Example : 10
20 15
35 45 30 50
60
Figure : Ascending Heap (min heap)
Descending heap (max heap) : It is an almost complete binary tree such that an
item at any given node is greater than or equal to the left child and right child. So,
in a descending heap, the root node contains the highest element and the
elements in any path from root to a leaf will be in descending order.
Example : 100
100
75 80
70 80
25 50 45 30
25 50
Figure : Descending Heaps (max heap)
Array Representation of heap
Array Representation of a Heap: Store heaps elements in an array (whose elements
indexed, for convenience, 1 to n) in top-down left-to-right order
Example: 9
1 2 3 4 5 6
5 3
9 5 3 1 4 2
1 4 2
Figure : a heap Figure : Array representation of heap
Left child of node j is at 2ј
Right child of node j is at 2ј + 1
Parent of node j is at j/2
Parental nodes are represented in the first n/2 locations
Heap Construction
• A heap can be created using two techniques
1. Bottom – up heap construction
2. Top – down heap Construction
Bottom – up heap Construction
Example : Construct a heap for the list
2, 9, 7, 6, 5, 8 using Bottom-up construction
Solution:
2 2 2 2
9 7 9 7 9 8 9 8
6 5 8 6 5 8 6 5 7 6 5 7
2 2 9 9
9 8 9 8 2 8 2 8
6 5 7 6 5 7 6 5 7 6 5 7
9
6 8
2 5 7
is a Bottom-up heap construction for the given data.
Bottomup Heap Algorithm
Time Complexity (Bottom up heap)
• Each key on level i of the tree will travel to the leaf level h in the worst case
of the heap construction algorithm.
• Since moving to the next level down requires two comparisons— one to
find the larger child and the other to determine whether the exchange is
required.
• the total number of key comparisons involving a key on level i will be
• 2(h − i). Therefore, the total number of key comparisons in the worst case
will be:
Top – down heap Construction
Example : Construct a heap for the list 2, 9, 7, 6, 5, 8 using
Top-down construction
Solution:
Solution :
Step 1: Insert 2
2
Step 2: Insert 9
2 2 9
Not a
heap, so
9 heapify 9 2
It is an heap
Step 3: Insert 7
9
It is an heap
2 7
Step 4: Insert 6
9 9
9
Not a
2 2 7 6 7
7 heap, so
heapify
6 6 2
It is an heap
Step 5: Insert 5
9
6 7
It is an heap
2 5
Step 6: Insert 8
9 9 9
Not a
6 7 6 7 6 8
heap, so
heapify
2 5 8 2 5 8 2 5 7
It is an heap
Time Complexity(Top-down)
•Obviously ,insertion operation cannot require more key
comparisons than the heap’s height.
•Since the height of a heap with n nodes is
Time Complexity of insertion is in O(logn)
Heapsort
Step 1:Heap Construction
Step 2:Maximum Deletion
HeapSort
Heap sort example
Heap sort example
Heap sort example
Heap sort example
Heap sort example
Time Complexity
• Since we know that heap construction stage of algorithm is in O(n),we need
to find just the time efficiency of stage 2.
• Number of key comparisons ,C(n) is 2.
• first comparison to find largest child. second comparison to determine
whether parent should be exchanged with child node & it depends on
height of the tree i.e 2 log(n-1).
• Recreation of heap depends on height of the tree.
• So Time Complexity to swap and recreate the heap from n-1 down to 1 can
be obtained as shown:
• T.E to recreate the heap for (n-1) elements=2 log(n-1).
• T.E to recreate the heap for (n-2) elements=2 log(n-2).
• T.E to recreate the heap for (n-3) elements=2 log(n-3).
Time complexity
•Since we already know that the heap construction stage of
the algorithm is in O(n), we have to investigate just the time
efficiency of the second stage
•This means that ,C(n) ∈ O(n log n)for the second stage of
heapsort.
•For both stages, we get O(n) + O(n log n) =O( n log n).
Space and time trade-offs
•A tradeoff is a situation where one thing increases and another
thing decreases. It is a way to solve a problem in:
•Either in less time and by using more space, or
•In very little space by spending a long amount of time.
•Normally time factor is preferred over space in most of situations
Different Methods used
•Input enhancement: sorting by counting, Horse pools
algorithm.
•Prestructuring: Hashing, indexing with B-trees
•Dynamic programing: Knapsack problem, Floyds
algorithm ,Warshalls Algorithm
Sorting by counting
• As a first example of applying the input-enhancement technique, we
discuss its application to the sorting problem.
• One rather obvious idea is to count, for each element of a list to be
sorted, the total number of elements smaller than this
• element and record the results in a table. These numbers will indicate
the positions of the elements in the sorted list: e.g., if the count is 10 for
some element, it should be in the 11th position (with index 10, if we start
counting with 0) in the sorted array.
• Thus, we will be able to sort the list by simply copying its elements to
their appropriate positions in a new, sorted list. This algorithm is called
comparison counting sort.
Example:
Algorithm
Time Efficiency of the Algorithm
Distribution Counting
Distribution Counting
• Note that the distribution values indicate the proper positions for the last
occurrences of their elements in the final sorted array.
• If we index array positions from 0 to n − 1,the distribution values must be
reduced by 1 to get corresponding element positions.
• It is more convenient to process the input array right to left.
• For the example, the last element is 12, and, since its distribution value is 4,
we place this 12 in position 4 − 1 = 3 of the array S that will hold the sorted
list.
• Then we decrease the 12’s distribution value by 1 and proceed to the next
(from the right) element in the given array. The entire processing of this
example is depicted in Figure 7.2.
Distribution Counting
Algorithm
Horspools Algorithm
• Consider, as an example, searching for the pattern BARBER in some text:
• Starting with the last R of the pattern and moving right to left, we
compare the corresponding pairs of characters in the pattern and the
text. If all the pattern’s characters match successfully, a matching
substring is found. Then the search can be either stopped altogether or
continued if another occurrence of the same pattern is desired.
Horspools Algorithm
•If a mismatch occurs, we need to shift the pattern to the
right. Clearly, we would like to make as large a shift as
possible without risking the possibility of missing a
matching substring in the text. Horspool’s algorithm
determines the size of such a shift by looking at the
character c of the text that is aligned against the last
character of the pattern. This is the case even if character c
itself matches its counterpart in the pattern.
4 cases for shift:
• In general, the following four possibilities can occur.
• Case 1:If there are no c’s in the pattern—e.g., c is letter S in our
example— we can safely shift the pattern by its entire length.
4 cases for shift:
• Case 2: If there are occurrences of character c in the pattern but it is
not the last one there—e.g, c is letter B in our example—the shift
should align the rightmost occurrence of c in the pattern with the c in
the text:
4 cases for shift:
• Case 3: If c happens to be the last character in the pattern but there
are no c’s among its other m − 1 characters—e.g., c is letter R in our
example—the situation is similar to that of Case 1 and the pattern
should be shifted by the entire pattern’s length m:
4 cases for shift:
• Case 4: Finally, if c happens to be the last character in the pattern and
there are other c’s among its first m − 1 characters—e.g., c is letter R
in our example— the situation is similar to that of Case 2 and the
rightmost occurrence of c among the first m − 1 characters in the
pattern should be aligned with the text’s c:
Shift Table
•However, if such an algorithm had to check all the characters of the
pattern on every trial, it would lose much of this superiority.
•Fortunately, the idea of input enhancement makes repetitive
comparisons unnecessary.
•We can precompute shift sizes and store them in a table. The table
will be indexed by all possible characters that can be encountered in
a text, including, for natural language texts, the space, punctuation
symbols, and other special characters.
Shift table
• The table’s entries will indicate the shift sizes computed by the
formula:
Shift Table
Shift table
• For example, for the pattern BARBER, all the table’s entries will be equal to
6, except for the entries for E, B, R, and A, which will be 1, 2, 3, and 4,
respectively.
• Here is a simple algorithm for computing the shift table entries.
• Initialize all the entries to the pattern’s length m and scan the pattern left
to right repeating the following step m − 1 times: for the j th character of
the pattern (0 ≤ j ≤ m − 2), overwrite its entry in the table with m − 1 − j ,
which is the character’s distance to the last character of the pattern.
• Note that since the algorithm scans the pattern from left to right, the last
overwrite will happen for the character’s rightmost occurrence—exactly as
we would like it to be.
Shift Table
Horspool’s Algorithm
Horspool’s Algorithm
Horspool’s Algorithm
Algorithm
Balanced Search Tree
• It is a binary tree whose nodes contain elements of a set of orderable
items, one element per node, so that all elements in the left subtree
are smaller than the element in the subtree’s root, and all the
elements in the right subtree are greater than it.
• The first approach is of the instance-simplification variety: an
unbalanced binary search tree is transformed into a balanced one.
Because of this,
• such trees are called self-balancing. Specific implementations of this
idea differ by their definition of balance
AVL TREES
•An AVL tree is a binary search tree in which the balance factor of
every node, which is defined as the difference between the
heights of the node’s left and right subtrees, is either 0 or +1 or
−1. (The height of the empty tree is defined as −1.
•Of course, the balance factor can also be computed as the
difference between the numbers of levels rather than the height
difference of the node’s left and right subtrees.)
AVL TREES
ROTATIONS in AVL TREE
•If an insertion of a new node makes an AVL tree unbalanced,
we transform the tree by a rotation.
•A rotation in an AVL tree is a local transformation of its
subtree rooted at a node whose balance has become either
+2 or −2.
•If there are several such nodes, we rotate the tree rooted at
the unbalanced node that is the closest to the newly inserted
leaf.
•There are only four types of rotations; in fact, two of them
are mirror images of the other two.
4 types of rotation
•R-Rotation
•L-Rotation
•RL Rotation
•LR Rotation
Types of Rotation
Operation on AVL TREES
•Insertion of a node: The new node is inserted using the usual
binary search tree insert procedure i.e. comparing the key of the
new node with that in the root, and inserting new node into left
or right sub tree as appropriate.
•After insertion of new nodes two things can be changed i.e.
•Balanced factor
•height
AVL TREES
0
0
8
8
-1
1 -1 -1
5 1 0
0 5
0
0 1 0 0
7 0 1 0
5 7 9 5
Original AVL Tree
After inserting value 9
Neither the balance factor nor the height of the AVL tree is affected
AVL TREES
+1
0
8
8
-1
1 0 -1
5 1 -1
0 5
0
0
7 0 1 0
7
5
Original AVL Tree
After inserting value 15
Height remains unchanged but the balance factor of the root gets changed
AVL TREES
+2
+1
8
8 -1
0 1 0
1 0 5
5 0
0
0 +1
0 0 3 7
3 7
0
6
Original AVL Tree
After inserting value 6
Height as well as balanced factor gets changed. It needs rearranging about root
node
•In order to restore the balance property, we use the tree rotations
AVL TREES
-2
3 0
5 6
0
2 6 -1 0
Rotate left 0
0 0 3 6 -1
4 0 6 -1 5 5
5 5 2 0 4 0 7 0
0 5 0
7 0
0
Total height 4 Total height 3
Restoring balance by left rotation
AVL TREES
+2
3 0
5 3
+1
3 5 0 0
Rotate right +1
0 0 2 3 0
2 +1 3 0 5 5
5 3 1 0 3 0 5 0
0 3 0
1 0
0
Total height 4 Total height 3
Restoring balance by right rotation
AVL TREES
+2 +2
3 3
5 5
-1 +1
2 5 0 2 5 0
0 0 Rotate left 3 0
3 0
1 0 2 -1 2 +1 2
0 3 0
Total height 4 3 0 1 0
2 0
0 Rotate right
2
3
+1
2 3 0
0 5
1 0 3 0 5 0
0 2 0
Restoring balance by double rotation
AVL Tree Example:
• Insert 14, 17, 11, 7, 53, 4, 13 into an empty AVL tree
14
11 17
7 53
4
AVL Tree Example:
• Insert 14, 17, 11, 7, 53, 4, 13 into an empty AVL tree
14
7 17
4 11 53
13
AVL Tree Example:
• Now insert 12
14
7 17
4 11 53
13
12
AVL Tree Example:
• Now insert 12
14
7 17
4 11 53
12
13
AVL Tree Example:
• Now the AVL tree is balanced.
14
7 17
4 12 53
11 13
AVL Tree Example:
• Now insert 8
14
7 17
4 12 53
11 13
8
AVL Tree Example:
• Now insert 8
14
7 17
4 11 53
8 12
13
AVL Tree Example:
• Now the AVL tree is balanced.
14
11 17
7 12 53
4 8 13
In Class Exercises
• Build an AVL tree with the following values:
15, 20, 24, 10, 13, 7, 30, 36, 25
15, 20, 24, 10, 13, 7, 30, 36, 25
20
15
15 24
20
10
24
13
20 20
13 24 15 24
10 15 13
10
15, 20, 24, 10, 13, 7, 30, 36, 25
20
13
13 24 10 20
10 15 7 15 24
7 30
13 36
10 20
7 15 30
24 36
2-3 Trees
2 kinds of 2-3 tree
Problem 1:
2-3 Trees
Problem 2:
Note: For more problems on AVL Tree refer
Notes