Effect of Data Structure

• Data structure effect both the structural and functional aspects of the program.
• Different kinds of data structures are suited to different kinds of applications, and some are
highly specialized to specific tasks, For example.
• Relational databases commonly use B-tree indexes for data retrieval
• Compiler implementations usually use hash tables to look up identifiers.

[Link]
• Usually, efficient data structures are key to designing efficient algorithms. Some formal design
methods and programming languages emphasize data structures, rather than algorithms, as
the key organizing factor in software design.

• The implementation of a data structure usually requires writing a set of procedures that
create and manipulate instances of that structure.

[Link]
 Primitive data structure
• Primitive data structures are those which have predefined way of storing data by
the system. And the set of operations that can be performed on these data are
also predefined. They are directly operated upon by the machine instruction.
• Primitive data structures are char, int, float, double. The predefined operations
are addition, subtraction, etc.

[Link]
 Data
Structure

Non-
Primitive
Primitive

Files
Integer float Character Pointer Array List

Non-linear
Linear List
list

Link List
Stack Queues Graphs Trees

[Link]
 Non-Primitive data structure
• But there are certain situations when primitive data structures are not sufficient for our job.
There comes derived data structures and user defined data structures.
• Derived data structures are also provided by the system but are made using primitives like an
array. It can be array of chars, array of int, etc. The set of operations that can be performed on
derived data structures are also predefined.

• Finally, there are user defined data types which the user defines using the primitive and
derived data types using language constructs like structure or class and uses according to their
needs. And the user has to define the set or operations that we can perform on them. User
defines data types are Linked Lists, Trees, etc.

[Link]
 LINEAR DATA STRUCTURE NON-LINEAR DATA STRUCTURE
• In a linear data structure, data elements are
arranged in a linear order where each and every • In a non-linear data structure, data elements are
element are attached to its previous and next attached in hierarchical manner.
adjacent.

• Whereas in non-linear data structure, multiple levels

• In linear data structure, single level is involved.
are involved.

• Its implementation is easy in comparison to non- • While its implementation is complex in comparison
linear data structure. to linear data structure.

• In linear data structure, data elements can be • While in non-linear data structure, data elements
traversed in a single run only. can’t be traversed in a single run only.

• Its examples are: array, stack, queue, linked list, etc.

• While its examples are: trees and graphs.
[Link]
• Homogeneous data: Homogeneous data structures are those data structures
that contain only similar type of data e.g. like a data structure containing only
integer or float values. The simplest example of such type of data structures is an
Array.

• Heterogeneous Data: Heterogeneous Data Structures are those data structures

that contains a variety or dissimilar type of data, for e.g. a data structure that
can contain various data of different data types like integer, float and character.
The examples of such data structures include structures, union etc.

[Link]
 Array
• An array is a is a data structure that stores collection of elements of
same type stored at contiguous memory locations and can be
accessed using an index.

int num[5];

[Link]
 How to declare an array in C

• datatype arrayName[array Size];

• int myarray[5];

• In C, the default value of the elements in an array is undefined or garbage. When an array is declared, the
memory is allocated for the elements of the array, but the values of those elements are not initialized.

• It is important to note that some programming languages, like Java, automatically initialize the elements of an
array to a default value (e.g., 0 for integers, false for booleans, and null for objects) if no initial values are
specified.

• Note that in C, you cannot change the size of the array once it has been declared.

[Link]
 How to initialize an array in C

• dataType arrayName[arraySize] = {value1, value2, ..., valueN};

• int myarray[5] = {1, 2, 3, 4, 5};

• You can also initialize an array like this.

• int myarray[] = {1, 2, 3, 4, 5};

• Here, we haven't specified the size. However, the compiler knows it’s size is 5 as
we are initializing it with 5 elements.

[Link]
• Arrays have several advantages, like:
• Efficient storage and retrieval: Arrays store elements in contiguous memory
locations, which makes it easy to retrieve elements using their index. So very
efficient with large amounts of data.
• Random access(fast access): Arrays allow access to individual elements using their
index, which means that accessing any element of the array takes the same amount
of time.
• Easy to sort and search: Arrays can be easily sorted and searched using algorithms
like binary search, which can be more efficient than searching through unsorted
data.
• Flexibility: Arrays can be used to represent a wide variety of data structures,
including stacks, queues etc.
• Easy to use: Arrays are a simple and easy-to-use data structure that can be easily
understood by programmers of all skill levels.

[Link]
• Arrays also have some disadvantages, likes:
• Fixed size: In most programming languages, arrays have a fixed size that
cannot be changed once they are created. This can make it difficult to work
with data structures that need to grow or shrink dynamically(Internal
Fragmentation) (External Fragmentation).
• No built-in support for insertion or deletion: Inserting or deleting an
element in an array can be time-consuming and require shifting all the
elements after the insertion or deletion point.
• Homogeneous elements: Arrays can only store elements of the same type,
which can be limiting for many requirements.
• Poor performance for some operations: Some operations, such as searching
or inserting elements in a sorted array, can have poor performance compared
to other data structures like hash tables or binary search trees.

[Link]
 Applications of Arrays
