UNIT-2.pdf advanced data structure notes

UNIT-II

TREES:
A tree is a non linear data structure used to represent data containing
hierarchical relationship between elements.
F J
A
B C D
E G H I K
L M N

Complete Binary Tree:
A binary tree is said to be a complete binary tree, if all its level except possibly the last
level, have the maximum number of positive nodes, and all the nodes at the last level
appear as for left as possible.

LEVEL NODES
0 1
1 2
2 4
3 5
1
2 3
4 6
75
11 128 9 10

Full Binary Tree:
A binary tree is a full binary tree, if it contains maximum number of nodes in all level
1
2 3
4 6
7
8 9 10
5
11 12 13
14 15
LEVEL NODES
0 1
1 2
2 4
3 8

TYPES OF BINARY TREE
There are several types of binary trees possible each with its own properties
1. Expressin Tree
2. Binary Search Tree
3. Heap Tree
4. Threaded Binary Tree
5. Huffman Tree
6. Heighted Balanced Tree (Or) AVL Tree
7. Decission Tree
HEAPS:
Definition:
Max Tree:
A max tree is a tree in which the value in each node is greater than or equal to
those in its children.
MinTree:
A min tree is a tree in which the value in each node is less than or equal to those
in its children.

Max Heap:
A max heap is a max tree that also a complete binary tree.

( Max Heap )
95
85 45
75
25 35 15
55
65

Min Heap:
A min heap is a min tree that also a complete binary tree.
( Min Heap )
15
45 25
55
65 35 75
85
95

Operations on Heap Tree
1)Insertion into a Heap tree:
This operation is used to insert a node into an existing heap tree satisfying the
properties of heap tree.
95
85 45
75
25 35 15
55
65

INSERTION ALGORITHM
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 tree, but tree that
not necessarily a heap.
2) Then let ITEM rise to its appropriate place in H so that H is finally a heap.

Inclusion of 19 in the fashion of complete binary tree and it satisfies the
properties of heap.
95
85 45
75
25 35 15
55
65 19

When 111 is inserted into the heap tree.
111
95 45
75
85 35 15
55
65 25
19

Deletion of a node from a Heap Tree:
Any node can be deleted from a heap tree. But from the application point
of view, deleting root node has some special importance.
➢Read the root node into a temporary storage say, ITEM.
➢Replace the root node by the last node in the heap tree. Then repeat the
tree as stated below.
➢Let newly modified root node be the current node. Compare its value with
value of its child. Let X be the child those value is the largest. Interchange
the value of X with the value of the current node.
➢Make X as the current node.
➢Continue reheap if the current node is not an empty node.

99
45 63
35
29 57 42
27
12 24 26

63
55 57
35
29 26 42
27
12 24
(Deletion of root node 99 from a max heap tree)

Applications of Heaps:
1.PriorityQueues:Heapsarecommonlyusedtoimplementpriority
queues,whereelementswithhigherpriorityareextractedfirst.Thisis
usefulinmanyapplicationssuchasschedulingtasks,handling
interruptions,andprocessingevents.
2. Sorting Algorithms: Heapsort, a comparison-based sorting algorithm,
is implemented using the Heap data structure. It has a time complexity
of O(n log n), making it efficient for large datasets.
3. Graph algorithms: Heaps are used in graph algorithms such asPrim’s
Algorithm,Dijkstra’s algorithm., and theA* search algorithm.
4. Lossless File Compression: Heaps are used in data compression
algorithms such as Huffman coding, which uses a priority queue
implemented as a min-heap to build a Huffman tree.

5.Medical Applications: In medical applications, heaps are used to store
and manage patient information based on priority, such as vital signs,
treatments, and test results.
6.Load balancing: Heaps are used in load balancing algorithms to
distribute tasks or requests to servers, by processing elements with
the lowest load first.
7.Order statistics:The Heap data structure can be used to efficiently find
the kth smallest (or largest) element in an array.
8.Resource allocation: Heaps can be used to efficiently allocate
resources in a system, such as memory blocks or CPU time, by
assigning a priority to each resource and processing requests in order
of priority.

GRAPHS
Definition: A graph G=(V,E) is a ordered pair of finite sets V and E. The elements of ‘V’
are called vertices (Vertices are also called nodes or points). The elements of ‘E’ are
called edges(Edges are also called arcs and lines). Each edge in E joins two different
vertices of ‘V’ and is denoted by the tuple (i, j), Where i and j are the two vertices
joined by E.
V1

V4 V2
V3

V={V1, V2, V3, V4}
E={ (V1,V2), (V1,V3),(V1,V4), (V2,V3), (V3,V4)}

Digraph (or) Directed Graph:
A digraph is also called directed graph. It is a graph G such that G=<V,E>, Where V is
the set of all vertices and E is the set of ordered pair of verticies from V.
Ex:

V1
V4 V2
V3
i) A digraph is said to be strongly connected if and only if the edge is possible in both
directions.
ii) A digraph is said to be weekly connected if and only if the edge is only in one
direction.
i.e from V1 to V2 (or) V2 to V3

