CO2

Generics
And
Collection Framework
[Link] Reddy

[Link] Reddy
 • Introduction
• List
• Queue
• Set interface
• Map s
Agenda • Comparable and
Comparator interfaces
• Binary Search and AVL
Trees
• Graphs Introduction
• BFS and DFS
02/01/2023 Generics and collection framework [Link] Reddy 2
Evolution of Collection
Framework
• What is a Collection and
Collection Framework?
• Why we need a Collection
Framework?
• What are the different Collection
classes available?

9/3/20XX Presentation Title [Link] Reddy 3

Introduction
Collection is a simple entity which
represents multiple objects or group of
Objects.

Collection Framework defines various

interfaces and classes by which we can
represent a group of objects into a
collection.

9/3/20XX Presentation Title [Link] Reddy 4

Why Collection Framework in JAVA
• Storing value into a • Storing 100 values in a single
variable variable.

int a = 10; int[ ] array = new

int[100];

0 1 2 …... 99
.

9/3/20XX Presentation Title [Link] Reddy 5

Limitations of Array Collection
Framework
• Fixed size (Not Growable in • Growable in nature
nature) and Memory wastage
• Store both
• Storing Homogeneous data
Homogeneous and
only
Heterogeneous data
• No underlying Data Structure
(Can’t support ready-made • Implements an underlying
Methods)
Data Structure
Overcome through
9/3/20XX (Supports
Presentation Title ready-made
[Link] Reddy 6
Collection Framework Hierarchy
ArrayLi
st implemen
List LinkedLis
Iterable ts
t
Vector Stac
k

Collection PriorityQueu Orange –

Queue e interfaces
Blue border -
ex
s

classes
ten

HashSet
d

Set LinkedHashS
et
SortedSe TreeSet
9/3/20XX
t [Link] Reddy 7
Collections class
• Collections class is different from Collection interface.
• Collections is a java utility class present in [Link] package.
• Collections class provide static methods to perform
operations on collection interface classes.
• e.g. arraylist : 23 32 12 54 12
• Syntax : [Link](arraylist);
[Link]();

9/3/20XX Presentation Title [Link] Reddy 8

List interface
• When to choose List interface!

1. Insertion order of objects needs to be preserved.

2. To allow duplicate objects.

• All the methods present in Collection interface are also

available to List interface

• All the methods present in List interface are also available to

ArrayList, LinkedList classes.

9/3/20XX Presentation Title [Link] Reddy 9

 List

ArrayList

[Link] Reddy
ArrayList implements List
• ArrayList is a java class present in util package which
predominantly works based on “index”.
• Syntax :
ArrayList arraylist = new ArrayList(); //accepts
Heterogeneous data
The default size of arraylist = 10.
Grows dynamically at Run-Time.

• ArrayList doesn’t work with primitive datatypes(int, float, char etc).

• We need to use Wrapper classes(Integer, Double, Float Character
etc).
[Link] Reddy
ArrayList Constructors

• ArrayList() : builds an empty arraylist.

• ArrayList(Collection c) : builds an arraylist of size of

the collection specified.

• ArrayList(int capacity) : build an arraylist that has

the specified initial capacity.

9/3/20XX Presentation Title [Link] Reddy 12

ArrayList methods
• boolean contains(Object o)
• add(Object o)
• boolean containsAll(Collection
• add(int index, Object o)
c)
• addAll(int index,
• boolean isEmpty()
Collection c)
• Object toArray()
• addAll(Collection c)
• asList()
• size()
• remove(int index)
• get(int index)
• remove(Object o)
• set(int index, Object o)
• removeAll(Collection c)
• iterator()
• How to shuffle ArrayList
• How to sort ArrayList?
elements?
9/3/20XX Presentation Title [Link] Reddy 13
Ways to iterate over Collection
• for loop / While loop
• for-each loop
• Iterator interface () (Universal iterator)
• ListIterator() extends Iterator
• forEach() method
uses Lambda Expression
• forEachRemaining() method

9/3/20XX Presentation Title [Link] Reddy 14

for loop for-each loop
e.g. Arraylist variable  al • e.g. Arraylist variable  al

for(int i=0 ; [Link]() ; i++) for(Object s : al){

{ [Link](s);
}
[Link]([Link](i))
;
}

9/3/20XX Presentation Title [Link] Reddy 15

Iterator interface ListIterator
• e.g. Arraylist variable  al • e.g. Arraylist variable  al

Iterator itr = [Link](); ListItterator is used to iterator

While([Link]()){ in both directions.
[Link]([Link]());
} Forward direction : hasNext(),
next()
• hasNext() – check if iterator has Backward direction :
the elements hasPrevious,
• next() – print element and move previous()
to next
Syntax same as Iterator.
9/3/20XX Presentation Title [Link] Reddy 16
ArrayList
• List arraylist = new ArrayList(); //Non-Generic ArrayList

• Since JDK 1.5 Java Collection Framework is Generic.

• Java’s new generic collection allows us to have only one type of

object in a collection, thus providing Type-Safety.

• List<String> arraylist = new ArrayList<String>(); //Generic

• ArrayList will raise a Compile-time error if we add another type

object in Generic Collection.

9/3/20XX Presentation Title [Link] Reddy 17

Generics
• Generics means Parameterized types.

• The idea is to allow type(Integer, String, Character

etc and User-defined types) to be a parameter to
methods, classes and interfaces.

• Generics make possible to create classes that work

with different datatypes.

9/3/20XX Presentation Title [Link] Reddy 18

Generics
• An entity such as class, interface or method that
operates on a parameterized type is a generic entity.

• Generics make code stable by detecting the bugs at

compile time.

• Generics forces the Java programmer to specify the

specific type .

9/3/20XX Presentation Title [Link] Reddy 19

Benefits of Generics
• Type-Safety
• No Typecasting
• Compile-Time Checking

9/3/20XX Presentation Title [Link] Reddy 20

No Type-Safety -- JAVASCRIPT

9/3/20XX Presentation Title [Link] Reddy 21

Type-Safety -- JAVA

9/3/20XX Presentation Title [Link] Reddy 22

Type-Casting
ArrayList al = new ArrayList();
[Link](“dog”);
String name = [Link](0); //returns object
[Link](name); //o/p: Compile-Time error

String name = (String)[Link](0); //typecasting the Object

to String
[Link](name); //o/p : dog

9/3/20XX Presentation Title [Link] Reddy 23

Generic Classes
• A generic class is implemented exactly like a non-
generic class except a type parameter section.

• There can be more than one parameter type separated

by comma.

• The classes which accept parameter types are known

as Parameterized classes or Parameterized types.

9/3/20XX Presentation Title [Link] Reddy 24

Type Parameters
The type parameter naming conventions are important.
• T – Type
• E – Element
• K –Key
• V – Value
• N - Number

9/3/20XX Presentation Title [Link] Reddy 25

Generic Classes

• Syntax : class TestGenerics<T>{

}
TestGenerics<Integer> al = new
TestGenerics<Integer>();
TestGenerics<String> al = new TestGenerics<String>();
• Syntax : class Test<T,U>{
}
Test<Integer> al = new Test<Integer>();
Test<Float> al = new Test<Float>();

9/3/20XX Presentation Title [Link] Reddy 26

LinkedList
• List arraylist = new LinkedList(); //Non-Generic ArrayList

• Java’s new generic collection allows us to have only one type of object
in a collection, thus providing Type-Safety.

• List<String> arraylist = new LinkedList<String>();

//Generic

• LinkedList<String> arraylist = new LinkedList<>(); //Generic

• Compile-time error will arise if we add objects of different type in

Generic Collection.

9/3/20XX Presentation Title [Link] Reddy 27

Linked List representation

9/3/20XX Presentation Title [Link] Reddy 28

When to prefer Which Collection

ArrayList LinkedList
• For retrieving and searching • For inserting and deletion
an object

9/3/20XX Presentation Title [Link] Reddy 29

List

Vector

Stack

[Link] Reddy
Stack class (LIFO Mechanism)

• Object creation : Stack s = new Stack(); //Non-Generic

Stack<T> s = new Stack<>();
//Generic

9/3/20XX Presentation Title [Link] Reddy 31

Stack class Methods
• push(Object o) : push an element onto the top of Stack

• pop() : returns an element and remove that from stack

• peek() : Checks for top most element.

• empty() / isEmpty() : Checks stack is empty or not

• Search(Object o) : search the specified object and returns the

position of the object.

9/3/20XX Presentation Title [Link] Reddy 32

 Queue

LinkedList PriorityQueu
e

[Link] Reddy
Queue
• If we want to represent a group of elements which are prior to

processing, then we can go for Queue concept.

e.g. sending SMS to n mobile numbers.

• FIFO Mechanism

• Queue interface will be implemented by LinkedList and

PriorityQueue classes. LinkedList also implements List interface

• Queue needs same type of elements.

9/3/20XX Presentation Title [Link] Reddy 34

LinkedList vs PriorityQueue

LinkedList PriorityQueue

• Insertion order preserved • Insertion order preserved

• Duplicates are allowed • Duplicates are allowed

• Allows Heterogeneous data • Allows Only Homogeneous

data

9/3/20XX Presentation Title [Link] Reddy 35

Methods of Queue interface
• boolean add(Object o) : Returns true after element added successfully.
Else raise an exception.

• boolean offer(Object o) : Returns true after adding element successfully.

Else return false.

• Object remove() : Retrieves and removes the head of this queue. This
method differs from poll only in that it throws an exception if this queue is
empty.

• Object poll() : Retrieves and removes the head of this queue, or returns
null if this queue is empty.
9/3/20XX Presentation Title [Link] Reddy 36
Methods of Queue interface
• Object element() : Retrieves, but does not remove, the head of this
queue. This method differs from peek only in that it throws an
exception if this queue is empty.

• Object peek() : Retrieves, but does not remove, the head of this queue,
or returns null if this queue is empty.

• These Queue methods can be used by LinkedList class and

PriorityQueue class.

9/3/20XX Presentation Title [Link] Reddy 37

PriorityQueue
• Object creation :

PriorityQueue<Integer> queue; //instance variable

queue = new PriorityQueue<>; // object creation

9/3/20XX Presentation Title [Link] Reddy 38

 Set

HashSet TreeSet

LinkedHashS
et
[Link] Reddy
HashSet
• It creates a Collection using a hash table(underlying DS) for
storage.

• HashSet store the elements through Hashing mechanism.

• List allow duplicate values whereas Set doesn’t.

• Sorting and shuffling is not possible as there is no sequential

order. To make it possible convert entire HashSet into other
collection classes

9/3/20XX Presentation Title [Link] Reddy 40

Criteria to opt for HashSet
• To maintain unique objects only.

• To allow null values.

• No need of insertion order (elements are inserted based

on their hashcode randomly).

• More search operations.

9/3/20XX Presentation Title [Link] Reddy 41

HashSet
• Object Creation : HashSet<T> hashSet;

hashSet = new HashSet<>(int capacity,

loadfactor);

• initial size of HashSet is 16.

• Load factor / fill ratio for HashSet is 0.75 (size reaches 75%)

9/3/20XX Presentation Title [Link] Reddy 42

HashSet Constructors

• HashSet() : construct a default HashSet.

• HashSet(int capacity)

• HashSet(int capacity, float loadFactor)

• HashSet(Collection c)

9/3/20XX Presentation Title [Link] Reddy 43

HashSet Methods

• All the methods that are present in Set interface and

Collection interface are also available to HashSet
implementation.

• E.g. add(), addAll(), remove(), contains(), containsAll(),

isEmpty(), size()

9/3/20XX Presentation Title [Link] Reddy 44

HashSet Methods

• Union : addAll()
intersection : retainAll()

• Difference : removeAll()

9/3/20XX Presentation Title [Link] Reddy 45

LinkedHashSet (HashTable +
LinkedList)
• Doesn’t allow duplicates.

• Allows null values.

• Maintains Insertion order

9/3/20XX Presentation Title [Link] Reddy 46

LinkedHashSet Methods
• Methods we use in HashSet and LinkedHashSet are
same.

9/3/20XX Presentation Title [Link] Reddy 47

TreeSet
• TreeSet provides an implementation of Set interface and
uses Tree DS for storage.

• TreeSet uses natural ordering i.e. ; TreeSet uses

Comparable interface by default to store its value by
comparing other value.

9/3/20XX Presentation Title [Link] Reddy 48

TreeSet

• Doesn’t allow duplicates.

• Accessing and retrieving operations are quiet faster (Excellent

choice when storing large amounts of sorted information that
must be found quickly).

• Doesn’t allow null value (It will raise NullPointerException at

Run-Time).

• Maintains Ascending order.

9/3/20XX Presentation Title [Link] Reddy 49

TreeSet Methods

• Methods we use in HashSet and TreeSet are same.

9/3/20XX Presentation Title [Link] Reddy 50

Map Hierarchy

e n HashMap LinkedHashMa
l e m
p p
i m
Map ts

ex
te
nd SortedMa TreeMa
s
p p
Orange –
interface
Blue border -
9/3/20XX Presentation Title
classReddy
[Link] 51
Map interface
• Map interface is Nowhere related to Collection interface.
• Map represents a group of Objects in the form of <Key,
Value> pairs.

Entry Objects
Keys
1011 Values
Orange
1021 Grape
1023 Muskmelon

9/3/20XX Presentation Title [Link] Reddy 52

Map interface
• Every Key and Value pair is one Entry(A combination of
key and value).

• So Map is a collection of entries.

• Object Creation : HashMap<K,V> hm = new

HashMap<>();

• Default size of HashMap is 16.

• We can use Custom Datatypes also in HashMap class.

9/3/20XX Presentation Title [Link] Reddy 53
Criteria to go for Map
• Keys should be Unique.

• Allow duplicate Values.

• Data to be arranged in <Key, Value> pairs

9/3/20XX Presentation Title [Link] Reddy 54

Common Scenarios
 To map error codes and their descriptions.

 To map ZIP Codes and cities.

 To map Managers and Employees. Each manager(key)

is associated with a list of employees(value) he
manages.
 To map classes and students. Each class(key) is
associated with a list of students(value).

9/3/20XX Presentation Title [Link] Reddy 55

HashMap
• The underlying data structure for HashMap is
HashTable.

• Insertion order not preserved (Collection classes which

are using Hashing concept doesn’t preserve insertion
order)

• Allow Duplicate values but not Keys.

• Allows only one Null key.

9/3/20XX Presentation Title [Link] Reddy 56
When to go for HashMap
• Whenever we have more number of Search operation
as searching is faster in HashMap class.

9/3/20XX Presentation Title [Link] Reddy 57

HashMap methods
• put(Object key, Object value) : To add an entry in the map.
• putAll(Map map) : To add a map in the map.
• remove(Object key) : Remove an entry for that particular key.
• get(Object Key ) : Returns the value of that particular key.
• boolean isEmpty() : Returns true if map is empty.
• boolean conatinsKey(Object key)
• boolean containsValue(Object value)
• size() : Return the number of entries
• boolean replace(K key, oldValue, newValue)
• boolean replace(K key, V oldValue, V newValue)
• clear() : reset all the entries in the Map
9/3/20XX Presentation Title [Link] Reddy 58
Methods related to Entries
• Set keyset() : Returns all the key in the map as a set of
type Set.

• Why Set as return type for keyset()?

Set doesn’t allow duplicate keys.

• Collection values() : Return all values in the map.

• Set<[Link]<K,V>> entrySet() : Return all the

Entries(keys and values) in
9/3/20XX Presentation Title [Link] Reddy 59
Entry interface
• Each entry can be represented by one more interface called
Entry interface which is sub-interface of Map interface
which was created for HashMap.

• Entry interface can only be used on the Entry in the

HashMap.

• We access Entry by [Link] as it is sub-interface of Map.

9/3/20XX Presentation Title [Link] Reddy 60

Methods for Entry interface
• getKey() : Return key of that particular Entry

• getValue() : To obtain a value of that particular Entry.

Before using above two methods, first we need to extract an

Entry which contains a single key and value from Entryset and then we
apply those 2 methods.

• setValues(Value) : replace the particular Entry value with

the new value

• The above methods works only with Entry interface.

9/3/20XX Presentation Title [Link] Reddy 61

LinkedHashMap

• The difference is it will maintain insertion order as

this is the LinkedList implementation of Map
interface.

9/3/20XX Presentation Title [Link] Reddy 62

HashMap LinkedHashmap

• Provides quick insertion, • Provides order of insertion

Search and deletion where elements can be
operations accessed in their insertion
order

9/3/20XX Presentation Title [Link] Reddy 63

TreeMap

• TreeMap is a Red-Black tree based implementation.

• It provides efficient way of

• Java TreeMap contains values based on the Key.

• TreeMap don’t allows null Keys but allows multiple null

values.

• It maintains Ascending order.

9/3/20XX Presentation Title [Link] Reddy 64

Sorting in Collection
• We can sort the elements of String Objects, Wrapper
Class Objects and User-Defined class Objects.
• Collection interface classes can’t sort the elements on
their own.
• Collections provide static methods to sort elements of a
Collection.
• If Collection elements are of a Set type – use TreeSet.
• To sort arrays, we use Arrays class that provides sort
method.

9/3/20XX Presentation Title [Link] Reddy 65

Sorting in Collection

• If We store Objects of String class or Wrapper classes,

they are Comparable and can be sorted by
implementing the Comparable interface.

• If we want to sort objects of a custom class, then what

we need to do as Custom classes don’t support
Collections class methods ?

9/3/20XX Presentation Title [Link] Reddy 66

Comparable interface
• Comparable interface is mainly used to sort Objects
present in Custom Classes.

• This interface is available in [Link] package.

• It provides only a single sorting sequence(sorting based

on single data member only).

9/3/20XX Presentation Title [Link] Reddy 67

Comparable interface
• Compares this(current) object with the specified object for
order. Returns a negative integer, zero, or a positive integer
as this object is less than, equal to, or greater than the
specified object.

e.g. 1) <  - ve integer