• Memory Management: Arrays enable efficient storage of multiple items of the
same type, especially when size is known beforehand.
• Data Representation: Used for vectors and matrices in mathematical operations
like matrix multiplication.
• Database Management: Arrays store and manage datasets in relational
databases, allowing efficient querying and updates.
• Implementing Data Structures: Arrays are foundational for structures like
heaps, hash tables, and strings.
• Caching & Buffering: Arrays act as buffers in systems, storing data temporarily
before writing to slower mediums or transmitting over networks.

[Link]
• Types of indexing in array:
• 0 (zero-based indexing): The first element of the array is indexed by subscript of 0

• 1 (one-based indexing): The first element of the array is indexed by subscript of 1

• n (n-based indexing): The base index of an array can be freely chosen. Usually
programming languages allowing n-based indexing also allow negative index values and
other scalar data types like enumerations, or characters may be used as an array index.

[Link]
 One Dimensional array
• Address of the element at kth index
• a[k] = B + W*k
• a[k] = B + W*(k – Lower bound)
• B is the base address of the array
• W is the size of each element
• K is the index of the element
• Lower bound index of the first element of the array
• Upper bound index of the last element of the array

[Link]
Q Let the base address of the first element of the array is 250 and each
element of the array occupies 3 bytes in the memory, then address of
the fifth element of a one- dimensional array a[10] ?

a[k] = B + W*(k – Lower bound)

[Link]
 Two-Dimensional array
• The two-dimensional array can be defined as an array of arrays. The 2D array is organized as
matrices which can be represented as the collection of rows and columns.
• However, 2D arrays are created to implement a relational database look a like data structure.
It provides ease of holding the bulk of data at once which can be passed to any number of
functions wherever required.

[Link]
 Sparse Matrix
• A matrix is considered sparse if a large number of its elements are zero Conversely, a
matrix with most of its elements being non-zero is termed dense.
• Using a sparse matrix over a regular matrix has distinct advantages:
• Storage Efficiency: Given that a majority of the elements are zeros, sparse
matrices allow for memory conservation by only storing the non-zero elements.
• Computational Speed: By structuring the data to only account for non-zero
elements, operations become faster, as they skip over the zero values.

[Link]
 Array representation
• 2D array is used to represent a sparse matrix in which there are three rows named as
• Row: Index of row, where non-zero element is located
• Column: Index of column, where non-zero element is located
• Value: Value of the non zero element located at index – (row, column)

[Link]
 Linked List Representation
• In linked list, each node has four fields. These four fields are defined
as: Row: Index of row, where non-zero element is located
• Column: Index of column, where non-zero element is located
• Value: Value of the non zero element located at index – (row,column)
• Next node: Address of the next node

[Link]
 Applications of Stack
• Expression Parsing: Stacks help evaluate and check programming
expressions, ensuring balanced parentheses.
• Backtracking: Used in algorithms like maze-solving and the "Eight
Queens" puzzle.
• Function Calls: Manage function details during calls in programming
languages.
• Undo Feature: Implement undo in text editors and browsers.
• Syntax Checking: Compilers use stacks to match syntax elements like
'if' with 'else'.

[Link]
 Stack Implementation
Stack is generally implemented in two ways.
• Static Implementation: - Here array is used to create stack. it is a simple
technique but is not a flexible way of creation, as the size of stack has to be
declared during program design, after that size implementation is not efficient
with respect to memory utilization.

[Link]
Pop: - The process of deleting an element. from the top of stack is called POP operation,
after every POP operation the stack is decremented by one if there is no element in the
stack and the POP operation is requested then this will result into a stack underflow
condition.

POP (S, N, TOP)

{
if (TOP==-1) 5

print underflow and exit 4

y = S[TOP] 3
TOP=TOP-1
2
return(y) and exit
1
}
0

[Link]
• Infix notation: the operator is written in between the operands. e.g. A+B. the
reason why this notation is called infix is the place of operator in the expression.

• Prefix notation: In which the operator is written before the operands it is also
called as polish notation. e.g. +AB

• Postfix: In the postfix notation the operator are written after the operands, so
it is called the postfix notation. It is also known as suffix notation or reverse
polish notation. AB+

[Link]
[Link]
[Link]
 Evaluation of arithmetic expression

• An expression is defined as a number of operands or data items combined using

several operators. There are basically three of notation to represent an
expression.

[Link]
 Recursion
• Recursion is defined as defining anything in terms of itself Recursion is a programming
concept where a function calls itself in order to solve a larger problem by breaking it down
into smaller, more manageable sub-problems. It's a fundamental idea in computer science
and mathematics and is used to design algorithms and solve problems that have repetitive
structures.
• Base Case: Essential to halt recursion. It provides a direct solution without further recursive
calls.
• Recursive Case: The function calls itself to address smaller instances of the problem.
• Call Stack: Each recursive call is added to the program's call stack. Deep recursion might
cause a "stack overflow" error.

[Link]
int factorial(int n)
{
if (n == 0)
{
return 1; // Base case: factorial of 0 is 1
}
else
{
return n * factorial(n-1); // Recursive case
}
}

