Non Linear Data

Structures

D. Mpini
Learning Outcomes
• Introduction to Non Linear Data Heaps
Structures
○ Introduction
• Trees
○ Max heap
○ Introduction
○ Min heap
○ Key Terms
○ Heapify
○ Binary Tree
○ Applications of Heaps
○ Binary Search Tree
○ Implementation
○ Traversing a BST
○ • Graphs
Ternary Tree
• Introduction
○ AVL Tree
• Key Terms
○ Red Black Tree
• Applications of Graphs
○ Segment Tree
• Types of Graphs
○ N-ary Tree
• Graph Representation
○ B Tree
Introduction to Non Linear Data Structures

1 2 3

Non-linear data structures are Instead, the arrangement is These structures are more
data structures where the hierarchical or flexible and can represent
data elements are not interconnected, allowing real-world relationships more
arranged sequentially or complex relationships effectively compared to linear
linearly. between elements.
structures.
Trees

Concept of Trees Why trees

• Visualise a normal tree • parsing expressions

you know drawn • searches
downward • Certain document types,
• At the top of every tree is such as XML and HTML,
the so-called root node. can also be represented
This is the ancestor of all in a tree form
other nodes in the tree
Key terms

Each circled alphabet represents a node. A node is any structure that holds
Node data.

The root node is the only node from which all other nodes come. A tree with
Root node an undistinguishable root node cannot be considered as a tree.

A sub-tree of a tree is a tree with its nodes being a descendant of some

other tree.
Sub tree Nodes F, K, and L form a sub-tree of the original tree consisting of all the
nodes.
Key terms

• The number of sub-trees of a given node. A tree consisting of only

one node has a degree of 0. This one tree node is also considered as
Degree
a tree by all standards.
• The degree of node A is 2.

• This is a node with a degree of 0.

Leaf node
• Nodes J, E, K, L, H, M, and I are all leaf nodes.

The connection between two nodes. An edge can sometimes connect a

Edge node to itself, making the edge appear as a loop.
Key terms

• A node in the tree with other connecting nodes is the parent of those
Parent nodes.
• Node B is the parent of nodes D, E, and F.

• This is a node connected to its parent.

Child
• Nodes B and C are children of node A, the parent and root node.

• All nodes with the same parent are siblings.

Sibling • This makes the nodes B and C siblings.
Key terms

• The level of a node is the number of connections from the root node.
Level
• The root node is at level 0. Nodes B and C are at level 1.

• This is the number of levels in a tree.

Height
• Our tree has a height of 4.

• The depth of a node is the number of edges from the root of the tree
to
Depth
• that node.
• The depth of node H is 2.
Binary Trees

• A binary tree is one in which each

1 node has a maximum of two
children.

• Binary trees are very common, and

we shall use them to build up a BST
2 implementation in
Python.
Binary Search Tree
• A binary search tree (BST) is a special kind of a binary tree in which all the nodes in the
left sub-tree are less than or equal to the value of that node.
• That is, it is a tree that is structurally a binary tree.
• Functionally, it is a tree that stores its nodes in such a way to be able to search through
the tree efficiently.
Other Types of Trees

