Unit 3: Non- Linear Data

Structures

Lecturer: Shimirwa Aline Valerie

 Introduction To Non
Linear Data Structures
 Unlike linear data structures, such as arrays and linked
lists, nonlinear data structures do not follow a strict
linear order. Instead, they allow for more complex
relationships and connections between elements.
 Nonlinear data structures are designed to represent
relationships, hierarchies, and networks. They are
widely used in various applications, including
databases, graph algorithms, artificial intelligence, and
more. Trees , Graphs, heaps, hash tables and tries are
most common nonlinear data structures.
 6. Leaf: Also known as a terminal node, a leaf is a node
that has no children. It is located at the bottom of the tree.
Introduction to trees 7. Edge: The connection between nodes is represented by
an edge. It defines the relationship between nodes.
Tree: In data structures, a tree is a nonlinear hierarchical data
structure that consists of nodes connected by edges. It is similar to a 8. Path: A path is a sequence of nodes connected by
real-world tree, where the nodes represent elements and the edges edges. It represents the route from one node to another in
represent the relationships between those elements. the tree.
9. Depth: The depth of a node is the number of edges
some basic terminologies commonly used in trees: between the root and that particular node. The root node
1. Root: The topmost node of a tree. It has no parent and serves as has a depth of 0.
the starting point for traversing the tree. 10. Height: The height of a node is the number of edges
2. Node: Each element or entity in a tree is represented by a node. in the longest path from that node to a leaf node. The
Nodes contain data and can have references to child nodes. height of the tree is the height of the root node.

3. Parent: The immediate predecessor of a node is called its 11. Subtree: A subtree is a smaller tree that is formed by
parent. It is the node directly above a particular node. selecting a node and all its descendants. Each node in a
tree, excluding the root, can be considered as the root of
4. Child: The nodes directly below a specific node are called its its own subtree.
children. A node can have multiple children.
12. Parental Relationship: The relationship between a
5. Sibling: Nodes that share the same parent are called siblings. parent node and its child nodes is called the parental
They are on the same level of the tree. relationship.
 Introduction to trees cont..

13. Node Degree: The degree of an individual node is the

number of children it has. For example, a node with no
children (a leaf node) has a degree of 0, while a node with
three children has a degree of 3.
14. Tree Degree: The degree of a tree is defined as the
maximum degree among all nodes in the tree. It represents
the maximum number of children any node in the tree can
have.
15. Level of a Node: The level of a node is determined by
the number of edges or steps needed to reach that node
from the root node. For example, The root node of a tree
is always at level 0 and immediate children of the root
node are at level 1, their children are at level 2, and so on.
 Application of tree data 5. Network Routing: Tree structures such as
spanning trees and routing trees are used in
structure network protocols to determine efficient routes
and minimize network congestion.
1. File Systems: Tree structures are commonly used to
represent file systems. Each directory is represented as a
node, and the hierarchical structure allows for efficient
organization, navigation, and retrieval of files. These are just a few examples of the wide
range of applications where tree data structures
2. Database Systems: Trees are used in database systems for are utilized. Trees provide an efficient and
indexing and searching. organized way to represent hierarchical
3. HTML/XML Parsing: Tree structures are used to parse and relationships and facilitate various operations
represent the hierarchical structure of HTML or XML and algorithms in different fields.
documents. This allows for easy traversal and manipulation
of the document structure.
4. Decision Making and Classification: trees are used in
machine learning and data mining for decision-making and
classification tasks. They provide a structured representation
of decision rules and help in analyzing and predicting
outcomes.
 AVL Tree: An AVL (Adelson-Velskii and
Landis) tree is a self-balancing binary search tree
Types of the tree in which the heights of the left and right subtrees
of any node differ by at most one. AVL trees
There are several types of trees based on their specific automatically reorganize themselves to maintain
characteristics and properties. Here are some commonly balance, ensuring efficient operations.
encountered types of trees:
Red-Black Tree: A red-black tree is another
 Binary Tree: A binary tree is a tree in which each node type of self-balancing binary search tree. It