[Link]
 Iteration
• Iteration refers to the process of repeatedly executing a set of statements as long as a
specified condition remains true. In programming, iteration is commonly
implemented using loops.

• Loop Types:
• For Loop: Used for a known number of repetitions.
• While Loop: Runs as long as a condition is true.
• Do-While Loop: Executes at least once before checking the condition.

• Control Statements:
• Break: Exits the loop.
• Continue: Skips to the next iteration.

• Nested Loops: Loops within loops, often seen in matrix tasks.

[Link]
int factorial(int n)
{
int result = 1;
for(int i = 1; i <= n; i++)
{
result *= i;
}
return result;
}

[Link]
 Aspect Recursion Iteration
Function calls itself to solve sub- Uses loops to repeatedly execute code
Basic Concept
problems. blocks.

Typically uses more memory due to Uses less memory as it doesn't rely on
Memory Usage
call stack. the call stack.

Requires a base case to prevent

Termination Requires a loop exit condition.
infinite loops.

Ease of Can be more intuitive for certain Often simpler and more
Implementation problems. straightforward for repetitive tasks.

Might be slower due to overhead of Typically faster due to direct loop

Performance
function calls.
[Link]
 Queue
• A queue is a linear list of elements in which deletions can take place only at one
end called the front, and insertions can take place only at the end called rear.
• Queue is a first in first out types of data structure(FIFO), the terms ‘Front’ and
‘Rear’ are used in describing a linear list only when it is implemented as a queue.

[Link]
 Dequeue
• In a dequeue, both insertion and deletion operations are performed at either end of the
queues. That is, we can insert an element from the rear end or the front end. Also deletion is
possible from either end.
• This dequeue can be used both as a stack and as a queue.
• There are various ways by which this dequeue can be represented. The most common ways of
representing this type of dequeue are :
• Using a doubly linked list
• Using a circular array

[Link]
• Types of dequeue :
• Input-restricted dequeue : In input-restricted dequeue, element can be
added at only one end but we can delete the element from both ends.
• Output-restricted dequeue : An output-restricted dequeue is a dequeue
where deletions take place at only one end but allows insertion at both
ends.

[Link]
 Priority Queue

• A priority queue is a collection of elements such that each element has been
assigned a priority and such that the order in which elements are deleted and
processed comes from the following rules.
• An element of higher priority is processed before any element of lower
priority
• Two element with the same priority are processed according to the order in
which they were added to the queue.

[Link]
 Problem with Array
• Fixed size and reallocation: Arrays have a fixed size, which can lead to memory waste if the
allocated size is larger than the actual data. Resizing an array often requires creating a new
one and copying elements, which can be inefficient.
• Inefficient insertion and deletion: Adding or removing elements in the middle of an array
requires shifting the remaining elements, resulting in a higher time complexity (O(n))
compared to linked lists.
• Less flexible: Arrays can only store elements of the same data type, and their structure
cannot be easily adapted to different types (e.g., singly, doubly, circular) like linked lists.

0 1 2 3 4 5 6 7

[Link]
• Solution is linked list
• A linked list is a dynamic data structure that consists of elements called nodes,
which are connected in a linear sequence. Each node contains two parts: data and a
reference to the next node.
• The first part is the information part of the node, which can store any type of
information, such as integers, characters, or objects.
• The second part called linked field or next pointer field, contains the address of the
next node of the list.

[Link]
• The pointer of the last node contains a null pointer, which is an invalid address (0 or
negative value).
• The linked also contains a list pointer variable called start/first/head which contain the
address of the first node in the list.
• A special case is the list that has no nodes, such a list is called null list or empty list and
is denoted by a null pointer in the variable start/first/head.

[Link]
 Implementation of link list
struct node
{
int data;
struct node *next;
};

[Link]
 Advantage of link list
• Dynamic size and efficient memory usage: Linked lists can easily grow or shrink, allowing for
efficient memory allocation and reduced waste as elements are added or removed.
• Fast insertion and deletion: Operations like inserting or removing elements can be performed
in constant time (O(1)) if the position is known, offering better performance compared to
array-based structures.
• Versatility: Linked lists can be adapted to various types (singly, doubly, circular) and can store
elements of different data types or objects, providing a flexible data structure for a wide range
of applications.

[Link]
 Disadvantage of link list
• Slower access times: Linked lists have a higher time complexity for element access (O(n))
compared to arrays, as elements must be accessed sequentially from the head of the list.
• Memory overhead: Each node in a linked list requires additional memory to store the
reference (or pointer) to the next node, increasing the overall memory usage compared to
array-based structures.
• Pointer manipulation: Implementing linked lists involves managing pointers, which can
increase code complexity and lead to potential issues, such as memory leaks or segmentation
faults, if not handled carefully.

[Link]
 Aspect Array Linked List
Non-contiguous memory
Memory Allocation Contiguous memory locations.
locations.

Dynamic size, can grow or

Size Flexibility Fixed size.
shrink as required.

O(1) for direct access due to O(n) for accessing an element

Access Time indexing. as it requires traversal.

O(n) in worst case as shifting O(1) if the pointer to the node

