ADVANCED DATA STRUCTURES & ALGORITHM

ANALYSIS
Objectives:

 Understand the fundamentals of algorithm analysis, including space and time

complexity analysis and asymptotic notations.
 Learn to create AVL Trees,B-Trees and perform insertion and deletion operations.
 Explore the applications of AVL Trees and B-Trees in solving real-world problems
efficiently.

Modules:

1. Introduction: Algorithm Analysis

2. Space and Time complexity analysis
3. Asymptotic notations
4. AVL Trees – creation, insertion, deletion operations and applications
5. B- Trees – creation, insertion, deletion operations and applications

Outcomes :

After completion of the unit, students will be able to

 Analyze algorithms in terms of space and time complexity using asymptotic notations.
 Create AVL Trees and perform insertion and deletion operations on them.
 Apply AVL Trees to solve practical, real-world problems efficiently.

MODULE 1: Introduction: Algorithm Analysis:

Algorithm Definition:

 An Algorithm is a finite set of instructions that if followed, accomplishes a

particular task.
Characteristics of an algorithm:

 Input: An algorithm has zero or more but only finite number of inputs.

 Output: At least one quantity must be produced as output.

 Definiteness: Each instruction must be clear and ambiguous. It must be clear what
should be done.
  For example consider the instruction: add 6 or 7 to x. It is not clear about
which one of the two possibilities should be done.
 Finiteness: If we trace out the instructions of an algorithm, then for all cases, the
algorithm terminates after a finite number of steps.

 An algorithm must terminate after a finite number of operations, but the time for
termination should be reasonably short.

 For example, an algorithm could be devised that decides whether any given
position in a game of chess is a winning position. An algorithm works by
examining all possible positions and counter moves, but this takes billions
of years to make a decision, even with more modern computers. So we say
that algorithm is not finite.
 Effectiveness: Every instruction must be very basic so that it can be carried out by
a person using only pencil and paper.

 Each operation must be feasible and effective and can be done in a finite
amount of time.
 For example, performing integer arithmetic is effective but performing real
arithmetic is not effective as it involves long decimal expansions.

Example 1: Algorithm that finds and returns the maximum of n given numbers:

Algorithm Max (A, n)

// A is an array of size n.
{
Result :=A[l];
for i :=2 to n do
if A[i] >Result
then
Result:=A[i];
return Result;
}

In this algorithm is named Max, A and n are procedure parameters. Result

and i are local variables.
  Example 2: Recursive algorithm for Towers of Hanoi problem
Algorithm TowersOfHanoi(n, x, y, z)
//Move the top n disks from tower x to tower y.
{
if (n >= 1) then
{
TowersOfHanoi((n-1), x, z, y)
write(“move top disk from tower”, x, “to top of tower”, y);
TowersOfHanoi((n-1), z, y, x)
}
}

MODULE 2 : Space and Time complexity analysis:

Performance Analysis
 There are two criteria for judging the performance of an algorithm:

 Computing time

 Storage Requirements

 Performance evaluation can be loosely divided into two major phases:

(1) Priori estimates referred to as performance analysis

(2) Posteriori testing referred to as performance measurement.

 The space complexity of an algorithm is the amount of memory it needs to

run to completion.
 The time complexity of an algorithm is the amount of computer time it needs to
run to completion.

Space Complexity

 The space needed by the algorithm is the sum of the following components:

 A fixed part that is independent of the characteristics (e.g., number, size)

of the inputs and outputs.
 This part typically includes the instruction space (i.e., space for the code),
space for simple variables and fixed-size component variables (also called
 aggregate), space for constants, and soon.
 A variable part that consists of the space needed by component variables
whose size is dependent on the particular problem instance being solved,
the space needed by referenced variables (to the extent that this depends on
instance characteristics), and the recursion stack space (insofar as this
space depends on the instance characteristics)
 The space requirement S(P) of any algorithm P may be written as :

S (P) = c + Sp (instance characteristics), where c is a constant.

When analyzing the space complexity of an algorithm, we concentrate on estimating