has at most two children, referred to as the left child maintains balance through the use of color
and the right child. It is one of the most fundamental properties assigned to the nodes. Red-black trees
types of trees and is widely used in various provide guaranteed logarithmic time complexity
applications. for searching, insertion, and deletion operations.
 Binary Search Tree (BST): A binary search tree is a
binary tree in which the left child of a node contains a
value smaller than the node's value, and the right child
contains a value greater than the node's value. BSTs
are often used for efficient searching, insertion, and
deletion operations.
 Introduction to Binary tree  Traversal: Binary trees can be traversed in different
ways, such as in-order traversal (left-child, parent,
Binary Tree: In data structures, a binary tree is a type of tree right-child), pre-order traversal (parent, left-child,
where each node has at most two children, known as the left right-child), and post-order traversal (left-child,
child and the right child. It is a hierarchical data structure in right-child, parent). These traversal methods
which each node can have zero, one, or two children. determine the order in which the nodes are visited
Here are some key characteristics of a binary tree: and processed.
 Node Structure: Each node in a binary tree contains a
data element and two references (pointers or links) to its
left and right child nodes. The left child node is smaller
or less than the parent node, and the right child node is
greater or equal to the parent node, depending on the
specific ordering property of the binary tree.
 Empty Tree: An empty binary tree is represented by a
special null value or by a node with empty references
for both the left and right child nodes.
 Subtree Structure: Each child node in a binary tree can
itself be the root of its own subtree, forming a recursive
structure. This allows for the representation of complex
hierarchical relationships.
 Types of Binary Tree

1. Complete Binary Tree: A complete binary tree is a

binary tree in which all levels, except possibly the
last, are completely filled, and all nodes are as far left
as possible. It is typically used in array-based
representations of binary trees.
2. Full Binary Tree: A full binary tree is a binary tree in
which every node has either 0 or 2 children. In other
words, every node is either a leaf node or has two
child nodes
3. Perfect Binary Tree: A perfect binary tree is a binary
tree in which all levels are completely filled with
nodes. It is a complete binary tree where all leaf
nodes are at the same level.
 Memory Representation of a Array-based Representation
tree
A tree can be represented in memory using different data structures
such as array and linked list.
 Array-based Representation: In an array-based
representation, the tree is stored in a contiguous block of
memory, typically an array. The nodes of the tree are arranged
in a specific order based on the tree traversal (e.g., breadth-
first, depth-first). Each node in the array stores its data element,
and the child-parent relationships are determined using the
indices of the array elements. For example, for a node at index
i, its left child would be at index 2i+1 and its right child at
index 2i+2. This representation is efficient in terms of memory Linked list-based Representation
usage but may require additional space for unused elements
when the tree is not completely full.
 Linked list-based Representation: In a linked structure
representation, each node of the tree is represented as a struct
or an object that contains the data element and a link to its
parent node (if required) and a link to one of its child nodes
(typically the left child). This structure forms a hierarchical
linked list-like structure, where nodes are connected through
these links. This representation is commonly used for binary
trees, where each node has at most two child nodes.
 Binary Tree implementation
in C
 To create a binary tree, you can use a recursive
algorithm that builds the tree from its individual nodes.
Here is an algorithm to create a binary tree:
 Step 1: Define the structure for the tree node
 Step 2: Create a function to create a tree:
 In this function the user is prompted to enter the
data for each node of the binary tree. It creates a
new node for each data value and recursively calls
itself(createTree) function to create the left and
right child nodes. The process continues until the
user enters -1 to indicate no further nodes.
 Step 3: Implement the main function to demonstrate
the binary tree creation.
 Binary Tree Traversal
 Binary tree traversal refers to the process of visiting each