Ternary Tree: each node AVL Tree: is a self- Red-Black Tree: self-
can have up to three balancing binary search balancing binary search tree
children, distinguishing it tree, ensuring that the with the key innovation of
from binary trees. height difference between assigning colours (red or
every node's left and right black) to its nodes.
subtrees is at most one.

Segment Tree: versatile N-ary Tree: generalisation B-Tree/Balanced Tree:

and efficient data structure of binary trees where each self-balancing search tree
for solving range query node can have up to N data structure renowned for
problems on an array or a children, providing a more its efficient handling of large
list. flexible and scalable datasets and optimal
hierarchical structure. performance for disk
storage systems.
Traversing a Binary Search Tree
Visiting all the nodes in a tree can be done depth first or breadth first.
These modes of traversal are not peculiar to only binary search trees but trees in general.

Breadth First Approach Depth First Approaches

• This kind of traversal starts from the root of a • Here we follow a branch (or edge) to its limit
tree and visits the node from one level of the before recoiling upwards to continue
tree to the other traversal.
• This mode of traversal is made possible by •
using a queue data structure. We will be using the recursive approach for
• Starting with the root node, we push it into a the traversal.
queue. •
• The node at the front of the queue is accessed There are three forms of depth-first traversal,
(dequeued) and either printed and stored for namely
later use. • in-order > visit the left sub-tree, the parent
• The left node is added to the queue followed node, and finally the right sub-tree.
by the right node. • pre-order > visit the left sub-tree, the parent
• This process is repeated until queue is all node, and finally the right sub-tree.
done • post-order > visit the left sub-tree, the right
sub-tree, and lastly the root node.
Implementation

Implenting a Binary Tree Implementing a Binary Search Tree

Implementation

Breadth First Traversal Depth First Traversal

• In order
• Pre order
• Post order
Heaps
Heaps

Definition Properties

• Heap data structure is a complete binary • The heap property states that any given
tree that satisfies the heap property. node is
• always greater than its child node/s and the
key of the root node is the largest among all
other nodes. This property is also
called max heap property.
• always smaller than the child node/s and the
key of the root node is the smallest among
all other nodes. This property is also
called min heap property.
Heaps

Max heap Min heap

Heapify

• Heapify is the process of creating a heap data structure

Definition from a binary tree.
• It is used to create a Min-Heap or a Max-Heap.

• Step 1 − Create a new node at the end of heap.

• Step 2 − Assign new value to the node.
Steps • Step 3 − Compare the value of this child node with its
parent.

• Step 4 − If value of parent is less than child, then swap

them.
• Step 5 − Repeat step 3 & 4 until Heap property holds.
Applications of Heaps

Priority Queues Sorting Algorithms

Heaps are the foundation for implementing • Heapsort is a popular sorting algorithm that
efficient priority queues. These queues prioritize utilizes the heap data structure.
elements based on their key value, ensuring the • It has a time complexity of O(n log n), making
highest (or lowest) priority element is accessed it efficient for sorting large datasets.
first. This makes them ideal for:
• Job Scheduling: Prioritizing tasks based on
their urgency or deadlines.
• Event Processing: Handling high-priority
events first in real-time systems.
• Network Routing: Prioritizing packets in
network traffic based on importance.
Applications of Heaps

Graph algorithms Order statistics

Many graph algorithms rely on heaps for their Heaps allow for efficient retrieval of the kth largest
efficient operation. These include: or smallest element in a dataset. This is useful for
• Dijkstra's Algorithm: Finding the shortest applications like:
path between nodes in a graph. • Finding the top k search results: Ranking
• Prim's Algorithm: Finding the minimum search results based on relevance.
spanning tree of a graph. • Maintaining leaderboards: Keeping track of
• Kruskal's Algorithm: Finding the minimum top players in games.
spanning tree of a graph.
Practical

Create a BT Heapify a BT
Graphs
Graphs

• Data structure which • • A graph data structure

consists of data stored in Nodes: vertices (V,E) consists of:
a collection of • • A collection of
interconnected nodes Edges: paths between vertices (V) or nodes.
and edges nodes • A collection of
edges (E) or path
Graphs

• V = {a, b, c, d, e, f, g}
• E = {ab, bc, cd, de, df,
ef, eg, fg, ag}
• |V|=7
• |E|=9
Applications of Graphs

World wide web Biggest graph in the world

Search engines Mapping search results

Software & Social networks, Mapping applications, booking

applications applications data storage
Key Terms
Path finite or infinite set of edges which joins a set of vertices. It can connect to 2 or more
nodes.

Closed path path in which the initial node is same as terminal(end) node

Simple path path that does not repeat any nodes(vertices).

Degree number of edges connecting a node in the graph

Loop A loop (also called a self-loop) is an edge that connects a vertex

to itself. It is commonly defined as an edge with both ends as the
same vertex
Types of Graphs
Cycle Graph graph in which all the vertices are of degree 2.

Connected Graph graph in which there is an edge or path joining each pair of
vertices.

Complete Graph In a complete graph, there is an edge between every single pair
of node in the graph.
Types of Graphs
Weighted Graph In weighted graphs, each edge has a value associated with
them (called weight). It refers to a simple graph that has weighted
edges. The weights are usually used to compute the shortest
path in the graph.

Directed Graph In Directed Graphs, we can only traverse from one node to
another if the edge have a direction pointing to that node

Consider a family tree or a one way street

Undirected Graph Undirected graphs have edges that do not have a direction.
Hence, the graph can be traversed in either direction.

topology of digital social networks, where each friend of someone

is that someone’s friend; Suppose Steve is a friend of John, then
John too is the friend of Steve.
computer networks, like if one device is connected to another,
Graph Representation
Adjacency Matrix
● 2 dimensional array of size V x V

● where V is the number of nodes in a graph

Graph Representation
Adjacency List
● represents a graph as an array of linked lists.
Practical

Forming a graph Representing tree