Sp(instance characteristics).
For any given problem, we need first to determine which instance characteristics
to use to measure the space requirements.
 Example 1:

Algorithm abc computes a+ b+b*c+(a+ b -c)/(a+6)+4.0;

Algorithm abc (a,b,c)

return a + b + b * c+ (a + b - c)/(a+ b) + 4.0;

• The problem instance is characterized by the specific values of a, b, and c.

• Making the assumption that one word is adequate to store the values of
each of a, b, c, and the result, we see that the space needed by abc is
independent of the instance characteristics.

• Sp (instance characteristics) = 0.

 Example 2:

Algorithm Sum compute sum of a [1] to a[n] iteratively, where the a[i]'s are real
numbers
Algorithm Sum (a,n)
{
s :=0.0;
 for i :=to n do
s :=s+ a[i];
returns;

• The problem instances for are characterized by n, the number of elements to be

summed.

• The space needed by n is one word, since it is of type integer.

• The space needed by a is the space needed by variables of type array of

floating point numbers.

• This is at least n words, since a must be large enough to hold the n

elements to be summed.

• So, Ssum(n) ≥ (n +3) (n for a[ ]one each for n, i and s).

Time Complexity

 The time T(p) taken by a program P is the sum of the compile time and the run
time(execution time)
 The compile time does not depend on the instance characteristics. Also we may assume
that a compiled program will be run several times without recompilation .This rum time is
denoted by tp (instance characteristics).
 The number of steps any problem statement is assigned depends on the kind of statement.
For example,
comments 0 steps.
An assignment statement is 1 step.

[This does not involve any calls to other algorithms]

Interactive statement such as for, while & repeat-until Control part of the statement.

 We can determine the number of steps needed by a program to solve a particular

problem by using one of the two methods as follows:
Method1: Count Method

 We introduce a new variable, count, into the program. This is a global

variable with initial value 0. Statements to increment count by the
appropriate amount are introduced into the program. This is done so that
each time a statement in the original program is executed; count is
 incremented by the step count of that statement.
 Example1: By including a global variable Count (Iterative Algorithm)

Algorithm sum(a,n)
{ s=0.
0;
count=count+1;
for i= 1 to n do
{
count=count+1;
s = s + a[i];
count=count+1;
}
count=count+1;
count=count+1;
return s;
}

 For the for loop, the value of count will increase by a total of 2n.

• If count is zero to start with, then it will be 2n + 3 on termination.

• So each invocation of Sum executes a total of 2n + 3 steps.

Example 2: (Recursive Algorithm)

Algorithm RSum(a,n)

Count:=count+1; // For the if conditional

if (n<= 0) then

count:=count+1; // For the return

return 0.0;

else
 count:=count+1; // For the addition, function invocation and return

return RSum (a, n-1) + a[n];

• When analyzing a recursive program for its step count, we often obtain a
recursive formula for the step count.

• Let tRSum(n) be the increase in the value of count when the Algorithm
terminates.

• We see that tRSum(0) = 2. When n >0, count increases by 2 .

tR Sum(n) = 2 if n = 0
2 + tR Sum(n-1) if n > 0

• These recursive formulas are referred to as recurrence relations.

• One way of solving any such recurrence relation is to make repeated

substitutions for each occurrence of the function tRSum on the right-hand
side until all such occurrences disappear.
tR Sum(n) = 2 + tR Sum(n-1)
= 2 + 2+ tR Sum(n-2)
= 2(2) + tR Sum(n-2)
…
…
…

= n (2) + tR Sum(0)
= 2n + 2, n≥0

So the step count for RSum is 2n+2.

Method 2: Table method

 The second method to determine the step count of an algorithm is to build
a table in which we list the total number of steps contributed by each
statement.
  This figure is often arrived at by first determining the number of steps per
execution(s/e) of the statement and the total number of times (i.e.,
frequency) each statement is executed.
 The s/e of a statement is the amount by which the count changes as a result
of the execution of that statement.
 By combining these two quantities, the total contribution of each statement
is obtained.
 By adding the contributions of all statements, the step count for the entire
algorithm is obtained
 Example 3: The step count of an algorithm can be determined by using the
table method as follows. Constructing Frequency Table

Table 1.1 Frequency table method for Sum of n natural numbers

Table 1.2 Frequency table method for Sum of n natural numbers using recursion
MODULE 3 : Asymptotic notations:
Asymptotic Notation (O,Ω, θ)

The following notations are commonly use notations in performance analysis and used to
characterize the complexity of an algorithm:

1. Big–OH (O)

2. Big–OMEGA (Ω)

3. Big–THETA (Θ) and

Asymptotic Analysis of Algorithms

Our approach is based on the asymptotic complexity measure. This means that we don‟t try to
count the exact number of steps of a program, but how that number grows with the size of the
input to the program. That gives us a measure that will work for different operating systems,
compilers and CPUs. The asymptotic complexity is written using big-O notation.

 It is a way to describe the characteristics of a function in the limit.

 It describes the rate of growth of functions.

 Focus on what‟s important by abstracting away low-order terms and constant factors.

 It is a way to compare “sizes” of functions

Table 1.3 Order of growth

 Big Oh Notation:

 Big oh(O) notation is used to represent upper bound of algorithm runtime.

 Let f(n) and g(n) are two non-negative functions

 Definition: The function f(n) = O(g(n)) if and only if there exists positive constants c
and n0 such that f(n)≤c*g(n) for all n , n ≥ n0.

Fig 1.1 Big Oh Notation

Example

If f(n)=3n+2 then prove that f(n) = O(n)

Let f (n) =3n+2, c=4, g (n) =n

if n=1 3n+2≤ 4n
3(1)+2 ≤ 4(1)
3+2≤4
5≤4 (F)

if n=2 3n+2≤4n
3(2)+2≤4(2)
8≤8 (T)
3n+2≤4n for all n ≥2
This is in the form of f(n) ≤ c*g(n) for all n ≥ no, where c=4, no =2
Therefore, f(n) = O(n).
Big Omega Notation:

 Big Omega(Ω) notation is used to represent lowerbound of algorithm runtime.

 Let f(n) and g(n) are two non-negative functions

 Definition: The function f(n) = Ω(g(n)) if and only if there exists positive constants c
and n0 such that f(n) ≥ c*g(n) for all n , n ≥ n0.

Fig 1.2 Big Omega Notation

Example

f(n)=3n+2 then prove that f(n) = Ω(g(n))

Let f(n) =3n+2, c=3, g(n) =n

if n=1 3n+2 ≥ 3n 3(1)
+ 2 ≥ 3(1)
5 ≥ 3 (T)
3n+2 ≥ 4n for all n ≥ 1
This is in the form of f (n) ≥ c*g(n) for all n≥ no, where c=3, no=1
Therefore, f (n) = Ω (n).

Big Theta Notation:

 Big Theta(ɵ) notation is used to represent the running time between upper bound
and lower bound.

 Let f(n) and g(n) be two non-negative functions.

Definition: The function f(n) = θ(g(n)) if and only if there exists positive constants c1 , c2 and n0
such that c1*g(n) ≤ f(n)≤c2* g(n) for all n, n≥n0

Fig 1.3 Big Theta Notation

Example:

f(n)=3n+2 then Prove that f(n) = θ (g(n))

Lower bound=3n+2 ≥ 3n for all n ≥ 1
c1=3, g(n) = n, no=1
Upper Bound = 3n+2 ≤ 4n for all n ≥ 2
c2 = 4, g(n) = n, n0 = 2
3(n) ≤ 3n+2 ≤ 4(n) for all n, n ≥ 2
This is in the form of c1*g(n) ≤ f(n) ≤ c2* g(n) for all n ≥ no Where c1=3, c2=4, g(n)=n, no=2

MODULE 4: AVL trees – creation, insertion, deletion operations and

applications:

AVL TREES
BALANCED TREES (OR) HEIGHT BALANCED TREES
 Trees whose height in the worst case turns out to be O(log n) are called balanced trees.
Example: AVL trees,2-3 trees, Red Black Trees, Splay trees.
 We can guarantee O(log n) performance for the search ,insert and delete operations of a
search tree by ensuring that the search tree height is always O(log n).
 Since trees are balanced by working with their height, they are also known as height
balanced trees.
  Definition: A height balanced tree T is a binary tree that may be empty. If non empty,
then
1. Its left and right sub trees must also be height balanced trees
2. The height of left and right sub trees differ by at most 1 i.e |HL-HR|<=1
 Examples of Balanced trees: AVL trees, Splay trees, Red Black trees, B trees and B+
trees.

AVL TREES

 An AVL tree is a binary search tree in which difference between the heights of the left
and right sub trees will be either -1, 0 or 1.
 Therefore an AVL tree is a balanced/height balanced binary search tree.
 Definition: An empty binary tree is an AVL tree. If T is a non empty binary tree with
TL and TR are its left and right sub trees, then T is an AVL tree if and only if
1) TL and TR are AVL trees and
2) |HL-HR|<=1 where HL and HR are the height of left sub trees(TL) and right sub tree
(TR) respectively of T.
Balance factor (bf) is associated with every node is an AVL tree which may be either 0
or +1 or -1.
 Balance factor: The balance factor bf(u) of a node u is defined as the height of the left