2) >  + ve integer

3) ==  0

9/3/20XX Presentation Title [Link] Reddy 68

Comparable interface
• @throws NullPointerException if the specified object is null

• @throws ClassCastException if the specified object's type

prevents it from being compared to this object.

• Comparable interface has only one method compareTo(T

o).

9/3/20XX Presentation Title [Link] Reddy 69

Comparator interface

• We use Comparator in two scenarios

When I want to sort the objects based on multiple

parameters and we can sort objects based on any choice.
When there is no possibility of implementing any interface
by the class(Not able to use Comparable interface).
A third party library which include this class

9/3/20XX Presentation Title [Link] Reddy 70

Comparator interface

• Compares its two arguments for order. Returns a negative

integer, zero, or a positive integer as the first argument is
less than, equal to, or greater than the second

• o1 < o2  - ve integer

• o1> o2  +ve integer

• o1 == o2  0

9/3/20XX Presentation Title [Link] Reddy 71

Comparator interface
• @param : o1 the first object to be compared.

• @param : o2 the second object to be compared.

• @throws NullPointerException if an argument is null and this

comparator does not permit null arguments

• @throws ClassCastException if the arguments' types

prevent them from being compared by this comparator.

9/3/20XX Presentation Title [Link] Reddy 72

 Comparable