Insertion/Deletion may be required. is known.

Extra memory for pointers,

More memory efficient for a
Memory Efficiency known size of data. which can be overhead for
[Link] small data sizes.
Q Write a C-style pseudocode for Traversing a link list iteratively, where
pointer head have the address of the first node of the list?
void traverseList(Node* head)
{
Node* current = head;
while (current != NULL)
{
printf("%d -> ", current->data);
current = current->next;
}
printf("NULL\n");
}
[Link]
Q Write a C-style pseudocode for Traversing a link list recursively, where
pointer head have the address of the first node of the list?

void traverseListRecursive(Node* current)

{
if (current == NULL)
{
printf("NULL\n");
return;
}
printf("%d -> ", current->data);
traverseListRecursive(current->next);
}

[Link]
 Header circular link list
• A header singly circular linked list is a variation of a singly circular linked list that includes a
special node, called the header node, at the beginning of the list.

• The header node does not store any actual data; instead, it serves as a fixed reference point
that simplifies some operations on the linked list. The header node's primary purpose is to
eliminate the need for special cases when performing certain operations like inserting or
deleting elements at the beginning or end of the list.

[Link]
 Doubly link list
• A doubly linked list is a data structure in which each node contains a data element and two
pointers, one pointing to the previous node (the ‘previous’ pointer) and the other pointing to
the next node (the ‘next’ pointer) in the sequence.

• This bidirectional linking allows for easier traversal and manipulation of the list in both forward
and backward directions, as well as simplifying some operations such as insertion or deletion
of nodes at any position in the list.

[Link]
Here are some key features of doubly linked lists:
• Each node has two pointers: ‘next’ pointing to the subsequent node and
‘previous’ pointing to the preceding node in the list.
• The first node’s ‘previous’ pointer and the last node’s ‘next’ pointer are set to
‘null’ indicating the beginning and end of the list, respectively.
• Doubly linked lists allow for easier traversal and manipulation in both forward
and backward directions compared to singly linked lists.
• Doubly linked lists consume more memory than singly linked lists due to the
additional ‘previous’ pointer.

[Link]
Q Consider the following function that takes reference to head of a Doubly Linked List as parameter. Assume that a node
of doubly linked list has previous pointer as prev and next pointer as next.
void fun(struct node **head_ref)
{
struct node *temp = NULL;
struct node *current = *head_ref;
while (current != NULL)
{
temp = current->prev;
current->prev = current->next;
current->next = temp;
current = current->prev;
}
if(temp != NULL )
*head_ref = temp->prev;
}
Assume that reference of head of following doubly linked list is passed to above function
1 <--> 2 <--> 3 <--> 4 <--> 5 <-->6.
What should be the modified linked list after the function call?
(A) 2 <--> 1 <--> 4 <--> 3 <--> 6 <-->5
(B) 5 <--> 4 <--> 3 <--> 2 <--> 1 <-->6.
(C) 6 <--> 5 <--> 4 <--> 3 <--> 2 <--> 1.
[Link]
(D) 6 <--> 5 <--> 4 <--> 3 <--> 1 <--> 2
 Polynomial Representation Using Linked List

• In the linked representation of polynomials, each node should consist of three elements,
namely coefficient, exponent and a link to the next term.
• The coefficient field holds the value of the coefficient of a term, the exponent field contains
the exponent value of that term and the link field contains the address of the next term in the
polynomial.

• 3x4 + 8x2 + 6x + 8

[Link]
 Tree
• The tree is one of the most powerful, flexible, versatile and nonlinear advanced data
structures, it represents hierarchical relationship existing between several data items. it is
used in wide range of applications.

[Link]
• A tree is a finite set of one or more data items(nodes) such that
• There is a special data item called root of the tree
• And its remaining data items are partitioned into number of mutually exclusive (disjoint)
subsets, each of which is itself a tree and they are called subtree. i.e. Every node (exclude
a root) is connected by a directed edge from exactly one other node; A direction is: parent
-> children

[Link]
 Root
• The first/Top most node is called as Root Node. We always have exactly one
root node in every tree. We can say that root node is the origin of tree data
structure.

[Link]
 Edge
• In a tree data structure, the connecting link between any two nodes is called
as EDGE. In a tree with 'N' number of nodes there will be exactly of 'N-1' number
of edges.

[Link]
 Parent
• In a tree data structure, the node which is predecessor of any node is called as PARENT
NODE.
• In simple words, the node which has branch from it to any other node is called as
parent node. Parent node can also be defined as "The node which has child / children".

[Link]
 Child
• In a tree data structure, the node which is descendant of any node is called as CHILD Node.

• In simple words, the node which has a link from its parent node is called as child node. In a
tree, any parent node can have any number of child nodes. In a tree, all the nodes except root
are child nodes.

[Link]
 Leaf / External
• In a tree data structure, the node which does not have a child is called as LEAF Node. In simple
words, a leaf is a node with no child.
• In a tree data structure, the leaf nodes are also called as External Nodes. External node is also
a node with no child. In a tree, leaf node is also called as 'Terminal' node.

[Link]
 Internal Nodes