sub tree of u minus the height of the right sub tree of u.
 bf(u) = ( h(uL) - h(uR) ) where h(uL) and h(uR) are the height of the left and right sub
trees of the node u respectively.

Properties of AVL Tree:

1) The minimum height of an AVL tree with n elements is O(log n)
2) The maximum height of an AVL tree with n elements is 1.44
3) An n-element AVL tree can be searched in O(height)= O(log n) time.
4) A new element can be inserted into an n-element AVL search tree so that the result
is an n+1 element AVL tree and such an insertion can be done in O(log n) time.
5) An element can be deleted from an n-element AVL search tree so that the result is
an n-1 element AVL tree and such a deletion can be done in O(log n) time.
Examples:

Fig 1.4 AVL tree Fig 1.5 Not an AVL tree

Operations on an AVL Trees

The basic operations performed on an AVL tree are
1. Inserting a new element
2. Deleting an element
3. Searching an element

Insertion operation on AVL Trees

 In AVL Tree, new node is always inserted as a leaf node. The insertion operation is
performed as follows....
 Step 1: Insert the new element into the tree using Binary Search Tree insertion
logic.
 Step 2: After insertion, check the Balance Factor of every node.
 Step 3: If the Balance Factor of every node is 0 or 1 or -1 then go for next
operation.
 Step 4: If after insertion the balance factor of any of the nodes turns out to be