node in a binary tree in a specific order. There are three
commonly used methods of binary tree traversal: in-order
traversal, pre-order traversal, and post-order traversal.
1. Pre-Order Traversal: In a pre-order traversal, the
nodes of the binary tree are visited in the following
order(current node, left node, right node).
2. In-Order Traversal: In an in-order traversal, the nodes
of the binary tree are visited in the following order( left,
current node , right).
3. Post-Order Traversal: In a post-order traversal, the
nodes of the binary tree are visited in the following
order(left , right, current node
 Algorithms For Traversing
Binary Tree
 There are three commonly used methods of binary tree
traversal: in-order, pre-order and post-order traversal.
 Introduction to Binary
Search Tree
 A binary search tree (BST) is a data structure used for
organizing and storing elements in a way that allows efficient
search, insertion, and deletion operations.
 A binary search tree ,also known as ordered binary tree is a
binary tree wherein the nodes are arranged in a order. The order
is :
a. All the values in the left sub-tree has a value less than that of
the root node.
b. All the values in the right node has a value greater than the
value of the root node.
c. The same rule is carried forward to all the sub-tree in tree.
 Since the tree is already ordered, the time taken to carry out a
search operation on the tree is greatly reduced as now we don’t
have to traverse the entire tree, but at every sub-tree we get hint
where to search next.
 Binary trees also help in speeding up the insertion and deletion
operation.
 Insertion 0peration in BST
Algorithm to insert a node into a binary search tree:
1.If the tree is empty, create a new node with the given value and
make it the root.
2.If the value to be inserted is less than the value of the current
node:
1. If the left child of the current node is empty, create a new
node with the given value and make it the left child of the
current node.
2. If the left child of the current node is not empty, recursively
insert the value into the left subtree.
3.If the value to be inserted is greater than the value of the current
node:
1. If the right child of the current node is empty, create a new
node with the given value and make it the right child of the
current node.
2. If the right child of the current node is not empty,
recursively insert the key into the right subtree.
 Deletion operation in BST
To delete a node from a binary search tree, you can follow these
steps:
1. Start at the root node and traverse the tree to find the node to be
deleted, keeping track of its parent node.
2. If the node is not found, the deletion operation terminates.
3. If the node to be deleted has no children (i.e., it is a leaf node), you
can simply remove it by updating its parent node's reference to
null.
4. If the node to be deleted has only one child, you can replace the
node with its child by updating the parent node's reference to point
to the child node.
5. If the node to be deleted has two children, you need to find its in-
order successor or predecessor node. The in-order successor is the
smallest node in the right subtree, and the in-order predecessor is
the largest node in the left subtree. Replace the node to be deleted
with its successor/predecessor and recursively delete the
successor/predecessor node from the tree.
6. When deleting the successor/predecessor node, apply the deletion
 Search Operation in BST
Algorithm to search a node in a binary search tree:
1. Start at the root node.
2. If the tree is empty or the current node is the node we
are searching for, return the current node.
3. If the value of the node we are searching for is less
than the value of the current node, recursively search
in the left subtree.
4. If the value of the node we are searching for is greater
than the value of the current node, recursively search
in the right subtree.
 Introduction to Graphs

 A Graph is a non-linear data structure consisting of

vertices and edges. The vertices are sometimes also
referred to as nodes and the edges are lines or arcs that
connect any two nodes in the graph. More formally
a Graph is composed of a set of vertices( V ) and a set
of edges( E ). The graph is denoted by G(V, E).
 A graph is a data structure that is used to represent
connections or relationships between objects.

Components of a Graph
 A finite set of vertices also called nodes.
 A finite set of ordered pair of the form (u, v) called
edge. The pair is ordered because (u, v) is not the same
as (v, u) in the case of a directed graph(di-graph). The
pair of the form (u, v) indicates that there is an edge
from vertex u to vertex v. The edges may contain
weight/value/cost.
 Directed Graph (Digraph): A directed graph
is a graph where the edges have a specific
Types of graphs direction. The edges can be traversed only in
the direction specified by the edge. Example: A
There are several types of graphs in graph theory, each web page graph, where web pages are
with its own unique characteristics. Here are some represented as vertices, and links between web
common types of graphs: pages are represented as directed edges.
 Undirected Graph: An undirected graph is a graph
where the edges have no specific direction. The edges
can be traversed in both directions. Example: A social
network graph, where users are represented as vertices,
and friendships between users are represented as
undirected edges.
 Complete Graph: A complete graph is a
graph where there is an edge between every
Types of graphs cont.. pair of distinct vertices. In other words, all
vertices are directly connected to each other.
 Weighted Graph: A weighted graph is a graph where Example: A round tournament graph, where
each edge has a numerical weight or value associated participants in a tournament are represented as
with it. These weights can represent distances, costs, or vertices, and there is an edge between every
any other relevant quantity. Example: A transportation pair of participants.
network graph, where cities are represented as vertices,
and the edges are weighted by the distance between
cities.
 Acyclic Graph: An acyclic graph is a graph
that does not contain any cycles.
Types of graphs cont..
 Cyclic Graph: A cyclic graph is a graph that contains
at least one cycle, which is a path that starts and ends
at the same vertex. Example: A chemical compound
graph, where atoms are represented as vertices, and
there are edges between atoms based on their chemical
bonds.
 Types of graphs cont..

 Bipartite Graph: A bipartite graph is a graph whose

vertices can be divided into two disjoint sets such that
there are no edges between vertices within the same
set. In other words, the vertices can be partitioned into
two independent sets. Example: A matching graph,
where job applicants and job positions are represented
as vertices, and there is an edge between an applicant
and a position if the applicant is qualified for the
position.
 Internet and Web: The World Wide Web can
Real World Application Of Graph In be represented as a directed graph, with web
Data Structure pages as nodes and hyperlinks as edges. Web
crawlers and search engines use graph
Graphs have numerous real-world applications in various algorithms to discover and index web pages,
domains. Here are some examples of how graphs are used determine page ranks, and provide relevant
in data structures: search results.
 Social Networks: Social media platforms like Recommendation Systems: Graphs play a
Facebook, Twitter, and LinkedIn represent connections crucial role in recommendation systems, which
between users as a graph. Graph data structures help suggest products, movies, music, or other items
analyze relationships, recommend friends or to users. Collaborative filtering techniques
connections, detect communities, and study utilize graph-based similarity measures between
information propagation. users or items to generate recommendations.

 Transportation Networks: Graphs are used to model Computer Networks: Graphs model network
transportation systems, such as roads, railways, and topologies and connectivity between devices.
flight routes. Graph algorithms can optimize routes, Graph algorithms assist in routing, network flow
calculate distances, determine the shortest path, and optimization, identifying bottlenecks, and
analyzing network performance.
analyze traffic flow.
 Representations of Graphs

A graph can be represented in different ways depending on the

application and requirements. The two most common
representations are:
1. Adjacency Matrix: In this representation, a graph is
represented as a two-dimensional matrix, where the rows The adjacency matrix for the above graph
and columns correspond to the vertices. Each cell in the is:
matrix indicates whether there is an edge between the
corresponding vertices. For example, if there is an edge
between vertex i and vertex j, the cell (i, j) or (j, i) will
have a value of 1. If the graph is weighted, the cell can
store the weight of the edge instead of just 1 or 0. This
representation is commonly used when the graph is dense,
i.e., it has many edges compared to the maximum
possible number of edges.
2. Adjacency List: In this representation, each vertex of the
graph is associated with a list of its neighboring vertices.
 Representations of Graphs cont..

Implementation of adjacency matrix:

 We follow the below pattern to use the adjacency
matrix in code:
 In the case of an undirected graph, we need to
show that there is an edge from vertex i to
vertex j and vice versa. In code, we assign adj[i][j]
= 1 and adj[j][i] = 1.
 In the case of a directed graph, if there is an edge
from vertex i to vertex j then we just assign adj[i]
[j]=1.
 Adding an edge takes O(1) time.
 Adjacency Matrix representation Consumes more
space O(V2). Even if the graph is sparse(contains less
number of edges), it consumes the same space.
 Representations of Graphs cont..

2. Adjacency List: In this representation, each vertex of

the graph is associated with a list of its neighboring
vertices. This representation is commonly used when the
graph is sparse, i.e., it has fewer edges compared to the
maximum possible number of edges.
The adjacency list for the above graph is:
 Algorithm of Breadth-First Search:
Graph Traversal •Step 1: Consider the graph you want to
navigate.
 Graph traversal is the process of visiting all the vertices in a
•Step 2: Select any vertex in your graph (say v1),
graph in a systematic way. There are two commonly used
methods for graph traversal: Depth-First Search (DFS) and from which you want to traverse the graph.
Breadth-First Search (BFS). •Step 3: Utilize the following two data structures
Breadth-First Search (BFS) for traversing the graph.
• Visited array(size of the graph)
 Breadth-First Search (BFS) is a graph traversal algorithm that
explores all the vertices of a graph in breadth-first order, i.e., it • Queue data structure
visits all the vertices at the same level before moving on to the
next level. •Step 4: Add the starting vertex to the visited
array, and afterward, you add v1’s adjacent
 The time complexity of breadth-first search (BFS) is O(V + E), vertices to the queue data structure.
where V is the number of vertices and E is the number of edges
in the graph. This is because BFS visits each vertex and each •Step 5: Now using the FIFO concept, remove
edge exactly once. In the worst case, BFS may visit all vertices the first element from the queue, put it into the
and edges in the graph. visited array, and then add the adjacent vertices
 The space complexity of BFS is O(V), where V is the number of the removed element to the queue.
of vertices in the graph. This is because BFS uses a queue to
store the nodes to visit, and in the worst case, all vertices can be •Step 6: Repeat step 5 until the queue is not
added to the queue. empty and no vertex is left to be visited.
 Illustration of Breadth-First Step 3: Remove node 0 from the front of queue
and visit the unvisited neighbors and push them
Search (BFS) Algorithm into queue.

Step1: Initially queue and visited arrays are empty.

Step2: Push node 0 into queue and mark it visited. Step 4: Remove node 1 from the front of queue
and visit the unvisited neighbors and push them
into queue.
 Illustration of Breadth-First
Search (BFS) Algorithm cont.. Steps 7: Remove node 4 from the front of
queue and visit the unvisited neighbors and
Step 5: Remove node 2 from the front of queue and visit push them into queue. As we can see that every
the unvisited neighbors and push them into queue. neighbors of node 4 are visited, so move to the
next node that is in the front of the queue.

Step 6: Remove node 3 from the front of queue and visit

the unvisited neighbors and push them into queue. As we
can see that every neighbors of node 3 is visited, so move
to the next node that are in the front of the queue.
 Depth First Search(DFS) for Follow the below method to implement DFS
traversal.
a Graph • Step 1: Create an array to keep track of visited nodes.

 Depth-first search (DFS) is a graph traversal algorithm • Step 2: Choose a starting node.
that explores a graph by visiting as far as possible • Step 3: Create an empty stack and push the starting
along each branch before backtracking. It starts at a node onto the stack.
specific node (often called the "source" or "start" node) • Step 4: Mark the starting node as visited.
and explores as deep as possible before backtracking
and visiting the next unvisited neighbor. • Step 5: While the stack is not empty, do the following:
• Pop a node from the stack.
 The DFS algorithm can be implemented using a stack
• Process or perform any necessary operations on
data structure. the popped node.
• Get all the adjacent neighbors of the popped
node.
• For each adjacent neighbor, if it has not been
visited, do the following:
• Mark the neighbor as visited.
• Push the neighbor onto the stack.
• Step 6: Repeat step 5 until the stack is empty.
 Illustration of Depth First
Search(DFS) Step 3: Now, Node 1 at the top of the stack,
so visit node 1 and pop it from the stack and
 Step1: Initially stack and visited arrays are empty. put all of its adjacent nodes which are not
visited in the stack.

 Step 2: Visit 0 and put its adjacent nodes which are not
Step 4: Now, Node 2 at the top of the stack,
visited yet into the stack.
so visit node 2 and pop it from the stack and
put all of its adjacent nodes which are not
visited (i.e, 3, 4) in the stack.
 Illustration of Depth First
Search(DFS) cont.. The time complexity of depth-first search
(DFS) for a graph depends on the representation
 Step 5: Now, Node 4 at the top of the stack, so visit of the graph and the specific implementation of
the algorithm.
node 4 and pop it from the stack and put all of its
 If the graph is represented using an
adjacent nodes which are not visited in the stack.
adjacency matrix, the time complexity of
DFS is O(V^2), where V is the number of
vertices. This is because, in each step, we
need to iterate through the entire row of the
adjacency matrix to find the neighbors of a
given vertex.
 Step 6: Now, Node 3 at the top of the stack, so visit  If the graph is represented using an
node 3 and pop it from the stack and put all of its adjacency list, the time complexity of DFS
adjacent nodes which are not visited in the stack. is O(V + E), where V is the number of
vertices and E is the number of edges. This
is because, in each step, we need to iterate
through the adjacency list of a vertex to find
its neighbors.
 How to find Shortest Paths in a graph Follow the steps below to solve the problem:
using Dijkstra’s Algorithm • Create a set sptSet (shortest path tree set) that keeps
track of vertices included in the shortest path tree,
i.e., whose minimum distance from the source is
 Given a graph and a source vertex in the graph, find calculated and finalized. Initially, this set is empty.
the shortest paths from the source to all vertices in the
• Assign a distance value to all vertices in the input
given graph.
graph. Initialize all distance values as INFINITE.
 Examples: given below graph, find the shortest path Assign the distance value as 0 for the source vertex
take 0 as source vertex: so that it is picked first.
• While sptSet doesn’t include all vertices
• Pick a vertex u that is not there in sptSet and has a
minimum distance value.
• Include u to sptSet.
• Then update the distance value of all adjacent
vertices of u.
• To update the distance values, iterate through all
adjacent vertices.
• For every adjacent vertex v, if the sum of the
distance value of u (from source) and weight of
edge u-v, is less than the distance value of v, then
update the distance value of v.
 Illustration of How to find Shortest
Paths in a graph using Dijkstra’s
Algorithm

Step 1:
 The set sptSet is initially empty and distances assigned
to vertices are {0, INF, INF, INF, INF, INF, INF, INF}
where INF indicates infinite.
 Now pick the vertex with a minimum distance value.
The vertex 0 is picked, include it in sptSet.
So sptSet becomes {0}. After including 0 to sptSet,
update distance values of its adjacent vertices.
 Adjacent vertices of 0 are 1 and 7. The distance values of
1 and 7 are updated as 4 and 8.
 The following subgraph shows vertices and their
distance values, only the vertices with finite distance
values are shown. The vertices included in SPT are
shown in green colour.
 Illustration of How to find Shortest
Paths in a graph using Dijkstra’s
Algorithm cont..

Step 2:
 Pick the vertex with minimum distance value and not
already included in SPT (not in sptSET). The vertex 1
is picked and added to sptSet.
 So sptSet now becomes {0, 1}. Update the distance
values of adjacent vertices of 1.
 The distance value of vertex 2 becomes 12.
 Illustration of How to find Shortest
Paths in a graph using Dijkstra’s
Algorithm cont..

Step 3:
 Pick the vertex with minimum distance value and not
already included in SPT (not in sptSET). Vertex 7 is
picked. So sptSet now becomes {0, 1, 7}.
 Update the distance values of adjacent vertices of 7.
The distance value of vertex 6 and 8 becomes finite
(15 and 9 respectively).
 Illustration of How to find Shortest
Paths in a graph using Dijkstra’s
Algorithm cont..

Step 4:
 Pick the vertex with minimum distance value and not
already included in SPT (not in sptSET). Vertex 6 is
picked. So sptSet now becomes {0, 1, 7, 6}.
 Update the distance values of adjacent vertices of 6.
The distance value of vertex 5 and 8 are updated.
 Illustration of How to find Shortest
Paths in a graph using Dijkstra’s
Algorithm cont..

Step 4:
 Pick the vertex with minimum distance value and not
already included in SPT (not in sptSET). Vertex 6 is
picked. So sptSet now becomes {0, 1, 7, 6}.
 Update the distance values of adjacent vertices of 6.
The distance value of vertex 5 and 8 are updated.
 Illustration of How to find Shortest
Paths in a graph using Dijkstra’s
Algorithm cont..

 We repeat the above steps until sptSet includes all

vertices of the given graph. Finally, we get the
following Shortest Path Tree:
 Exercise
G is the weighted graph representing the paths between
some locations of Rwanda. The aim of this exercise is to
produce the shortest path between these locations.
a. Build the adjacency matrix of the graph G.
b. Create the shortest path from Musanze to Rusizi by
using Dijkstra’s algorithm.