Comparator

• Comparable provides a single • Comparator provides multiple

sorting sequence (sorting sorting sequences (sorting
collection based on single data
collection based on multiple data
member).
member).
• Comparable affects the original
• Comparator doesn’t affect the
class i.e.; actual class is modified.
original class i.e.; actual class is
• Comparable provides
not modified.
compareTo() method to sort
elements. • Comparator provides compare()
method to sort elements.
9/3/20XX Presentation Title [Link] Reddy 73
 Comparat
Comparabl or
e
• Comparable is present in • Comparator is present in
[Link] package. [Link] package.

• We can sort list elements of • We can sort list elements of

Comparable type by Comparator type by
[Link](List) method. [Link](List,
Comparator) method.

9/3/20XX Presentation Title [Link] Reddy 74

Tree Data Structure
Data structure is a way to organise the data in which we
can process the data efficiently.

Categories of DS:

[Link]  {Arrays, Linked List, Stack, Queue}

[Link]-Linear  {Tree, Graphs }

In linear DS, data is arranged in a sequential form while it

is in Hierarchical form in Non-Linear DS.

9/3/20XX Presentation Title [Link] Reddy 75

Traversals
• PreOrder  root, left, right

• InOrder  left, root, right

• PostOrder  left, right, root

9/3/20XX Presentation Title [Link] Reddy 76