anything other than 0, +1 or -1, then the tree is said to be unbalanced.
 To balance the tree we perform rotations
 Rotations: Rotations are mechanisms which shift some of the sub trees of the
unbalanced tree either to left or right to obtain a balanced tree.
 There are four rotations and they are classified into two types.
 LL ROTATION
(Single Right Rotation)
SINGLE ROTATION

RR ROTATION
(Single Left Rotation)

LR ROTATION
(Left Right Rotation)
DOUBLE ROTATION

RL ROTATION
(Right Left Rotation)

Fig 1.6 AVL Rotations

LL Rotation (Single Right Rotation)

 The new node „x‟ is inserted in the Left sub tree of left child of node A. As a result, the
balance of A becomes +2.
 To restore balance at A Single right rotation need to be applied at A.

General Notation:

Example:
RR Rotation (Single Left Rotation)
 The new node „x‟ is inserted in the Right sub tree of right child of node A. As a result,
the balance of A becomes -2.
 To restore balance at A Single left rotation need to be applied at A.
General Notation:

Example:

LR Rotation (Left Right Rotation)

 Imbalance occurred at A due to the insertion of node x in the right sub tree of left child
of node A.
 LR rotation involves sequence of two rotations
(i) Single Left rotation/RR rotation
(ii) Single Right rotation/LL rotation
 General Notation:

Example:

RL Rotation (Right Left Rotation)

 Imbalance occurred at A due to the insertion of node x in the Left sub tree of right child
of node A.
 RL rotation involves sequence of two rotations