• In a tree data structure, the node which has at least one child is called as INTERNAL Node. In
simple words, an internal node is a node with at least one child.
• In a tree data structure, nodes other than leaf nodes are called as Internal Nodes. The root
node is also said to be Internal Node if the tree has more than one node. Internal nodes are
also called as 'Non-Terminal' nodes.

[Link]
 Degree
• In a tree data structure, the total number of children of a node is called as DEGREE of that
Node. In simple words, the Degree of a node is total number of children it has.
• The highest degree allowed of a node in a tree is called as 'Degree of Tree'

[Link]
 Level / Depth / Height
• In a tree data structure, the root node is said to be at Level 0 and the children of root node are
at Level 1 and the children of the nodes which are at Level 1 will be at Level 2 and so on...
• In simple words, in a tree each step from top to bottom is called as a Level and the Level count
starts with '0' and incremented by one at each level (Step).

[Link]
 Path
• In a tree data structure, the sequence of Nodes and Edges from one node to another node is
called as PATH between that two Nodes. Length of a Path is total number of edge in that
path. In below example the path A - B - E - J has length 4.

[Link]
 Sub Tree
• In a tree data structure, each child from a node forms a subtree recursively.
Every child node will form a subtree on its parent node.

[Link]
 Binary tree
• A binary tree T is defined as a finite set of elements called nodes such that,
• T is empty (null tree)
• T contain a distinguished node R, called the root of T, and the remaining nodes of T form
an ordered pair of disjoint binary tree T1 and T2
• Direct: - A tree T in which any node can have maximum two children (left and right)

struct node {
int data;
struct node* left;
struct node* right;
}

[Link]
 Binary tree representation using array
• Binary tree can be represented using an array
• General representation
• The root is at index ‘1’
• For any given node at position ‘i’
• Left Child is at position 2*i
• Right Child is at position 2*i + 1
• If a node does not have a left or right child, that position in the array remains empty or is filled with a
special value indicating it's vacant (like null or -1)

[Link]
 Linked representation of binary tree

[Link]
[Link]
 Binary tree representation using Linked List
• A binary tree can be efficiently represented using a linked list structure where each node of the tree is
represented by a separate node in the linked list. This linked structure is typically referred to as a
"node-based" representation.

• Each node in the linked list contains the following components:

• Data: The value stored in the node.
• Left Pointer: A pointer pointing to the left child node.
• Right Pointer: A pointer pointing to the right child node.

[Link]
 Traversal of binary tree
• The process of visiting (checking and/or updating) each node in a tree data structure, exactly
once in called tree traversal. Such traversals are classified by the order in which the nodes are
visited.
• Unlike linked lists, one-dimensional arrays and other linear data structures, which are
canonically traversed in linear order, trees may be traversed in multiple ways.
• They may be traversed in depth-first or breadth-first order. There are three common ways to
traverse them in depth-first order: in-order, pre-order and post-order. Beyond these basic
traversals, various more complex or hybrid schemes are possible, such as depth-limited
searches like iterative deepening depth-first search.

[Link]
void inorderTraversal(Node* root)
{
if (root == NULL)
return;
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}

[Link]
void preorderTraversal(Node* root)
{
if (root == NULL)
return;
printf("%d ", root->data);
preorderTraversal(root->left);
preorderTraversal(root->right);
}

[Link]
void postorderTraversal(Node* root)
{
if (root == NULL)
return;
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ", root->data);
}

[Link]
 Binary search tree / Ordered tree / Sorted binary tree
• A binary search tree (BST) is a binary tree in which left subtree of a node contains a key less
than the node’s key and right subtree of a node contains only the nodes with key greater than
the node’s key. Left and right sub tree must each also be a binary search tree.

[Link]
 Searching
• We begin by examining the root node. If the tree is null, the key we are searching for does not exist in
the tree. Otherwise, if the key equals that of the root, the search is successful and we return the node.
• If the key is less than that of the root, we search the left subtree. Similarly, if the key is greater than
that of the root, we search the right subtree.
• This process is repeated until the key is found or the remaining subtree is null. If the searched key is not
found after a null subtree is reached, then the key is not present in the tree.

[Link]
 Insertion