Binary Search Tree
• The keys are arranged in BST in such a way that
• All left subtree keys should be smaller than root node

• All right subtree keys should be larger than root node

5
root

3 8

2 4 9
6 leaf
9/3/20XX Presentation Title [Link] Reddy 77
Binary Search Tree

• If we want to store only unique values in our Binary

Search Tree, we can do nothing and just ignore if a
duplicate value is being inserted.

• If we want to store duplicate values in our Binary

Search Tree, we can insert in either the left or the right
subtree. But not both. We have to choose one
beforehand and stick with it.

9/3/20XX Presentation Title [Link] Reddy 78

Binary Search Tree
5
root
If any key in Left subtree
is greater than root, then
BS lid

3 8 that tree is not a valid

Va
T

BST and vice-versa.

4
2 6 9 leaf

9/3/20XX Presentation Title [Link] Reddy 79

Advantages
• Searching is easier as we need to check either Left or
Right subtrees.
• Insertion and deletion operations are faster when
compared to array and LinkedList.

9/3/20XX Presentation Title [Link] Reddy 80

Operations on BST
• Insertion
• Search
• Deletion

9/3/20XX Presentation Title [Link] Reddy 81

Node Representation of BST
class Node {

int key;

Node left;

Node right;

9/3/20XX Presentation Title [Link] Reddy 82

Insert Operation
• Let’s insert K.

1. if node == null, create a new node with the value of the

key field equal to K. We return this newly created node
directly from here.

2. if K <= [Link], it means K must be inserted in the left

subtree of the current node. We repeat(recur) the process
from step 1 for the left subtree.

9/3/20XX Presentation Title [Link] Reddy 83

Insert Operation
3. else K > [Link], which means K must be inserted in
the right subtree of the current node. We
repeat(recur) the process from step 1 for the right
subtree.

4. Return the current node.

9/3/20XX Presentation Title [Link] Reddy 84

Search Operation
• The only difference is that in the insert operation, we try
to follow the path where the element should be inserted
and in the end, create a new node.

• But in search, we try to follow the path where the

element must be present and once we find it, we
directly return that node. If we are not able to find it, we
can just return null.

9/3/20XX Presentation Title [Link] Reddy 85

Deletion operation
• While deletion in BST, its rule should not be violated.

• Deleting a node in BST, three possibilities will arise :

• Deleting a leaf Node.

• Deleting a node having one child.

• Deleting a node having two children.

9/3/20XX Presentation Title [Link] Reddy 86

Deletion operation
• Scenario1 : Deleting a leaf node by replacing it with NULL.

• Scenario2 : Replace target node with its child node and

replace the child node with NULL.

• Scenario3 :
• Find the inorder successor of the node to be deleted.

• After that, replace that node with the inorder successor until the
target node is placed at the leaf of tree.
• Replace the node with NULL.

9/3/20XX Presentation Title [Link] Reddy 87

BST Complexities
Algorithm Average Case Worst Case

Space O(n) O(n)

Insertion O(log n) O(n)

Searching O(log n) O(n)

Deletion O(log n) O(n)

9/3/20XX Presentation Title [Link] Reddy 88

Applications
• Binary Search Tree works really well if your data set is
dynamic and constantly updated, i.e. there are a lot of
insertions or deletions.

• Binary Search Trees can also be used to sort a dynamic

data set. The in-order traversal always gives the sorted
increasing order of all the elements.

9/3/20XX Presentation Title [Link] Reddy 89

BST Case Study
45, 15, 79, 90, 10, 55, 12, 20, 50 – construct a BST
20, 16, 5, 18, 17, 19, 60, 85, 70 – construct a BST when
preOrder is given.
5, 17, 19, 18, 16, 70, 85, 60, 20 - construct a BST when
postOrder is given.

9/3/20XX Presentation Title [Link] Reddy 90

AVL Tree
• Drawbacks of BST

• How BST can be improvised

• AVL Tree

• Rotation in AVL Tree

• Creating AVL Tree

9/3/20XX Presentation Title [Link] Reddy 91

Drawback of BST
• For same keys, we get different shape binary trees that can
be of maximum height or even of minimum height.
• (40,30,10) (40,10,30) (10,40,30) (10,30,40)
(30,10,40)
4
…. 1
4 1
0 0 3
0 0
0

3 1 4 3 1 4
0 0 0 0 0 0

1 3 3 4
0 0 0 0
H=1
H=2
H=2 H=2 H=2

9/3/20XX Presentation Title [Link] Reddy 92

Drawback of BST
• We prefer minimum height BST.

• To overcome this drawback we improvised BST which we call

as AVL Tree by applying Rotations after calculation balance
factor on each node of BST at that point of time.

• By using AVL tree we can achieve logarithmic search time

complexity irrespective of the order of elements.

• O(log n) is better than O(n).

9/3/20XX Presentation Title [Link] Reddy 93

AVL Tree

• An AVL Tree is a “height balanced Binary Search Tree”.

• “balancefactor” property is used to balance the BST

height .

• The difference between the height of every left and right

subtree of every node in the AVL Tree is either {-1,0,1}.

• Tree needs to be balanced if the balance factor is not in the

range of -1 to 1.
9/3/20XX Presentation Title [Link] Reddy 94
AVL Tree
• Balance factor = height of Left Subtree – height of Right
Subtree
• If balance factor of any node is 1  Left Subtree is one level
higher than the Right Subtree.
• If balance factor of any node is 0  Left Subtree and Right Subtree
are of equal height.
• If balance factor of any node is -1  Left Subtree is one level lower
than the Right Subtree.

9/3/20XX Presentation Title [Link] Reddy 95

AVL Tree
e.g.
50 3-2=
1
1–1=0
1–2=-
20 70
1

1–1=
0 0 0 0
10 30 60 80

0 25 40 0

9/3/20XX Presentation Title [Link] Reddy 96

Note
• Always balancing of nodes will be performed from the
bottom of the tree.

9/3/20XX Presentation Title [Link] Reddy 97

AVL Tree Rotations – 4 types
• (40,30,10)

40 30 LL
rotation
30
10 40

10

9/3/20XX Presentation Title [Link] Reddy 98

AVL Tree Rotations
• (10,30,40)

10 30
RR
rotation
30 10 40

40

9/3/20XX Presentation Title [Link] Reddy 99

AVL Tree Rotations
• (40,10,30)

40 40
30

10 30

10 40

30 10

LR rotation

9/3/20XX Presentation Title [Link] Reddy 100

AVL Tree Rotations
• (10,40,30)

10 10
30

40 30

10 40

30
40

RL
rotation
9/3/20XX Presentation Title [Link] Reddy 101
Note
• At any point of time, Rotations are performed only on
three nodes always whatever the size of the tree may
be.

• At every operation, we need to check the balance factor

on every node in order to ensure that the entire tree is
balanced.

• LL, RR  Single Rotation

• LR, RL  Double Rotation

9/3/20XX Presentation Title [Link] Reddy 102
 Special cases
A is
imbalance
A B

L
B AR L
C A

C BR
CL CR
CL CR BR AR

9/3/20XX Presentation Title [Link] Reddy 103

Special cases
A is
imbalance
A C

LR
B AR
B A

BL C

BL CL CR
CL CR AR

9/3/20XX Presentation Title [Link] Reddy 104

Operations on AVL Trees
• All AVL Tree operations are similar to that of BST except
insertion and deletion.

• Upon every insertion and deletion, we need to check

whether the tree is balanced or not.

• If required, the rotations are performed after each

operation to balance the tree.

9/3/20XX Presentation Title [Link] Reddy 105

AVL Tree Complexities
Algorithm Average Case Worst Case

Space O(n) O(n)

Insertion O(log n) O(log n)

Searching O(log n) O(log n)

Deletion O(log n) O(log n)

9/3/20XX Presentation Title [Link] Reddy 106

Note
• AVL Tree never exceed log n height where as in BST it
may vary from log n(normal tree) to n (Skewed tree).

9/3/20XX Presentation Title [Link] Reddy 107

Case Study on AVL Tree
H, I, J, B, A, E, C, F, D, G, K, L
40, 20, 10, 25, 30, 22, 50

9/3/20XX Presentation Title [Link] Reddy 108

Graphs Introduction
• A Graph is a non-linear data structure which is composed
of vertices(V) and a set of Edges(E).

2 3

4 5

9/3/20XX Presentation Title [Link] Reddy 109

Graphs Representation
• To Represent a graph, there are two popular methods:
• Adjacency Matrix  Use for Dense graphs

• Adjacency List  Use for Sparse graph

9/3/20XX Presentation Title [Link] Reddy 110

Adjacency Matrix
• It is used to represent which nodes are adjacent to each
other.

• If there is any weighted graph then instead of 1’s and

0’s, we can store the weight of the edge.

• Space complexity is n2 (n is number of vertices).

9/3/20XX Presentation Title [Link] Reddy 111

Adjacency Matrix
• It is a matrix A[n][n] where n is the “number of vertices”.

Undirected 1 2 3 4
5
Graph
2 3
1 0 1 0 1
2 10 0 1 1
0
1 3 0 1 0 1
1
4 1 1 1 0
1
5 5 0 0 1 1
4
0
5x5

9/3/20XX Presentation Title [Link] Reddy 112

Adjacency Matrix
• It is a matrix A[n][n] where n is the “number of vertices”.

Directed 1 2 3 4
5
Graph
2 3
1 0 0 0 0
2 10 0 0 1
0
1 3 0 1 0 0
1
4 1 0 0 1
0
5 0 1 0 1
4 5
0
5x5

9/3/20XX Presentation Title [Link] Reddy 113

Adjacency List
• Represents a graph as an array of Linked lists.

• The index of an array represents a node.

• Each element in the Linked List represents the nodes that

are connected to that node by an edge.

• The last node in the Linked list will point to null.

• Space complexity is (n+2e).n is number of vertices and e is

edge

9/3/20XX Presentation Title [Link] Reddy 114

Adjacency List
• It is a matrix A[n][n] where n is the “number of vertices”.
Nodes
Undirected 1 2 4
Graph
2 3
2 1 3 4

3 2 4 5
1

4 1 2 3

4 5
5 3 4
5

9/3/20XX Presentation Title [Link] Reddy 115

Graph Operations

• Add Vertex • Has Edge

• Remove Vertex • Graph Traversal

• Add Edge • Display Vertex

• Remove Edge

9/3/20XX Presentation Title [Link] Reddy 116

Applications of Graph
• GPS systems and Google Maps use graphs to find the
shortest path from one destination to another.

• The Google Search algorithm uses graphs to determine the

relevance of search results.

• World Wide Web is the biggest graph. All the links and
hyperlinks are the nodes and their interconnection is the
edges. This is why we can open one webpage from the other.

9/3/20XX Presentation Title [Link] Reddy 117

Applications of Graph
• Social Networks like Facebook, Twitter, etc. use graphs to
represent connections between users.

• The nodes we represent in our graphs can be considered

as the buildings, people, group, landmarks or anything in
general , whereas the edges are the paths connecting
them.

9/3/20XX Presentation Title [Link] Reddy 118

Breadth-First Search Algorithm
• BFS explores all closer vertices of a node before going
down their neighboring vertices.

9/3/20XX Presentation Title [Link] Reddy 119

Rules of Breadth-First Search Algorithm
• A Queue(which facilitates the First In First Out) is used
in Breadth-First Search.

• Since Graphs have no Root, we can start the Breadth-

First Search traversal from any Vertex of the Graph.

• While Breadth-First Search, we visit all the Nodes in the

Graph.

9/3/20XX Presentation Title [Link] Reddy 120

Rules of Breadth-First Search Algorithm
• For every Node already visited, we visit all of its unvisited
neighboring Nodes and add them to Queue.

• Breadth-First Search continues until all Vertices in the

graph are visited.

• There are no loops caused in Breadth-First Search, as we

prevent revisiting the same Node by marking them
visited.

9/3/20XX Presentation Title [Link] Reddy 121

Breadth-First Search Algorithm
• Also known as Level Order Traversal.

5 Uses Queue Data

3 Structure for finding
2
shortest path

1
Take any node as root
6
node, if not mentioned
4 0

9/3/20XX Presentation Title [Link] Reddy 122

Breadth-First Search Algorithm
• Why are we not exploring the already explored nodes?
• This will form a cycle and we will stuck in an infinite

loop. So to handle such scenarios by preventing the

traversal of the same element again, we need to
maintain the state of all visited elements.

9/3/20XX Presentation Title [Link] Reddy 123

Pseudocode of Breadth-First Search
Create a Queue
Mark Vertex V as Visited.
Put V into Queue

While Q is not empty

Remove the head of Q (Let it be Vertex U)
Iterate all Unvisited Neighbors of U
Mark the neighbor as Visited
Enqueue the Neighbor into Q.

9/3/20XX Presentation Title [Link] Reddy 124

Depth-First Search Algorithm
• DFS uses Stack Data Structure.

5
3
Take any node as root
2 node, if not mentioned

4 0

9/3/20XX Presentation Title [Link] Reddy 125

Summary

9/3/20XX Presentation Title [Link] Reddy 126

 127

Venkata Suresh Reddy

[Link] Reddy

Bhavanam
sureshvenkat83@[Link]
Presentation Title
Thank you

9/3/20XX