(i) Single Right rotation/LL rotation
(ii) Single Left rotation/RR rotation
General Notation:

[Type text]
Example:

Example for Construction of an AVL Tree

Construct AVL tree for the list by successive insertion: 5, 6, 8, 3, 2, 4, 7
i. Insert 5 into empty tree
Deletion operation On AVL Trees
The sequences of steps to be followed in deletion are:
1. Initially, the AVL tree is searched to find the node to be deleted
2. If the search is successful, delete the node. The following are the 3 possibilities for the
node „x‟ that is to be deleted
(i) x is a leaf – In this case the leaf node is discarded
(ii) x has exactly one non empty sub tree – If x has no parent, the root of its sub tree
becomes the new search tree root. If x has a parent P, then we change the pointer from
parent p so that it points to x‟s only child
(iii) x has two non empty sub trees – x is replaced with either the largest element in the
left sub tree or the smallest element in its right sub tree.
 3. After deletion of node, check the balance factor of each node
4. Rebalance the tree if the tree is unbalanced. For this AVL tree deletion rotations are used.
 On deletion of a node x from the AVL tree. Let A be the closest ancestor node on the
path from x to the root node, with a balance factor of +2 or -2. To restores balance at
node A, we classify the type of imbalance as follows:
 L – type imbalance:
o The imbalance is of type L if the deletion took place from A‟s left sub tree.
o The balance factor of A = -2
o A has a right sub tree with root B
o L-type imbalance is sub classified into types L0, L1 and L-1 depending on the
balance factor of B
L0 Rotation
 L0 imbalance occurs if the deletion takes place from the left sub tree of A and balance
factor of B is 0
 L0 rotation is Single Left rotation, that is applied at node A
General Notation:

Example:

Before deletion After deleting 26 After L0 rotation

L1 Rotation
 L1 imbalance occurs if the deletion takes place from the left sub tree of A and balance
factor of B is 1
 L1 rotation is RL rotation, which involves 2 rotations:
i. Single Right
ii. Single Left
General Notation:

Example:

Before deletion After deleting 16 After L1 rotation

L-1 Rotation
 L-1 imbalance occurs if the deletion takes place from the left sub tree of A and balance
factor of B is -1
 L-1 rotation is Single Left rotation, that is applied at node A

General Notation:
Example:

Before deletion After deleting 16 After L-1 rotation

 R – type Imbalance:
o The imbalance is of type R if the deletion took place from A‟s Right sub tree.
o The balance factor of A = 2
o A has a left sub tree with root B
o R-type imbalance is sub classified into types R0, R1 and R-1 depending on the
balance factor of B

R0 Rotation

 R0 imbalance occurs if the deletion takes place from the Right sub tree of A and balance
factor of B is 0
 R0 rotation is Single Right rotation, that is applied at node A
General Notation:
Example:

R1 Rotation
 R1 imbalance occurs if the deletion takes place from the Right sub tree of A and balance
factor of B is 1
 R1 rotation is Single Right rotation, that is applied at node A

General Notation:

Example:
R-1 Rotation
 R-1 imbalance occurs if the deletion takes place from the Right sub tree of A and balance
factor of B is -1
 R-1 rotation is LR rotation, which involves 2 rotations:
i. Single Left
ii. Single Right
General Notation:

Example:

Searching an element
Searching operation on AVL search tree is same as Binary Search Tree.

Applications of AVL Trees

1. Databases and File Systems: AVL trees are used in databases and file systems to maintain
ordered data efficiently. They help in fast lookup, insertion, and deletion operations,
ensuring that the data structure remains balanced for optimal performance.
 2. Memory Management: In memory management systems, AVL trees are