• Insertion begins as a search would begin; if the key is not equal to that of the root, we search
the left or right subtrees as before.
• Eventually, we will reach an external node and add the new key-value pair (here encoded as a
record ‘new Node') as its right or left child, depending on the node's key.
• In other words, we examine the root and recursively insert the new node to the left subtree if
its key is less than that of the root, or the right subtree if its key is greater than or equal to
the root.

[Link]
 Deletion
• Deleting a node with no children: simply remove the node from the tree.
• Deleting a node with one child: remove the node and replace it with its child.
• Deleting a node with two children: call the node to be deleted D. Do not delete D.
• Instead, choose either its in-order predecessor node or its in-order successor node as
replacement node E (s. figure). Copy the user values of E to D.
• If E does not have a child simply remove E from its previous parent G. If E has a child, say F, it
is a right child. Replace E with F at E's parent.

[Link]
 Balance factor
• In a binary tree the balance factor of a node N is defined to be the height
difference Balance Factor(N): = Height (LeftSubtree(N)) – Height
(RightSubtree(N)) of its two child subtrees.

• A binary tree is defined to be an AVL tree if the invariant Balance Factor(N) ∈ {–1,
0, +1} holds for every node N in the tree.

[Link]
 Insertion in an AVL tree
• Insert a node similarly as we do in binary search tree.
• After insertion start checking the balancing factor of each node in a bottom up
fashion that is from newly inserted node towards the root.
• Stop on the first node whose balancing factor is violated and go two steps
towards the newly inserted nodes. watch the movement, which is identified as
the problem.
Problem Solution
LL R
RR L
LR LR
RL RL
[Link]
 Deletion in an AVL tree

AVL
Deletion

L R

L0 L1 L-1 R0 R1 R-1

RR RL RR LL LL LR
[Link]
 Feature/Property Strictly Binary Tree Extended (Full) Binary Tree

Every non-leaf node has exactly

Definition Every node has either 0 or 2 children.
two children.

Nodes with One Child No nodes with only one child. No nodes with only one child.

May have external (dummy) nodes to

Special Nodes None.
make it full.

Used in scenarios like Huffman coding

Less common in practical
Typical Usage trees where it's beneficial to consider
applications.
the tree as full.
[Link]
• Types:
• Single Threaded: Nodes threaded towards either in-order predecessor or
successor.
• Double Threaded: Nodes threaded towards both predecessor and successor.

[Link]
 Graph
• Graph is a data structure that consists of following two components:
• A finite set of vertices also called as nodes.
• A finite set of ordered pair of the form (u, v) called as edge. The pair is ordered
because (u, v) is not same as (v, u) in 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.

[Link]
• Graphs are used to represent many real-life applications: Graphs are used to represent
networks. The networks may include paths in a city or telephone network or circuit network.
• Graphs are also used in social networks like LinkedIn, Facebook. For example, in Facebook,
each person is represented with a vertex (or node). Each node is a structure and contains
information like person id, name, gender and locale.

[Link]
 Representation of Graph in Memory
• Following two are the most commonly used representations of a graph.
• Adjacency Matrix
• Adjacency List

• There are other representations also like, Incidence Matrix and Incidence List.
The choice of the graph representation is situation specific. It totally depends on
the type of operations to be performed and ease of use.

[Link]
• Adjacency Matrix: Adjacency Matrix is a 2D array of size V x V where V is the number of
vertices in a graph. Let the 2D array be adj[][], a slot adj[i][j] = 1 indicates that there is an edge
from vertex i to vertex j.
• Adjacency matrix for undirected graph is always symmetric.
• Adjacency Matrix is also used to represent weighted graphs. If adj[i][j] = w, then there is an
edge from vertex i to vertex j with weight w.

[Link]
• For directed graph

[Link]
 Incidence Matrix
• Representation of undirected graph : Consider a undirected graph G = (V, E) which has n vertices and m edges all
labelled. The incidence matrix I(G) = [bij], is then n x m matrix,
• where bi,j=1 when edge ej is incident with vi
• = 0 otherwise
• Representation of directed graph : The incidence matrix I(D) = [bij] of digraph D with n vertices and m edges is
the n x m matrix in which.
• Bi,j = 1 if arc j is directed away from vertex vi
• =－1 if arc j is directed towards vertex vi
• =0 otherwise.

[Link]
• Pros: Representation is easier to implement and follow. Removing an edge takes
O(1) time. Queries like whether there is an edge from vertex ‘u’ to vertex ‘v’ are
efficient and can be done O(1).

• Cons: Consumes more space O(V2). Even if the graph is sparse(contains less
number of edges), it consumes the same space. Adding a vertex is O(V2) time.

[Link]
• Adjacency List: An array of lists is used. Size of the array is equal to the number of vertices. Let
the array be array[]. An entry array[i] represents the list of vertices adjacent to the ith vertex.
This representation can also be used to represent a weighted graph. The weights of edges can
be represented as lists of pairs.

[Link]
 Graph Traversal
• Traversal means visiting all the nodes of a graph.
• Depth First Traversal (or Search) for a graph is similar to Depth First Traversal of a tree.
• The only catch here is, unlike trees, graphs may contain cycles, so we may come to the same
node again. To avoid processing a node more than once, we use a Boolean visited array.

[Link]
Importance of DFS : DFS is very important algorithm as based upon DFS :
• Testing whether graph is connected.
• Computing a spanning forest of G.
• Computing the connected components of G.
• Computing a path between two vertices of G or reporting that no such
• path exists.
• Computing a cycle in G or reporting that no such cycle exists.

[Link]
Application of DFS : Algorithms that use depth first search as a building block
include :
• Finding connected components.
• Topological sorting.
• Finding 2-(edge or vertex)-connected components.
• Finding 3-(edge or vertex)-connected components.
• Finding the bridges of a graph.
• Generating words in order to plot the limit set of a group.
• Finding strongly connected components.

[Link]
Application of BFS : Breadth first search can be used to solve many problems in graph
theory, for example
• Copying garbage collection.
• Finding the shortest path between two nodes u and v, with path length measured by
number of edges (an advantage over depth first search).
• Ford-Fulkerson method for computing the maximum flow in a flow network.
• Serialization/Deserialization of a binary tree vs serialization in sorted order, allows the
tree to be re-constructed in an efficient manner.
• Construction of the failure function of the Aho-Corasick pattern matcher.
• Testing bipartiteness of a graph.

[Link]
 Introduction to hashing
• Main idea of data structure is to help us store the data. But Most common
operation on any data structure is not insert or delete but actually search, as
even for insertion and deletion search is also required.
• In any of the data structure the search time first depends on the number of
elements which data structure contains and then on type of structure. for e.g.
• Unsorted array – O(n)
• sorted array – O(logn)
• link list – O(n)
• BT – O(n)
• BST – O(n)
• AVL – O(logn)

[Link]
• So hashing is a technique where search time is independent of the number of items in which
we are searching a data value.
• The basic idea is to use the key itself to find the address in the memory to make searching
easy. For e.g. to use phone number, roll no, Aadhar card, voter id or any other key and convert
it into a smaller practical number (but it must be modified so a great deal of space is not
wasted) and uses the small number as index in a table called hash table.
• The values are then stored in hash table, By using that key you can access the element
in O(1) time.

[Link]
• This conversion called hash function which is from the set of K keys into the set
of memory location L.
• H: KàL
• In simple terms, a hash function maps a big number or string to a small integer
that can be used as index in hash table. An array that stores pointers to records
corresponding to our search key. The remaining entries can be nil.

[Link]
• Collision: - It is possible that two different set of keys K1 and K2 will
yield the same hash address. This situation is called collision. The
technique to resolve collision is called collision resolution.

[Link]
• Characteristics of good hash function
• Easy to compute and understand
• Efficiently computable- It must take less time to compute
• Should uniformly distribute the keys (Each table position equally
likely for each key) and should not result in clustering.
• Must have low collision rate

[Link]
 Most popular hash function
• Division-remainder method: The size of the number of items in the table is
estimated. That number is then used as a divisor into each original value or key
to extract a quotient and a remainder.
• The remainder is the hashed value. (Since this method is liable to produce a
number of collisions, any search mechanism would have to be able to recognize
a collision and offer an alternate search mechanism.)
• H(K) = K(mod m)
• H(K) = K(mod m) + 1

[Link]
 Mid-Square Method
• The mid-square method is a technique used to generate hash codes by squaring
the key and then extracting a portion of the resulting number. This method was
popular for hash function design in early hashing techniques but has been
superseded by more robust methods in modern systems.
• Square the Key: Take the key, square it (e.g., key 123 gives 15129).
• Middle Extraction: Extract middle digits from the squared result (e.g., from
15129, take 512).
• Fit to Table: Optionally, use modulus to fit the hash within table size.

[Link]
 Folding Method
• The folding method is a technique used in hashing to partition the key into several parts, then
combine these parts to determine the hash code.
• Here's how the folding method works:
• Partition the Key: Divide the key into equal-sized parts. For example, for a key 123456789
and partition size of 3, you'd have 123, 456, and 789.
• Add the Partitions: Sum these parts together. Continuing the example, 123 + 456 + 789 =
1368.
• Modulus Operation: If the resulting sum is larger than the hash table size, a modulus
operation will bring it within range. For instance, if the hash table has 1000 slots, 1368 %
1000 = 368 would be the final hash code.

[Link]
• Advantages:
• It distributes keys that are close in value across the hash table.
• Simple and intuitive.

• Disadvantages:
• Not as efficient for keys with certain patterns.
• Might still lead to collisions if the table size isn't chosen wisely.
• Like other simple hashing techniques, the folding method's usage has been largely
superseded by more advanced hash functions in modern systems. However, it remains a
basic technique useful for understanding foundational hashing concepts.

[Link]
 Collision Resolution Technique
• Open Addressing/closed hashing - In Open Addressing, all elements are stored in the hash
table itself. i.e. collision is resolved by probing or searching through alternate locations in the
Hash table itself in a particular sequence.

• When searching for an element, we one by one examine table slots until the desired element
is found or it is clear that the element is not in the table. So, at any point, size of table must be
greater than or equal to total number of keys.

• It is of three types linear probing, quadratic probing, double hashing

[Link]
 Linear probing
• Linear probing is a method used in open addressing hashing. When a collision occurs, it
searches the table sequentially from the hashed position to find an empty or matching slot.

• Key Points:
• Uses a random hash function, ensuring constant expected time for operations.
• Achieves O(1) time for insert, remove, and search if the load factor is kept below one.

• Insert(k): Probe until an empty slot is found, then insert k.

• Search(k): Probe until a matching key or empty slot is found.
• Delete(k): Mark slots of deleted keys as “deleted”. Inserts can use these slots, but searches
don’t stop at them.

[Link]
 Linear Probing
• In linear probing method, in case of a collision we find out the next free space and store the
key that is causing collision in it.
• The method of linear probing uses the hash function
h(k, i) = (h’(k) + i) mod m;
for i = 0, 1, … ,m - 1.

[Link]
• Advantage:
• Linear probing is fast, simple, and easy to implement, making it a popular
choice on standard hardware.
• It offers high performance due to its excellent locality of reference.

• Disadvantage:
• It's sensitive to the quality of its hash function compared to other schemes.
• Performance drops faster at high load factors due to primary clustering,
leading to more nearby collisions and longer operation times.
• Requires a superior hash function for optimal performance than some other
methods.

[Link]
• Primary Clustering: In open-addressing hash tables, especially with linear
probing, collisions result in records being placed in the next available hash table
cell. This creates a contiguous cluster of occupied cells. When another record
hashes to any part of this cluster, the cluster size increases by one.

• Secondary Clustering: This occurs in open addressing modes, including linear

and quadratic probing, where the probe sequence doesn't depend on the key. A
subpar hash function can make many keys hash to the same spot.
Consequently, these keys either follow the same probe sequence or land in the
same hash chain, leading to slower access times.

[Link]
 Quadratic Probing
• Quadratic probing operates by taking the original hash index and adding successive
values of an arbitrary quadratic polynomial until an open slot is found.

• Quadratic probing uses a hash function of the form

h (k, i) = (h’(k) + f (i2)) mod m
Where, h’ is an auxiliary hash function and i = 0, 1, …, m - 1.

[Link]
Example: Consider the key values 8, 3, 13, 23 and the hash table size is 10.
• 8 will be placed at: h (8) = [h (8) + f (02)] mod 10 = 8, so it gets placed at
location 8.
• 3 will be placed at: h (3) = [h (3) + f (02)] mod 10 = 3, no collision, so it gets
placed at location 3
• 13 will be placed at: h (13) = [h (13) + f (02)] mod 10 = 3, collision occurred, so
we increase the value of i.
• h (13) = [h (13) + f (12)] mod 10 = 4, no collision, so it gets placed at
location 4.
• 23 will be placed at: h (23) = [h (23) + f (02)] mod 10 = 3, collision occurred, so
we increase the value of i.
• h (23) = [h (23) + f (12)] mod 10 = 4, again collision occurred, so we
increase the value of i.
• h (23) = [h (23) + f (22)] mod 10 = 3 + 4 = 7, no collision occurred, so it gets
placed at location 7.
• Quadratic probing avoids clustering of elements and thus improves the
searching time.
[Link]
• Advantage
• Quadratic probing can be a more efficient algorithm in a closed hashing table, since it
better avoids the clustering problem that can occur with linear probing, although it is not
immune.
• It also provides good memory caching because it preserves some locality of reference;
however, linear probing has greater locality and, thus, better cache performance.

• Disadvantage
• Quadratic probing lies between the two in terms of cache performance and clustering.

[Link]
• Performance of Open Addressing: Like Chaining, performance of hashing can be
evaluated under the assumption that each key is equally likely to be hashed to
any slot of table (simple uniform hashing)
• m = Number of slots in hash table
• n = Number of keys to be inserted in hash table
• Load factor α = n/m (< 1)
• Expected time to search/insert/delete < 1/(1 - α)
• So Search, Insert and Delete take (1/(1 - α)) time

[Link]
 Chaining
• The idea is to make each cell of hash table point to a linked list of records that
have same hash function value. In chaining, we place all the elements that hash
to the same slot into the same linked list.

[Link]
• Advantage: - Chaining is simple

• Disadvantage: -but requires additional memory outside the table.

[Link]
[Link]. Separate Chaining Open Addressing
1. Chaining is Simpler to implement. Open Addressing requires more computation.

2. In chaining, Hash table never fills up, we can always In open addressing, table may become full.
add more elements to chain.

3. Chaining is Less sensitive to the hash function or Open addressing requires extra care for to avoid
load factors. clustering and load factor.

4. Chaining is mostly used when it is unknown how Open addressing is used when the frequency and
many and how frequently keys may be inserted or number of keys is known.
deleted.
5. Cache performance of chaining is not good as keys Open addressing provides better cache performance as
are stored using linked list. everything is stored in the same table.

6. Wastage of Space (Some Parts of hash table in In Open addressing, a slot can be used even if an input
chaining are never used). doesn’t map to it.

7. [Link]
Chaining uses extra space for links. No links in Open addressing
 Double Hashing
• Double hashing is used in hash tables to handle hash collisions using open addressing. It uses
two hash values: the primary for table indexing and the secondary to set an interval for
searching. This method differs from linear and quadratic probing. With double hashing, data
mapped to the same location has varied bucket sequences, reducing repeated collisions.
• Given two random, uniform, and independent hash functions h1 and h2, the ith location
in the bucket sequence for value k in a hash table of |T| buckets is: h(i, k) = (h1 (k) + i •
h2(k)) mod |T|. Generally, h1 and h2 are selected from a set of universal hash
functions; h1 is selected to have a range of {0, IT| - 1} and h2 to have a range of {1, IT|
- 1}. Double hashing approximates a random distribution; more precisely, pair-wise
independent hash functions yield a probability of (n/|TI)2 that any pair of keys will
follow the same bucket sequence

[Link]