Weighted Graph:
A graph or digraph is termed as weighted graph if all the edges in it are labelled with
some weights. V1
5 7
V4 9 V2
6 3
V3
Adjacent Vertices:
A vertex Vi is adjacent or neighbor of another vertex say Vj, if there is an edge from Vi
to Vj. V1
V4 V2
V3
In the above figure V2 is adjacent to V3

Self Loop:
If there is an edge whose starting and ending vertices are same, that is (Vi, Vi)
is an edge, then it is called a self loop or simply a loop.
V1
V2

V3
The above graph has a self loop at vertex V4.
Parallel Edges:
If there are more than one edges between the same pair of vertices, then
they are known as parallel edges.
In the above graph there are two parallel edges between V1 and V2.
Multigraph:
A graph which has either self loop or parallel edges or both is called as
multigraph.
V4

Simple Graph:
A graph (Digraph) if it does not have any self loop or parallel edges is called a
simple graph (Digraph)
V1
V4 V2
V3
Complete Graph:
A graph (Digraph) G is said to be complete if each vertex Vi is adjacent to every
other vertex Vj in G. In other words, there are edges from any vertex to all other
vertices.
V1

V4 V2
V3

Cyclic Graph:
If there is a path containing one or more edges which starts from a vertex Vi
and terminates into the same vertex then the path is known as a cycle. If a graph
does not have any cycle then it is call acyclic graph.
Ex: V1
V1 V4 V2
V4 V2
V3 V3
(Cyclic Graph) (Acyclic Graph)
Isolated Vertex:
A vertex is isolated if there is no edge connected from any other vertex to the
vertex.
V1 V1’ V’
V4 V2 .u
V3’ V2’
V3
In above graph u is an isolated vertex.

Degree of Vertex:
The number of edges connected with vertex Vi is called the degree of vertex
Vi and it is denoted by degree(Vi).
V1
V4 V2

V3
degree(V4)=3
degree(V3)=3
degree(V2)=3
degree(V1)=3

Connected Graph: In a graph (Not digraph) G, two vertices Vi and Vj are said to be
connected if there is a path in G from Vi to Vj.

V1
V4 V2
V3
Pendent Vertex: A vertex Vi is pendant if indegree(Vi) =1 and outdegree(Vi)=0
For example
V1
V2 V3

V4 V5 V6 V7
In the above graph there are 4 pendant vertices V4, V5, V6, V7

Representation of a Graph
A graph can be represented as
1. Set Representation
2. Linked Representation
3. Sequential (or) Matrix Representation
1.Set Representation:
This is one of the straight forward method representing a graph. With this method
two sets are maintained
i) ‘V’, The set of vertices
ii) ‘E’ The set of edges, which is the subset of V X V.
But if the graph is weighted graph, The set E is the ordered collection of 3 tuples
i.e E= W X V X V, where W is the set of weights.

V(G1)= {V1, V2, V3, V4, V5, V6, V7}
E(G1)= {(V1,V2), (V1,V3), (V2,V4), (V2,V5), (V3,V6), (V3,V7)}
V1
V2
V3
V4 V5 V7V6

5

2 3 1 6 7
4

8
V(G) = {A,B,C,D}
E(G) = {(3,A,C), (5,B,A), (1,B,C), (7,B,D), (2,C,A), (4,C,D), (6,D,B), (8,D,C)}
A B
C
D

2. Linked Representation:
Linked representation is another space saving way of representation. In this
type two types of node structures is assumed as shown below.

(Node structure for non weighted graph)

(Node structure for weighted graph)
In the linked representation, the number of lists depends on the number of vertices in
the graph. The header node in each list maintains a list of all adjacent vertices of a
node.
Node
Label
Adjacency
List
Node
Label
Adjacency
List
Weight

V1
V2
V3
V4 V5 V7V6
V1.
V2. V3^
V3 V1 V6 V7^
V7 V3^
V2 V1 V4 V5^
V5 V2^
V6 V3^
V4 V2^

5
2 3 1 6 7

4

8

A B
C
D
^
B 1C^ D 5A7
C 2A^
^
C^8
D^4
D 6B^
A 3C^

3. Matrix Representation:
Matrix representation is the most useful way of representing any graph. This
representation uses a square matrix of order nXn, n being the number of vertices in
the graph.
Entries in the matrix can be decided as follows
a
ij = 1 if there is an edge from Vi to Vj
= 0 otherwise
This matrix is known as adjacency matrix (or) Path matrix (or) Reachable
matrix.
V1 V2 . . . . Vj . . . . Vn
V1 .
V2 .
. .
. .
Vi . . . . . . . a
ij
.
.
Vn nXn
[Matrix Representation of Graph]

V1 V2 V3 V4 V5 V6 V7
V1 0 1 1 0 0 0 0
V2 1 0 0 1 1 0 0
V3 1 0 0 0 0 1 1
V4 0 1 0 0 0 0 0
V5 0 1 0 0 0 0 0
V6 0 0 1 0 0 0 0
V7 0 0 1 0 0 0 0
[ Matrix Representation of Graph ]
V1
V2
V3
V4 V5 V7V6

+

a b
c d
a b c d
a 0 0 0 1
b 1 0 1 1
c 1 0 0 1
d 0 0 1 0

1 7
2 3 6
4

8
5

A B C D
A 0 0 3 0
B 5 0 1 7
C 2 0 0 4
D 0 6 8 0
A B
C
D