used to keep track of free memory blocks. The balancing property of AVL
trees ensures that the allocation and deallocation of memory can be
performed efficiently.
3. Routing Algorithms: In network routing algorithms, AVL trees help manage
routing tables and maintain the shortest path to different nodes in a network.
4. Compiler Optimisation: AVL trees are used in compiler design for various
optimisations, such as constant folding, code motion, and dead code
elimination. They help in maintaining the structure of the code in an
optimised manner.
5. Multimedia Applications: In multimedia systems, AVL trees can be used
for indexing and searching multimedia files like images, videos, and audio
files. The balanced nature of AVL trees ensures quick access to these files.
6. Scheduling Systems: AVL trees are used in scheduling systems to manage
tasks or processes based on priority. They ensure that the highest priority task
is always executed first and new tasks are inserted efficiently.
7. Geometric Applications: In computational geometry, AVL trees are used to
manage and query geometric objects, such as points, lines, and polygons.
They help in solving problems like finding the nearest neighbour or
detecting intersections.

MODULE 5: B- trees – creation, insertion, deletion operations

and applications:

B- TREES

B trees are extended binary search trees that are specialized in m-way searching, since the
order of B trees is 'm'. Order of a tree is defined as the maximum number of children a node
can accommodate. Therefore, the height of a b tree is relatively smaller than the height of
AVL tree and RB tree.

They are general form of a Binary Search Tree as it holds more than one key and two
children.

The various properties of B trees include –

  Every node in a B Tree will hold a maximum of m children and (m-1) keys, since the
order of the tree is m.
 Every node in a B tree, except root and leaf, can hold at least m/2 children
 The root node must have no less than two children.
 All the paths in a B tree must end at the same level, i.e. the leaf nodes must be at the
same level.
 A B tree always maintains sorted data.

B trees are also widely used in disk access, minimizing the disk access time
since the height of a b tree is low.

Basic Operations of B Trees

The operations supported in B trees are Insertion, deletion and searching with the time
complexity of O(log n) for every operation.

Insertion operation

The insertion operation for a B Tree is done similar to the Binary Search Tree but the
elements are inserted into the same node until the maximum keys are reached. The insertion
is done using the following procedure −
Step 1 − Calculate the maximum (m−1)(m−1) and, minimum (⌈m2⌉−1)(⌈m2⌉−1) number of
keys a node can hold, where m is denoted by the order of the B Tree.
Step 2 − The data is inserted into the tree using the binary search insertion and once the keys
reach the maximum number, the node is split into half and the median key becomes the
internal node while the left and right keys become its children.

Step 3 − All the leaf nodes must be on the same level.

The keys, 5, 3, 21, 9, 13 are all added into the node according to the binary search property
but if we add the key 22, it will violate the maximum key property. Hence, the node is split in
half, the median key is shifted to the parent node and the insertion is then continued.

Another hiccup occurs during the insertion of 11, so the node is split and median is shifted to
the parent.
While inserting 16, even if the node is split in two parts, the parent node also overflows as it
reached the maximum keys. Hence, the parent node is split first and the median key becomes
the root. Then, the leaf node is split in half the median of leaf node is shifted to its parent.

The final B tree after inserting all the elements is achieved.

Deletion operation

The deletion operation in a B tree is slightly different from the deletion operation of a Binary
Search Tree. The procedure to delete a node from a B tree is as follows –

Case 1 − If the key to be deleted is in a leaf node and the deletion does not violate the
minimum key property, just delete the node.
Case 2 − If the key to be deleted is in a leaf node but the deletion violates the minimum key
property, borrow a key from either its left sibling or right sibling. In case if both siblings have
exact minimum number of keys, merge the node in either of them.
Case 3 − If the key to be deleted is in an internal node, it is replaced by a key in either left
child or right child based on which child has more keys. But if both child nodes have
minimum number of keys, theyre merged together.
Case 4 − If the key to be deleted is in an internal node violating the minimum keys property,
and both its children and sibling have minimum number of keys, merge the children. Then
merge its sibling with its parent.
B-Tree applications

 Large databases employ it to access information stored on discs.

 Finding data in a data set can be done in a great deal less time.
 Multilevel indexing is possible with the indexing feature.
 The B-tree method is also used by the majority of servers.
 In CAD systems, B-Trees are used to catalogue and search geometric data.
 Other applications of B-Trees include encryption, computer networks, and natural
language processing.
 Since accessing values stored in a large database that is stored on a disc takes a long
time, B trees are used to index the data and provide quick access to the actual data
stored on the disks.