Unit-1

Introduction to Data Structures

Introduction to Data Structures : Basic Terminology, Classification of Data Structures, Operation
on Data Structures, abstract data types, selecting a Data Structure,
Linear list – Introduction, singly linked list, Circular Linked Lists, Doubly Linked List,
Stacks- Operations, Stack algorithm, Stack ADT, Stack applications,
Queues- operations, Queue Algorithm, Queue ADT, Queue Applications.

Introduction:
• A data structure is a way of storing and organizing data in the computer memory so that
it can be processed efficiently.
• In the field of computing, we have formulated many ways to handle data efficiently.
• For storing the data we use variables.

Variable:
• Variable is basically nothing but the name of a memory location that we use for storing
data.
• We can change the value of a variable in C or any other language, and we can also reuse
it multiple times.
• We use symbols in variables for representing the memory location- so that it becomes
easily identifiable by any user.

Variable Definition in C:
• The variable definition in C language tells the compiler about how much storage it should
be creating for the given variable and where it should create the storage. Basically, the
variable definition helps in specifying the data type. It contains a list of one variable or
multiple ones as follows:
Syntax : data_type variable; (or)
data_type variable_list;

CSE(AI&ML) 1
Variable Initialization in C:
• We can initialize the variables in their declaration (assigned an initial value). The initializer
of a variable may contain an equal sign- that gets followed by a constant expression. It
goes like this:
Syntax : data_type variable_name = value;

• For storing the data we use variables, but those are not feasible when handling a huge
amount of data.
• If we want to access the information such as student name, roll no, section, gender,
address etc, with a single variable it is unfeasible task to store such a large amount of
related data. Thus, the concept of data structure is introduced.
• Arrays are considered as good example for implementing simple data structure.

Arrays:
• Array is one of the most used data structures in C programming. It is a simple and fast
way of storing multiple values under a single name.
• An array is a fixed-size collection of similar data items stored in contiguous memory
locations. It can be used to store the collection of different data types such as int, char,
float, etc.,

Array Declaration in C:
• We have to declare the array like any other variable before using it.
• We can declare an array by specifying its name, the type of its elements, and the size of
its dimensions(mentioned in square brackets [ ]).
• When we declare an array, the compiler allocates the memory block of the specified size
to the array name.
Syntax :
data_type array_name [size];
(or)
data_type array_name [size1] [size2]...[sizeN];

CSE(AI&ML) 2
 • The C arrays are static in nature, i.e., they are allocated memory at the compile time.
• To access an array element, refer to its index number.
• Array indexes start with 0: [0] is the first element. [1] is the second element, etc.

Array Initialization in C:
• Initialization is the process to assign some initial value to the variable. When the array is
declared or allocated memory, the elements of the array contain some garbage value. So,
we need to initialize the array to some meaningful value.
Syntax:
data_type array_name [size] = {value1, value2, ... valueN};

• Element: Each item stored in an array is called an element.

• Index: Each location of an element in an array has a numerical index, which is used to
identify the element.

Basic operations:
• Traverse: Print all the array elements one by one.
• Insertion: Insert an element at the given index.
• Delete: Deletes an element at the given index.
• Search: Searches an element using the given index or by the value.
• Update: Updates an element at the given index.

Array ADT:
• We can perform more operations on the array data structure
Display () – To Display the entire array on the screen.
Add(n) / Append(n) – To add a particular element on the end of the array.
Insert (index, n) – To add an element to a particular index.
Delete (index) – To delete an element with the help of an index in the given array.

CSE(AI&ML) 3
Search (n) – To check whether the given element is present or not in an array.
Get (index) – It will return the element which presents on the given index.
Set (index, x) – It will change the element with the new element at a particular index.
Max () / Min () – These will return the max and min element in the given array.
Reverse () – It will reverse the order of elements in the given array.
Shift () – It will shift the whole elements either on the left or right side by the given number.

Disadvantages of Arrays:
• An array has a fixed size which means you cannot add/delete elements after creation. You
also cannot resize them dynamically.
• When inserting into an array, the insertion process requires moving each element from
its original location to the next available slot. The shift cost increases linearly with the
length of the array.
• Deleting an item from an array involves copying every preceding element to fill up the
gap left behind by the deleted element. Deleting items from an array is very expensive
because of this reason.
• Another disadvantage of arrays is that they don't support random access. If you want to
get some particular record from an array, you must know its exact index.
• Arrays have limited functionality compared to other data structures. They are good only
for simple tasks.

Why we need dynamic data structure?

• Dynamic data structure such as linked lists which are based on dynamic memory
management techniques, remove these limitations of static array based data structure.
• They provide the flexibility in adding, deleting, or rearranging data items at run time.
• With arrays there will always restriction to the maximum [Link] elements that can be
accommodated into the list, but with linked lists there is no such concern.
• The use of dynamic memory management techniques by linked list allows it to allocate
additional memory space or to release unwanted space at run time, thus optimizing the
use of storage space.

CSE(AI&ML) 4
Categories of Data structure:
• The data structure can be divided into 2 major types:
i)Linear data structure
ii)Non-linear data structure
i) Linear data structure:
A data structure is said to be linear, if its elements combine to form any specific order.
• There are basically two techniques of representing such linear data structure within
memory.
• First way is to provide the linear relationships among all the elements represented by
means of linear memory location. These linear structures are termed as “Arrays”.
• Second way is to provide the linear relationships among all the elements represented by
using the concept of ponters or links. These linear structures are termed as “Linked lists”.
• The common examples of linear data structure are: Arrays, Linked lists, Stacks, Queues
ii) Non-Linear data structure:
This structure is mostly used for representing data that contains a hierarchical
relationship among various elements.
• Examples of non-linear data structures are: Graphs, Trees, Hash tables.

Abstract data type (ADT):

• Abstract Data type (ADT) is a type (or class) for objects whose behavior is defined by a set
of values and a set of operations.
• The definition of ADT only mentions what operations are to be performed but not how
these operations will be implemented.
• It does not specify how data will be organized in memory and what algorithms will be
used for implementing the operations. It is called “abstract” because it gives an
implementation-independent view.
• The process of providing only the essentials and hiding the details is known as
abstraction.

CSE(AI&ML) 5
Dynamic Memory Allocation in C:
• In C language, the process of allocating memory at runtime is known as dynamic memory
allocation.
• Library functions known as memory management functions are used for assigning
(allocating) and freeing memory, during execution of a program.
• These functions are defined in the stdlib.h header file.
• These functions allocate memory from a memory area known as heap and when the
memory is not in use, it is freed to be used for some other purpose. We access the
dynamically allocated memory using pointers.

Difference between Static and Dynamic Memory Allocation:

Static Memory Allocation Dynamic Memory Allocation
1) Allocation is done before execution of the 1) Allocation is done during execution of the
program(at compile time). program(at runtime).
2) Here, variables are allocated memory 2) Here, memory is allocated only when the
permanently. program is active.
3) It uses stack for managing memory allocation. 3) It uses heap for managing memory allocation.
4) We can reuse the memory and free it after
4) We cannot reuse the memory.
usage.
5) Execution is faster than dynamic memory 5) Execution is slower than static memory
allocation. allocation.
6) It is less efficient. 6) It is more efficient.
7) It is simple to use. 7) It can be complicated to use.

CSE(AI&ML) 6
Memory Allocation Process:
• Global variables, static variables and Program instructions get their memory in
Permanent storage area, whereas local variables are stored in memory are called Stack.
• The memory space between these two region is known as Heap area. This region is used
for dynamic memory allocation during execution of the program. The size of heap keeps
changing.

Memory allocation functions:

• malloc(): allocates requested size of bytes and returns a void pointer pointing to the first
byte of the allocated space.
• calloc(): allocates space for an array of elements, initialize them to zero and then returns
a void pointer to the memory.
• free(): releases previously allocated memory.
• realloc(): modify the size of previously allocated space

Allocating block of Memory : malloc()

• malloc() function is used for allocating block of memory at runtime. This function reserves
a block of memory of the given size and returns a pointer of type void. This means that
we can assign it to any type of pointer using typecasting. If it fails to allocate enough space
as specified, it returns a NULL pointer.
Syntax: ptr=(data_type*)malloc(byte_size);
Ex: x=(int *)malloc(100);
c=(char *)malloc(50);
• We may also use a malloc() function to allocate space for complex data type such as
structures.
Ex: st-var=(struct store*)malloc(sizeof(struct store));

CSE(AI&ML) 7
Allocating multiple blocks of Memory : calloc()
• calloc() is another memory allocation function that is used for allocating memory at
runtime.
• calloc() function is normally used for allocating memory to derived data types such as
arrays and structures.
• If it fails to allocate enough space as specified, it returns a NULL pointer.
• While malloc allocates a single block of storage space, calloc allocates multiple blocks of
storage space, each of the same size, and then sets all bytes to zero.
Syntax: ptr=(data_type *)calloc(n,elem-size);
Ex: x=(int *)calloc(5,100);

Releasing the used space : free()

• With the dynamic run time allocation, it is our responsibility to release that memory
when it is not required so that it can be used for other purposes.
• The release of storage space becomes important when the storage is limited. We may
release the blocks of memory using free() function.
Syntax: void free(void *p);
Ex: int *x;
x = (int*)malloc(50 * sizeof(int));
free(x);

Altering the size of the block : realloc()

• The realloc() function is used to change the memory size that is already allocated
dynamically to a variable.
• If we want to change the size of memory allocated by malloc() or calloc() function, we
use realloc() function. Without losing the old data, it changes the size of the memory
block.
• The first argument of this function is a pointer pointing to the block of memory we
allocated before and the second argument is the updated size of the memory block. On
failure, it returns NULL.
• If the new size(of memory required) is larger than the old size, it retains the data and
newly allocated bytes are uninitialized. It might move the old data to a new block of
memory with increased size if there's not enough space at the old address.
Syntax: ptr=malloc(size);
ptr=realloc(ptr, new-size);
Ex: x=malloc(50);
x=realloc(x,100);

CSE(AI&ML) 8
Linear Lists:
• We know that a list refers to a set of items organized sequentially.
• An array is an example of List.
• In an array sequential organization is provided implicitly by its index. We use the index for
accessing and manipulation of array elements.
• A completely different way to represent a list is to make each item in the list part of a
structure that also contains a link to the structure containing the next item.
• This type of list is called a “Linked list” because it is a list whose order is given by links
from one item to the next.

Linked List:
Definition : A linked list is a sequence of data structures which are connected together via links.

• Linked list is a sequence of lists which contains items.

• Each list contains a connection to another list.
• Linked list is the second most-used structure after array.

• Each structure of the list is called a “node”. It consists of two fields

i) item
ii) address of next item
• The link is in the form of a pointer to another structure of the same type. Such a structure
is represented as follows:
struct node
{
int item;
struct node *next;
};

Self-referential structure:

CSE(AI&ML) 9
 • The structure which contain a member field that points to the same structure type are
called “ Self referential structure”.
• A node may be represented in general form as follows:
struct tag-name
{
type member1;
type member2;
-------
struct tag-name *next;
};
The structure may contain more than one item with different data types. However, one
of the items be a pointer of the tag-name.

Linked list Process:

Let us consider a simple example to illustrate the concept of linking.
Suppose we define a structure as follows:
struct linked-list
{
float age;
struct linked-list*next;
};

Let us assume that the list contains two nodes node1 and node2. They are of the type
struct linked-list and are defined as follows :
struct linked-list node1, node2;
This statement creates space for two nodes, each containing two empty fields as shown:

The next pointer of node1 can be made to point to node2 by the statement:
[Link]=&node2;

CSE(AI&ML) 10
 This statement stores the address of node2 into the field [Link] and thus establishes
a ‘link’ between node1 & node2.
200 is the address of node2, where the value of the variable [Link] will be stored.
Now, Let us assign values to the field of age :
[Link]=35.50;
[Link]=40.00;
The result is as follows:

No list goes on forever. Every list must have an end. We must therefore indicate the end
of a linked list. This is necessary for processing the list.
C has a special pointer called “NULL” that can be stored in the ‘next’ field of the last node.
In our two node list, the end of the list is marked as follows :
[Link]=NULL; (or) [Link]=0;

Linked List Operations:

• Since a linked list is an example of an ADT, we must define the associated functions that
are require to manipulate the linked list structure.
• The typical operations performed on a linked list are :
1) Insertion
2) Deletion
3) Searching
4) Printing
[Link]:
• It involves adding an element into the linked list and resetting the link pointer wherever
required.
• Inserting an element into a list has three possibilities:
a) Insertion at the beginning of the list.
b) Insertion at the end of the list.
c) Insertion at particular position of the list.
a) Insertion at the beginning:
• Insert a new node at beginning of the linked list.

CSE(AI&ML) 11
CSE(AI&ML) 12
b) Insertion at the ending:
• Insert a new node at ending of the linked list.

CSE(AI&ML) 13
c) Insertion at particular position:
• Insert a new node at particular position of the linked list.

CSE(AI&ML) 14
[Link]:
• It involves removing an element from the linked list and resetting the link pointer
wherever required.
• Inserting an element from a list has three possibilities:
a) Deletion from the beginning of the list.
b) Deletion from the end of the list.
c) Deletion at particular position from the list.
a) Deletion from the beginning:
• Deletion of a node from the beginning of the linked list.

[Link]=NULL;

free(A);

CSE(AI&ML) 15
b) Deletion from the ending:
• Deletion of a node from the ending of the linked list.

[Link]=NULL;

free(C);

c) Deletion at particular position:

• Deletion of a node at particular position of the linked list.

• Delete ‘20’
• [Link]=[Link];

[Link]=NULL;

CSE(AI&ML) 16
 free(B);

• 3) Searching : It involves traversing the linked list to find a specific element. The pointers
between elements help in traversing the linked list from starting to till end.
• 4) Printing : It involves displaying all the linked list elements on the console(screen). The
pointers between elements help in traversing the linked list from starting to till end.

Linked list with header:

• There is another type of linked list which contains a special node present at the beginning
of the list called header node.
• It is exactly similar to any other node in the list with the exception that its data field is
empty.
• The link field of the header node points to the first element in the list, and if there are no
elements then it points to null.
• The start pointer however always points to the header node.
• Thus, the first node in such linked lists is always the one being pointed by start or head
node.
• The objective of implementing a header linked list is to segregate the actual list elements
and have a separate pointer mechanism for tracking the beginning of the list.

CSE(AI&ML) 17
Types of Linked Lists:
• There are different types of linked lists are there.
1) Single linked list / Singly linked list
2) Double linked list / Doubly linked list
3) Circular linked list
a) Circular single linked list
b) Circular double linked list

1) Single Linked List:

2) Double Linked List:

CSE(AI&ML) 18
3) Circular Linked List:
a) Circular Single Linked List :

b) Circular Double Linked List :

Advantages of linked List:

• Dynamic data structure: A linked list is a dynamic arrangement so it can grow and shrink
at runtime by allocating and deallocating memory. So there is no need to give the initial
size of the linked list.

CSE(AI&ML) 19
 • No memory wastage: In the Linked list, efficient memory utilization can be achieved since
the size of the linked list increase or decrease at run time so there is no memory wastage
and there is no need to pre-allocate the memory.
• Implementation: Linear data structures like stacks and queues are often easily
implemented using a linked list.
• Insertion and Deletion Operations: Insertion and deletion operations are quite easier in
the linked list. There is no need to shift elements after the insertion or deletion of an
element only the address present in the next pointer needs to be updated.
• Flexible: This is because the elements in Linked List are not stored in contiguous memory
locations unlike the array.
• Efficient for large data: When working with large datasets linked lists play a crucial role
as it can grow and shrink dynamically.
• Scalability: Contains the ability to add or remove elements at any position.

Disadvantages of linked list:

• Memory usage: More memory is required in the linked list as compared to an array.
Because in a linked list, a pointer is also required to store the address of the next element
and it requires extra memory for itself.
• Traversal: In a linked list traversal is more time-consuming as compared to an array.
Direct access to an element is not possible in a linked list as in an array by index. For
example, for accessing a node at position n, one has to traverse all the nodes before it.
• Reverse Traversing: In a singly linked list reverse traversing is not possible, but in the case
of a doubly-linked list, it can be possible as it contains a pointer to the previously
connected nodes with each node. For performing this extra memory is required for the
back pointer hence, there is a wastage of memory.
• Random Access: Random access is not possible in a linked list due to its dynamic memory
allocation.
• Lower efficiency at times: For certain operations, such as searching for an element or
iterating through the list, can be slower in a linked list.
• Complex implementation: The linked list implementation is more complex when
compared to array. It requires a complex programming understanding.
• Difficult to share data: This is because it is not possible to directly access the memory
address of an element in a linked list.
• Not suited for small dataset: Cannot provide any significant benefits on small dataset
compare to that of an array.

CSE(AI&ML) 20
List ADT:
• The List ADT Functions is given below:
get() – Return an element from the list at any given position.
insert() – Insert an element at any position of the list.
remove() – Remove the first occurrence of any element from a non-empty list.
removeAt() – Remove the element at a specified location from a non-empty list.
replace() – Replace an element at any position by another element.
size() – Return the number of elements in the list.
isEmpty() – Return true if the list is empty, otherwise return false.
isFull() – Return true if the list is full, otherwise return false.

CSE(AI&ML) 21
Stack:
• A stack is a linear data structure in which a data item is inserted and deleted at one end.
• Stack follows LIFO (Last In First Out) or FILO (First In Last Out) principle.
• LIFO implies that the element that is inserted last, comes out first and FILO implies that
the element that is inserted first, comes out last.
Ex: Pile of books, newspapers, bangles etc…

Stack Operations:
• There are some basic operations that can be performed on stacks. They are
a) push() e) isEmpty()
b) pop() f) isFull()
c) peek() g) size()
d) display()
• a) push() : Inserting / Writing a value into the stack.
• b) pop() : Deleting / Reading a value from the stack.
• c) peek() : Displaying the top most element from the stack.
• d) display() : Displaying all the elements from the stack.
• e) isEmpty() : Check whether the stack is empty or not. It returns true if the stack is empty.
Otherwise, it returns false.
• f) isFull() : Check whether the stack is full or not. It returns true if the stack is full.
Otherwise, it returns false.
• g) size(): This operation returns the size of the queue i.e. the total number of elements it
contains.

Stack ADT:
• push() – Insert an element at one end of the stack called top.
• pop() – Remove and return the element at the top of the stack, if it is not empty.
• peek() – Return the element at the top of the stack without removing it, if the stack is not
empty.
• size() – Return the number of elements in the stack.

CSE(AI&ML) 22
 • isEmpty() – Return true if the stack is empty, otherwise return false.
• isFull() – Return true if the stack is full, otherwise return false.
• size(): This operation returns the size of the queue i.e. the total number of elements it
contains.

Example:
• Initially stack is empty.

Stack implementation:
• Implementation of the push operation checks if there is still any room left in the stack, if
there is any, it increments the stack counter by one and adds the received item at the top
of the stack.
• Implementation of pop operation checks whether or not the stack is already empty, if it
is not, it returns the top element of the stack and decrements the stack counter by one.
• We can implement the stack by using two ways:
a) Implementation of stack using arrays.
b) Implementation of stack using linked lists.
• Both types of implementations have their own usage in specific situations.
a) Implementation of stack using arrays:
• The implementation of stacks using arrays involves allocating a fixed size array in the
memory. Both stack operations are made on this array with a constant check being
made to ensure that the array doesn’t go out of bounds.
• Basic operations :
a) push()
b) pop()
c) peek()
d) display()

a) push()
• The push operation involves checking whether or not the stack pointer is pointing to the
upper bound of the array. If it is not the new item is pushed(inserted) into the stack.

CSE(AI&ML) 23
 • It means check whether the stack is full or not,
if the stack is not full, increment the stack counter by one and insert the new item into the stack,
if the stack is full, the new item is not possible to insert into the stack, then that situation we call
it as Stack Overflow

Sample code:
#define SIZE 5
int stack[SIZE];
int top=-1;
if(top==SIZE-1)
printf(“Stack is full”);
else
{
top=top+1;
printf(“Enter an element:”);
scanf(“%d”,&ele);
stack[top]=ele;
}

b) pop()
• The pop operation involves checking whether or not the stack is already empty, if it is not,
it returns the top element of the stack, decrements the stack counter by one.
• It means check whether the stack is empty or not,
if the stack is not empty, delete the top element from the stack and decrement the stack counter
by one,
if the stack is empty, it is not possible to delete an element from the stack, then that situation
we call it as Stack Underflow
Sample code:
#define SIZE 5
int stack[SIZE];
int top=-1;
if(top==-1)
printf(“Stack is empty”);
else
{
printf(“Deleted element is: %d”,stack[top]);
top=top-1;
}

CSE(AI&ML) 24
c) peek():
Sample code :
if(top==-1)
printf(“Stack is empty”);
else
printf(“Top most element is : %d”, stack[top]);

d) display():
Sample code :
if(top==-1)
printf(“Stack is empty”);
else
{
for(i=top;i>=0;i--)
printf(“%d\t”, stack[i]);
}

b) Implementation of stack using linked list:

• The implementation of stacks using linked list involves dynamically allocating memory
space at run time while performing stack operations.
• Since, the allocation of memory space is dynamic, the stack consumes only that much
amount of space is required for holding its elements.
• This is contrary to array-based stacks which occupy a fixed memory space even if there
are no elements present.
• Basic operations :
a) push()
b) pop()
c) peek()
d) display()

a) push():
• The push operation under linked list implementation of stack involves the following tasks:
a) Reserve memory space of the size of a stack element in memory.
b) Store the pushed(inserted) element at the new location.
c) Link the new element with existing stack.
d) Update the stack pointer.

CSE(AI&ML) 25
Sample code:
struct node
{
int data;
struct node *next;
} *new,*tos,*temp;
new=(struct node*)malloc(sizeof(struct node));
printf(“Enter a value:”);
scanf(“%d”,&value);
new->data=value;
new->next=NULL;
if(tos==NULL)
tos=new;
else
{
new->next=tos;
tos=new;
}

b) pop():
To delete the elements from the stack.
Sample code:
temp=tos;
printf(“Deleted item is:%d”,tos->data);
tos=tos->next;
temp->next=NULL;
free(temp);

c) peek():
To display the top most element from the stack.
Sample code:
if(tos==NULL)
printf(“Stack is empty”);
else
printf(“Top most element is:%d”,tos->data);

d) display():
To display all the elements in the stack.

CSE(AI&ML) 26
Sample code:
temp=tos;
if(tos==NULL)
printf(“Stack is empty”);
else
{
while(temp!=NULL)
{
printf(“%d->”,temp->data);
temp=temp->next;
}
}

Advantages of Stack:
• Easy implementation: Stack data structure is easy to implement using arrays or linked
lists, and its operations are simple to understand and implement.
• Efficient memory utilization: Stack uses a contiguous block of memory, making it more
efficient in memory utilization as compared to other data structures.
• Fast access time: Stack data structure provides fast access time for adding and removing
elements as the elements are added and removed from the top of the stack.
• Helps in function calls: Stack data structure is used to store function calls and their states,
which helps in the efficient implementation of recursive function calls.
• Supports backtracking: Stack data structure supports backtracking algorithms, which are
used in problem-solving to explore all possible solutions by storing the previous states.
• Used in Compiler Design: Stack data structure is used in compiler design for parsing and
syntax analysis of programming languages.
• Enables undo/redo operations: Stack data structure is used to enable undo and redo
operations in various applications like text editors, graphic design tools, and software
development environments.

Disadvantages of Stack:
• Limited capacity: Stack data structure has a limited capacity as it can only hold a fixed
number of elements. If the stack becomes full, adding new elements may result in stack
overflow, leading to the loss of data.
• No random access: Stack data structure does not allow for random access to its elements,
and it only allows for adding and removing elements from the top of the stack. To access
an element in the middle of the stack, all the elements above it must be removed.

CSE(AI&ML) 27
 • Memory management: Stack data structure uses a contiguous block of memory, which
can result in memory fragmentation if elements are added and removed frequently.
• Not suitable for certain applications: Stack data structure is not suitable for applications
that require accessing elements in the middle of the stack, like searching or sorting
algorithms.
• Stack overflow and underflow: Stack data structure can result in stack overflow if too
many elements are pushed onto the stack, and it can result in stack underflow if too many
elements are popped from the stack.
• Recursive function calls limitations: While stack data structure supports recursive
function calls, too many recursive function calls can lead to stack overflow, resulting in
the termination of the program.

Applications of stack:
• A Stack can be used for evaluating expressions consisting of operands and operators.
• Stacks can be used for Backtracking, i.e., to check parenthesis matching in an expression.
• It can also be used to convert one form of expression to another form.
• It can be used for systematic Memory Management.

• Evaluation of Arithmetic Expression requires two steps:

a) First, convert the given expression into special notation.
b) Evaluate the expression in this new notation.
• Notations for Arithmetic Expression
There are three notations to represent an arithmetic expression:
a) Infix Notation
b) Prefix Notation
c) Postfix Notation

Infix Notation
The infix notation is a convenient way of writing an expression in which each operator is
placed between the operands. Infix expressions can be parenthesized or unparenthesized
depending upon the problem requirement.
Example: A + B, (C - D) etc.
• All these expressions are in infix notation because the operator comes between the
operands.

Prefix Notation
The prefix notation places the operator before the operands. This notation was
introduced by the Polish mathematician and hence often referred to as polish notation.

CSE(AI&ML) 28
Example: + A B, -CD etc.
• All these expressions are in prefix notation because the operator comes before the
operands.

Postfix Notation
The postfix notation places the operator after the operands. This notation is just the
reverse of Polish notation and also known as Reverse Polish notation.
Example: AB +, CD+, etc.
• All these expressions are in postfix notation because the operator comes after the
operands.

Conversion from Infix to Prefix:

Infix to prefix algorithm:
1) Create an empty stack and an empty output string.
2) Reverse the infix expression: Reverse the order of all elements in the infix expression,
including operands and operators.
3) Iterate through the reversed infix expression from left to right.
4) If the current character is an operand (number or variable), append it to the output string.
5) If the current character is a closing bracket ‘)’, push it onto the stack.
6) If the current character is an operator or an opening bracket ‘(‘, compare its precedence
with the precedence of the operator at the top of the stack.
7) If the current operator has higher precedence than the operator at the top of the stack
or the stack is empty, push the current operator onto the stack.
8) If the current operator has lower or equal precedence than the operator at the top of the
stack, pop the operators from the stack and append them to the output string until an
operator with lower precedence is encountered or the stack becomes empty. Then push
the current operator onto the stack.
9) If the current character is an opening bracket ‘(‘, pop the operators from the stack and
append them to the output string until the corresponding closing bracket ‘)’ is
encountered. Discard the closing bracket.
10) Repeat steps 4 to 9 until all characters in the reversed infix expression have been
processed.
11) Pop the remaining operators from the stack and append them to the output string.
12) Reverse the output string to obtain the prefix expression.

Example : Convert the given infix expression A*B-C/D+E to its equivalent prefix expression.

CSE(AI&ML) 29
Evaluation of Prefix Expression:
Evaluation of prefix expression algorithm:
1) Reverse the given prefix expression, and iterate through the reversed prefix expression
from left to right.
(or)
Start from the last element of the given prefix expression.
2) Check the current element.
a) if it is an operand, push it to the stack.
b) if it is an operator, pop top two operands from the stack. Perform the operation and
push the elements back to the stack.
3) Do this till all the elements of the expression are traversed and return the top of stack
which will be the result of the operation.

Examples:
Example1: Evaluate the given prefix expression /+33-+47*+123
Example2: Evaluate the given prefix expression * + 6 9 - 3 1
Example3: Evaluate the given prefix expression -+7*45+20
Example4: Evaluate the given prefix expression -+8/632

CSE(AI&ML) 30
Conversion from Infix to Postfix:
Infix to postfix algorithm:
1) Print the operand as they arrive.
2) If the stack is empty or contains a left parenthesis on top, push the incoming operator on
to the stack.
3) If the incoming symbol is '(', push it on to the stack.
4) If the incoming symbol is ')', pop the stack and print the operators until the left
parenthesis is found.
5) If the incoming symbol has higher precedence than the top of the stack, push it on the
stack.
6) If the incoming symbol has lower precedence than the top of the stack, pop and print the
top of the stack. Then test the incoming operator against the new top of the stack.
7) If the incoming operator has the same precedence with the top of the stack then use the
associativity rules. If the associativity is from left to right then pop and print the top of the
stack then push the incoming operator. If the associativity is from right to left then push
the incoming operator.
8) At the end of the expression, pop and print all the operators of the stack.

Examples:
Example1 : Convert the given infix expression A*B-C/D+E to its equivalent postfix expression.
Example2 : Convert the given infix expression A*B/(C-D)+E*(F-G) to its equivalent postfix
expression.
Example3 : Convert the given infix expression K + L - M*N + (O^P) * W/U/V * T + Q to its
equivalent postfix expression.

CSE(AI&ML) 31
Evaluation of Postfix Expression:
Evaluation of postfix expression algorithm:
1) Iterate the given postfix expression from left to right.
2) Check the current element.
a) if it is an operand, push it to the stack.
b) if it is an operator, pop top two operands from the stack. Perform the operation and push
the elements back to the stack.
3) Do this till all the elements of the expression are traversed and return the top of stack
which will be the result of the operation.

Examples:
Example1: Evaluate the given postfix expression 6 8 + 9 2 - /
Example2: Evaluate the given postfix expression 5 6 2 + * 1 2 4 /
Example3: Evaluate the given postfix expression 5 6 7 + * 8 -
Example4: Evaluate the given postfix expression 3 4 * 2 5 * +

Precedence and Associativity:

Precedence Type Operators Associativity
1 Postfix () [] -> . ++ — Left to Right
+ – ! ~ ++ — (type)* &
2 Unary Right to Left
sizeof
3 Multiplicative */% Left to Right
4 Additive +– Left to Right
5 Shift <<, >> Left to Right
6 Relational < <= > >= Left to Right
7 Equality == != Left to Right
8 Bitwise AND & Left to Right
9 Bitwise XOR ^ Left to Right
10 Bitwise OR | Left to Right
11 Logical AND && Left to Right
12 Logical OR || Left to Right
13 Conditional ?: Right to Left
= += -+ *= /= %= >>=
14 Assignment Right to Left
<<= &= ^= |=
15 Comma , Left to Right

CSE(AI&ML) 32
Queue:
• A queue is a linear data structure in which the items are placed in linear fashion. In which
the data item is inserted at one end and deleted at another end.
• Queue follows FIFO (First In First Out) principle.
• FIFO implies that the element that is inserted first, comes out first.
Ex: A single-lane one-way road where the vehicle enters first- exits first, A ticket line, A line of
people waiting at a bank, An escalator, Print tasks are stored on a print queue while waiting to
be printed.

Queue Operations:
• There are some basic operations that can be performed on queue. They are:
a) enqueue() e) isEmpty()
b) dequeue() f) isFull()
c) peek() g) size()
d) display()
• a) enqueue() : Inserting / Writing a value into the queue.
• b) dequeue() : Deleting / Reading a value from the queue.
• c) peek() : Displaying the data element available at the front node of the queue without
deleting it.
• d) display() : Displaying all the elements from the queue.
• e) isEmpty() : Check whether the queue is empty or not. It returns true if the queue is
empty. Otherwise, it returns false.
• f) isFull() : Check whether the queue is full or not. It returns true if the queue is full.
Otherwise, it returns false.
• g) size(): This operation returns the size of the queue i.e. the total number of elements it
contains.

Example:
• Initially queue is empty.

CSE(AI&ML) 33
Queue ADT:
• enqueue() : Inserting / Writing a value into the queue.
• dequeue() : Deleting / Reading a value from the queue.
• peek() : Displaying the data element available at the front node of the queue without
deleting it.
• display() : Displaying all the elements from the queue.
• isEmpty() : Check whether the queue is empty or not. It returns true if the queue is empty.
Otherwise, it returns false.
• isFull() : Check whether the queue is full or not. It returns true if the queue is full.
Otherwise, it returns false.
• size(): This operation returns the size of the queue i.e. the total number of elements it
contains.

Queue implementation:
• Implementation of the enqueue operation checks if there is still any room left in the
queue, if there is any, it increments the rear index by one and adds the received item at
the position pointed by rear.
• Implementation of dequeue operation checks whether or not the queue is already empty,
if it is not, it returns the item which is pointed by front index, and increment the front
index by one.
• We can implement the queue by using two ways:
a) Implementation of queue using arrays.
b) Implementation of queue using linked lists.
• Both types of implementations have their own usage in specific situations.

CSE(AI&ML) 34
a) Implementation of queue using arrays:
• The implementation of queue using arrays involves allocating a fixed size array in the
memory. Both queue operations are made on this array with a constant check being made
to ensure that the array doesn’t go out of bounds.
• Basic operations :
a) enqueue()
b) dequeue()
c) peek()
d) display()

a) enqueue():
• The enqueue operation involves checking whether or not the rare pointer is pointing to
the upper bound of the array. If it is not the new item is inserted into the queue.
• It means check whether the queue is full or not,
if the queue is not full, increment the rear counter by one and insert the new item into
the queue,
if the queue is full, the new item is not possible to insert into the queue, then that
situation we call it as Queue Overflow

Sample code:
#define SIZE 3
int queue[SIZE];
int rear=-1, front=-1;
if(rear==SIZE-1)
printf(“Queue is full”);
else
{
rear++;
printf(“Enter an element:”);
scanf(“%d”,&item);
queue[rear]=item;
if(front==-1)
front=0;
}

b) dequeue():

CSE(AI&ML) 35
 • The dequeue operation involves checking whether or not the queue is already empty, if
it is not, it returns the item which is pointed by front index, and increment the front index
by one.
• It means check whether the queue is empty or not,
if the queue is not empty, delete the front element from the queue and increment the
front counter by one,
if the queue is empty, it is not possible to delete an element from the stack, then that
situation we call it as Queue Underflow

Sample code:
if(front==-1&&rear==-1)
printf(“Queue is empty”);
else
if(front==rear)
{
printf(“Deleted item is:%d”,queue[front]);
front=-1;
rear=-1;
}
else
{
printf(“Deleted item is:%d”,queue[front]);
front++;
}

c) peek():
Sample code :
if(front==-1&&rear==-1)
printf(“Queue is empty”);
else
printf(“Front element is : %d”, queue[front]);

d) display():
Sample code :
if(front==-1&&rear==-1)
printf(“Queue is empty”);
else
{

CSE(AI&ML) 36
 for(i=front;i<=rear;i++)
printf(“%d\t”, queue[i]);
}

b) Implementation of queue using linked list:

• The implementation of queue using linked list involves dynamically allocating memory
space at run time while performing queue operations.
• Since, the allocation of memory space is dynamic, the queue consumes only that much
amount of space is required for holding its elements.
• This is contrary to array-based queue which occupy a fixed memory space even if there
are no elements present.
• Basic operations :
a) enqueue()
b) dequeue()
c) peek()
d) display()

a) enqueue():
• The enqueue operation under linked list of queues invoves the following tasks:
• Reserving memory space of the size of a queue element in memory.
• Storing the added value at the new location.
• Linking the new element with the last element of the queue.
• Updating the end pointer.

Sample code:
struct node
{
int data;
struct node *next;
}
new=(struct node*)malloc(sizeof(struct node));
printf(“Enter an element:”);
scanf(“%d”,&elem);
new->data=elem;
new->next=NULL;
if(front==NULL&&rear==NULL)
{
front=new;

CSE(AI&ML) 37
 rear=new;
}
else
{
rear->next=new;
rear=new;
}

b) dequeue():
Sample code:
if(front==NULL&&rear==NULL)
printf(“Queue is empty”);
else
{
printf(“Deleted element is:%d”,front->data);
front=front->next;
temp->next=NULL;
free(temp);
}

c) peek():
Sample code:
if(front==NULL&&rear==NULL)
printf(“Queue is empty”);
else
{
temp=front;
printf(“%d->”,temp->data);
}

d) display():
Sample code:
if(front==NULL&&rear==NULL)
printf(“Queue is empty”);
else
{
temp=front;
while(temp!=NULL)

CSE(AI&ML) 38
 {
printf(“%d->”,temp->data);
temp=temp->next;
}
}

Note:
In linear data structures, the arrays and linked lists are having their own implementation whereas
stacks and queues does not. With the help of arrays and linked lists we can implement stacks and
queues.

Applications of Queues:
• Some other applications of the queue in real-life are:
• People on an escalator
• Cashier line in a store
• A car wash line
• One way exits

How to select a data structure ?

• A data structure is selected based on the type of data, operations required, and
efficiency needed.
Operation Suitable Data Structure

Fast access Array

Frequent
Linked List
insertion/deletion

Last In First Out Stack

First In First Out Queue

Fast search Hash Table

Sorted data Tree (BST, AVL)

Priority-based Heap

Network/relationships Graph

CSE(AI&ML) 39
 Unit-2
Trees
Trees: Introduction, Types of Trees, creating a Binary Tree from a General Tree, traversing a
Binary Tree, Binary Search Trees (BST), BST Operations- Searching, Insertion and Deletion, BST
ADT, BST Applications, Threaded Binary Trees, AVL Trees, Red –Black Trees, Splay Trees

Introduction:
• A tree data structure is a non-linear data structure because it does not store in a
sequential manner. It is a hierarchical structure, as elements in a Tree are arranged in
multiple levels.
• Tree is a non linear data structure, which organize data in a hierarchical structure.

Why Tree Data Structure?

• Other data structures such as arrays, linked list, stack, and queue are linear data
structures that store data sequentially. In order to perform any operation in a linear data
structure, the time complexity increases with the increase in the data size. But, it is not
acceptable in today's computational world.
• Different tree data structures allow quicker and easier access to the data as it is a non-
linear data structure.
Tree:
A tree is a finite set of one or more nodes. The first node referred as root node,
the other node could be partitioned into T1,T2,T3…..Tn are referred as sub trees.
(or)
A tree data structure is defined as a collection of objects or entities known as
nodes that are linked together to represent hierarchy.
(or)
A Tree is a non-linear hierarchical data structure consisting of nodes connected by
edges. It is widely used to represent hierarchical relationships (like organization charts, file
systems, etc.).
(or)
A tree is a connected graph without any circuits.
• In a Tree data structure, the topmost node is known as a root node. Each node contains
some data, and data can be of any type.
• In a tree data structure a node can have any [Link] child nodes.

CSE(AI&ML) 1
Some basic terms used in Tree data structure:
Node:
• A basic unit of a tree containing data and links to other nodes.
• Example: In a binary tree, a node stores data and links to left and right children.
Ex: A, B, C
Keys :
Key represents a value of a node based on which a search operation is to be carried out
for a node.
Root:
The first node from where the tree originates is called root.
(or)
The topmost node of a tree or the node which doesn't have any parent node is called the
root node.
(or)
A non empty tree must contain exactly one root node and exactly one path from the root
to all other nodes of the tree.
Ex: A
Note: Every tree has exactly one root.
Parent :
The node from which the branches emerges is called parent.

CSE(AI&ML) 2
 (or)
The node which is a predecessor of a node is called the parent node of that node.
(or)
If the node contains any sub node then that node is said to be the parent of that sub node.
(or)
A node that has sub-nodes is called the parent.
Ex: A, B, C, D, E, F, H, I ,J
Child:
The node which is the immediate successor of a node is called the child of that node.
(or)
If the node is descendent of any node then then that node is known as child node.
(or)
The node that emerge from the branches of a node, which is a descendant of some node.

Ex: B, C, D, E, F, G, H, I ,J, K, L, M, N, O, P

Note: All the nodes except root node are child nodes.
Links / edges / branches:
The link between nodes are called branches or links or edges.
(or)
A connection between parent and child nodes.
Ex: A-B, A-C, B-D, B-E, C-G, C-F
Note: In a tree with n [Link] nodes there are exactly n-1 [Link] edges.
Path:
All the nodes are reachable from root through a unique sequence of branches called a
path.
(or)
Path refers to the sequence of nodes along with the edges of a node.
(or)
A sequence of nodes connected by edges.
Ex: A-B-D-H-K
Path length:
Path length is the sum of the lengths of paths from the root to each node in a tree.
(or)
The number of edges from the root to that node.
(or)
The number of edges from source to destination.
Ex: A-K = 4, A-G = 2, A-J = 3

CSE(AI&ML) 3
Siblings:
Nodes having the same parent are called siblings.
(or)
Two or more nodes of a same parent.
(or)
Children of the same parent node are called siblings.
Ex: B,C D,E G,F O,P
Leaf node / external nodes / terminal nodes:
The nodes which don't have any child nodes are called leaf nodes.
(or)
A node that has no children.
Ex: G, K, L, M, N, O, P
• A leaf node is the bottom most node of the tree. There can be any [Link] leaf nodes present
in a general tree. Leaf node also be called external nodes (or) terminal nodes.
Internal nodes / non -terminal nodes :
A node has atleast one child node known as an internal nodes.
Ex: A, B, C, D, E, F, G, H, I, J
Note : Every non-leaf node is an internal node.
Ancestor :
The nodes that appear in the path from root node to a given node.
(or)
An ancestor of a node is any predecessor node on a path from the root to that node.
(or)
Any node that lies on the path from the root to that node (excluding the node itself). In
other words, if you can move upward from a node to reach another node, that node is an
ancestor.
(or)
Ancestor = Nodes above a given node (towards the root).
Ex: Ancestor of K = H, D, B, A
Ancestor of G = C, A
Note: The root node doesn't have any ancestor.
Descendant :
The node that appear in all paths from a given node .
(or)
The immediate successor of the given node is known as a descendant of a node.
(or)

CSE(AI&ML) 4
 Any node that lies below a given node in the tree (including children, grandchildren, etc.).
In other words, if you can move downward from a node to reach another node, that node is a
descendant.
(or)
Descendant = Nodes below a given node (towards leaves).
Ex: Descendant of A = B, D, H, K
Descendant of F = J, O
Note: The leaf nodes doesn't have any descendant.
Neighbor of a node :
• In a tree, neighbor of a node means any node that is directly connected to it by an edge.
• Parent or child nodes of that node are called Neighbors of that node.
Ex: Neighbor of B = A, D, E
Neighbor of L = H
Level :
Level of a node represents the generation of a node.
• In a tree each step from top to bottom is called as level of a tree.
• The level counts starts with 0 and increments by 1 at each level or step.
Ex : Level of A = 0
Level of B, C = 1
Level of D, E, F, G = 2
Degree of a node :
Degree of a node is the total [Link] children of that node.
Ex : degree(A) = 2 (B,C)
degree(F) = 1 (J)

Degree of a tree :
Degree of a tree is the highest degree of a node among all the nodes in the tree.
Ex : degree of a tree = 2
Height of a node :
The length of the longest path from that node to leaf node.
Ex: height(C)=1, height(C)=3  height(C)=3

Height of a tree :
The height of a tree is the maximum level of a node in a given tree.
• Height of a tree is the height of root node.
Ex : height(A)=2, height(A)=4  height(A)=4

Note : Height of all leaves is ‘0’

CSE(AI&ML) 5
Depth of a node:
Total [Link] edges from root node to a particular node is called as depth of that node.
(or)
Depth of a node is the length of a longest path from root node to that node.
Ex: depth(H)=3, depth(N)=4
Depth of a tree :
The maximum depth among all nodes in the tree.
Ex: depth of a tree=4
Note : Depth of root is ‘0’
Subtree:
Tree inside a tree.
(or)
A tree formed by any node and its descendants.
Ex: B D E
Note : In a tree each child from a node forms a subtree recursively.
Forest :
• A forest is a collection of disjoint trees (a group of multiple trees).
• If you remove the root of a tree, its subtrees form a forest.
Ex : If you remove A, then its subtrees form a forest
Tree rooted at B, Tree rooted at C
Visiting:
• Visiting a node means accessing or processing the data stored in the node.
• It is a single action, not a traversal.

Ex: If you go to node B and print its value → you are visiting node B.
Traversing:
Traversal means visiting all the nodes of a tree in a specific order, exactly once.
Common tree traversal methods:
i. Preorder (Root → Left → Right)
ii. Inorder (Left → Root → Right)
iii. Postorder (Left → Right → Root)
iv. Level Order (Breadth-first)
Types of trees:
There are some different types of trees are there :
• General tree
• Binary tree
• Binary search tree (BST)
• B-tree

CSE(AI&ML) 6
 • B+ tree
• AVL tree
• Red - Black tree
• Splay tree
General tree:
A tree in which a node can have any number of children.
Ex:

Binary tree:
Binary tree is a special tree data structure in which each node can have atmost 2 children.
Thus, in a binary tree each node has either ‘0’ or ‘1’ or ‘2’ children.
(or)
Binary tree is a finite set of elements. An empty tree is a Binary tree. If non-empty , a tree
in which all nodes can have atmost two children and all referred to as left and right subtrees.
Unlabeled binary tree:
A binary tree is unlabeled if it's nodes are not assigned any label.
[Link] diff binary trees possible with n is (2nCn)/(n+1)
Labeled binary tree:
A binary tree is labeled if all it's nodes are assigned a label.
[Link] diff binary trees possible with n labeled nodes is (2nCn)/(n+1)*n!
Types of binary trees:
There are some different types of binary trees are there :
1) Rooted binary tree
2) Full / Strictly binary tree
3) Complete / Perfect binary tree
4) Almost complete binary tree
5) Skewed binary tree
6) Balanced binary tree

CSE(AI&ML) 7
1) Rooted binary tree:
• A Rooted Binary Tree is a binary tree in which one specific node is designated as the root.
• Every binary tree is naturally a rooted tree because there is always a single root node at
the top.
• From the root, every other node can be reached via edges
Ex:

2) Full / Strictly binary tree:

A full binary tree is a binary tree that satisfies the following conditions:
• A binary tree in which every node has either 0 or 2 children is called a full binary tree. No
node has only one child.
• Full Binary Tree is also called as Strictly Binary Tree
Ex:

3) Complete / Perfect binary tree:

A complete binary tree is a binary tree that satisfies the following conditions:
• All internal nodes have exactly 2 children.
• All the leaf nodes are at the same level.
It is also called as perfect binary tree.
Ex:

CSE(AI&ML) 8
4) Almost complete binary tree:
Almost complete binary tree is a binary tree that satisfies the following conditions:
• All the levels are completely filled except possibly the last Level.
• The last level must be strictly filled from left to right.
Ex:

5) Skewed binary tree:

A Skewed binary tree is a binary tree that satisfies the following:
• All nodes except one node has one and only one child.
• The remaining node has no child.
(or)
A Skewed binary tree is a binary tree of n nodes such that it's depth is n-1
• There are 2 types of skewed binary trees are there:
i) Left skewed binary tree
ii) Right skewed binary tree
i) Left skewed binary tree:
A Left Skewed binary tree is a binary tree that satisfies the following:
• A binary tree where every node has only a left child.
• It looks like a linked list tilted to the left.
Ex :

ii) Right skewed binary tree:

A Right Skewed binary tree is a binary tree that satisfies the following:
• A binary tree where every node has only a right child.

CSE(AI&ML) 9
 • It looks like a linked list tilted to the right..
Ex :

6) Balanced binary tree:

• The height difference (Balance Factor) between left and right subtree of any node is at
most 1.
• Helps in faster searching.
Ex: AVL Tree, Red-Black Tree
Representation of binary trees:
Trees can be represented in two ways :
1. Array Representation (Sequential Representation).
2. Dynamic Node Representation (Linked List Representation).
[Link] Representation:
• If the node is stored at index i, then
• left child stores at 2*i+1
• right child at 2*i+2
• Parent at (i-1)/2

[Link] List Representation:

struct node
{
struct node *left;
int data;

CSE(AI&ML) 10
struct node *right;
}

Basic operations on Binary Tree:

• Inserting an element.
• Deletion for an element.
• Searching for an element.
• Traversing an element. There are four (mainly three) types of traversals in a binary tree
which will be discussed ahead.
Applications of Binary Tree:
• In compilers, Expression Trees are used which is an application of binary trees.
• Huffman coding trees are used in data compression algorithms.
• Priority Queue is another application of binary tree that is used for searching maximum
or minimum in O(1) time complexity.
• Represent hierarchical data.
• Used in editing software like Microsoft Excel and spreadsheets.
• Useful for indexing segmented at the database is useful in storing cache in the system,
• Syntax trees are used for most famous compilers for programming like GCC, and AOCL to
perform arithmetic operations.
• For implementing priority queues.
• Used to find elements in less time (binary search tree)
• Used to enable fast memory allocation in computers.
• Used to perform encoding and decoding operations.
• Binary trees can be used to organize and retrieve information from large datasets, such
as in inverted index and k-d trees.
• Binary trees can be used to represent the decision-making process of computer-
controlled characters in games, such as in decision trees.
• Binary trees can be used to implement searching algorithms, such as in binary search
trees which can be used to quickly find an element in a sorted list.

CSE(AI&ML) 11
 • Binary trees can be used to implement sorting algorithms, such as in heap sort which uses
a binary heap to sort elements efficiently.
Binary Tree Traversals:
Traversal: It is the process of visiting or displaying a node of a tree.
• Tree Traversal algorithms can be classified broadly into two categories:
I. Depth-First Search (DFS) Algorithms
II. Breadth-First Search (BFS) Algorithms
I. Tree Traversal using Depth-First Search (DFS) algorithm can be further classified into three
categories:
• Preorder Traversal (root-left-right)
• Inorder Traversal (left-root-right)
• Postorder Traversal (left-right-root)
[Link] Traversal:
• Preorder Traversal (root-left-right):
Visit the current node before visiting any nodes inside the left or right subtrees. Here, the
traversal is root – left child – right child. It means that the root node is traversed first then its left
child and finally the right child.
1) Visit the root
2) Process the left subtree of the root in preorder
3) Process the right subtree of the root in preorder
[Link] Traversal:
• Inorder Traversal (left-root-right):
Visit the current node after visiting all nodes inside the left subtree but before visiting any
node within the right subtree. Here, the traversal is left child – root – right child. It means that
the left child is traversed first then its root node and finally the right child.
1) Process the left subtree of the root in inorder
2) Process the root
3) Process the right subtree of the root in inorder
[Link] Traversal:
• Postorder Traversal (left-right-root):
Visit the current node after visiting all the nodes of the left and right subtrees. Here, the
traversal is left child – right child – root. It means that the left child has traversed first then the
right child and finally its root node.
1) Process the left subtree of the root in postorder
2) Process the right subtree of the root in postorder
3) Process the root
II. Tree Traversal using Breadth-First Search (BFS) algorithm can be further classified into one
category:

CSE(AI&ML) 12
 4) Level Order Traversal: Visit nodes level-by-level and left-to-right fashion at the same
level. Here, the traversal is level-wise. It means that the most left child has traversed first
and then the other children of the same level from left to right have traversed.
Binary Tree Traversals Examples:
 Construct binary tree from the given
Preorder - A B D E F C G H J L K
Inorder – D B E F A G C L J H K
 Construct binary tree from the given
Preorder – 10,5,2,6,14,12,15
Inorder – 2,5,6,10,12,14,15
 Construct binary tree from the given
Preorder – 1,2,4,7,5,8,3,6,9
Inorder – 4,7,2,8,5,1,6,9,3
 Construct binary tree from the given
Postorder - D F E B G L J K H C A
Inorder - D B F E A G C L J H K
 Construct binary tree from the given
Postorder – 4,8,2,5,1,6,3,7
Inorder – 8,4,5,2,6,7,3,1
Difference between Tree & Binary tree:
General tree Binary tree
General tree is a tree in which each node can Whereas in binary tree, each node can have at
have many children or nodes. most two nodes.
The subtree of a general tree do not hold the While the subtree of binary tree hold the ordered
ordered property. property.
In data structure, a general tree can not be
While it can be empty.
empty.
In general tree, a node can have at While in binary tree, a node can have at
most n(number of child nodes) nodes. most 2(number of child nodes) nodes.
While in binary tree, there is limitation on the
In general tree, there is no limitation on the
degree of a node because the nodes in a binary
degree of a node.
tree can’t have more than two child node.
In general tree, there is either zero subtree or While in binary tree, there are mainly two
many subtree. subtree: Left-subtree and Right-subtree.
Binary tree operations:
1. Insertion
2. Deletion

CSE(AI&ML) 13
 3. Searching
4. Traversing
[Link]:
• Insert at the first available position (level order)
This keeps the tree complete.
• Steps:
1. Create new node
2. If tree is empty → new node becomes root
3. Otherwise perform level-order traversal
4. Insert at the first node where
– left child is NULL → insert there
– else if right child is NULL → insert there
[Link]:
• Replace the node to be deleted with the deepest rightmost node
Steps:
1. Find the node to delete (level order)
2. Find the deepest rightmost node
3. Copy deepest node data into the node to delete
4. Delete the deepest node
[Link]:
• Use Level Order Traversal (since no ordering)
Steps:
1. Start from root
2. Traverse level by level
3. Compare each node with key
4. If found → return TRUE
5. If traversal ends → return FALSE

CSE(AI&ML) 14
Creating a Binary Tree from a General Tree:
The rules for converting a binary tree from a general tree are:
1. Root of the binary tree is the root of the general tree.
2. Left child of a node in the binary tree is the leftmost child of the node in the general tree.
3. Right child of a node in the binary tree is the right sibling of the node in the general tree.
Ex :

Steps:
1. Node A is the root of the general tree, so it will also the root of the binary tree
2. Left child of node A is the leftmost child of node A in the general tree and right child of
node A is the right sibling of the node A in the general tree. Since node A has no right
sibling in the general tree, it has no right child in the binary tree.
3. Now process node B. Left child of B is E and its right child is C(right sibling in general tree)
4. Now process node C. Left child of C is F(leftmost child) and its right child is D(right sibling
in general tree)
5. Now process D. Left child of D is I(leftmost child). There will be no right child of D because
it has no right sibling in the general tree.
6. Now process node I. There will be no left child of I in the binary tree because I has no left
child in the general tree. However, I has a right sibling J, so it will be added as the right
child of I.
7. Now process node J. Left child of J is K(leftmost child). There will be no right child of J
because it has no right sibling in the general tree.
8. Now process all the unprocessed nodes (E, F, G, H, K) in the same fashion, so the resultant
binary tree can be given as follows:

CSE(AI&ML) 15
Binary Search Tree:
The binary Search tree is a binary tree. An empty binary tree is also a BST. A non-empty
BST should satisfy the following properties:

1. All the elements must have a key and it must be distinct.

2. All the keys in the left sub tree must be less than the root element.
3. All the Keys in the right sub tree must be greater than root element.
4. All the left and right subtrees must also be the BST.

Operations:
1) Insertion
2) Searching
3) Traversing
4) Deletion
1) Insertion:
1. Place the new key in its correct position by comparing with root:
i. If the key is less than root then go to left subtree.
ii. If the key is greater than root then go to right subtree.
2. Repeat until correct empty spot is found.
Ex: Insert 15 into BST rooted at 10.
15 > 10 → go right → insert at right of 10.

Ex: 15, 10, 25, 30, 13, 2

Insert-15
Insert-10
10 < 15

CSE(AI&ML) 16
Insert-25
25 > 15
Insert-30
30 > 15
30 > 25
Insert-13
13 < 15
13 > 10
Insert-2
2 < 15
2 < 10

2) Searching:
• Start from root:
i. If key is equals to the root, then the key element is found
ii. If key is less than the root, then search in the left subtree
iii. If key is greater than the root, then search in the right subtree
3) Traversal:
• BST supports three main depth-first traversals:
i. Inorder (L → Root → R): Produces sorted order of elements.
ii. Preorder (Root → L → R): Used for copying tree structure.
iii. Postorder (L → R → Root): Used for deleting the tree.
4) Deletion:
• Deletion of a node has 3 Cases:
1. Deletion of a node is a Leaf node (no children) then simply delete it.
2. Deletion of a node having One child (either left or right) then replace the node with its
child.
3. Deletion of a node having Two children then replace the node with its inorder successor
(smallest in right subtree) or inorder predecessor (largest in left subtree).
1) Deletion of a node is a Leaf node (no children) then simply delete it.
Ex:

CSE(AI&ML) 17
Delete – 15 :
2) Deletion of a node having One child (either left or right) then replace the node with its child.

Delete-15:
3) Deletion of a node having Two children :
Case-i :
i. Visit the right subtree of the deleting node.
ii. Select the least value element called as inorder successor.
iii. Replace the deleting element with its inorder successor.
Case-ii :
i. Visit the left subtree of the deleting node.
ii. Select the greatest value element called as inorder predecessor.
iii. Replace the deleting element with its inorder predecessor.
3) Case-i) Visit the right subtree, Select the least value, Replace with deleting element.
Ex:

Delete-15:
3) Case-ii) Visit the left subtree, Select the greatest value, Replace with deleting element.

CSE(AI&ML) 18
Delete-25:
Examples:
Ex-1: Construct Binary Search Tree for the following elements 70, 56, 90, 45, 75, 100, 12, 120,
111, 11 and delete 45, 11, 90
Ex-2: Construct Binary Search Tree for the following elements 6, 4, 9, 2, 5, 8, 12 and delete 6, 5,
8
Ex-3: Construct Binary Search Tree for the following elements 29, 8, 3, 19, 16, 5, 13, 23, 27, 31
and delete 23, 5, 19
Applications:
1. Student database using roll number
2. Dictionary word search
3. Phone contact list
4. Library book management
5. Product price filtering in e-commerce
6. Gaming leaderboard ranking
7. Bank account search system
Time complexity :
Best case time Average case time Worst case time
Operations
complexity complexity complexity
Insertion O(log n) O(log n) O(n)

Deletion O(log n) O(log n) O(n)

Search O(log n) O(log n) O(n)

Space complexity :
Operations Space complexity

Insertion O(n)

Deletion O(n)
Search O(n)

CSE(AI&ML) 19
AVL Tree:
Balance factor :
Before going to the AVL tree, we have to learn about “Balance factor”.
Balance factor = height of the left subtree - height of the right subtree
Ex:
BF(2) : 0-0=0
BF(13) : 0-0=0
BF(30) : 0-0=0
BF(10) : 1-1=0
BF(25) : 0-1=-1
BF(15) : 2-2=0

• It is a complete binary tree (T) with TL & TR as left and right subtrees of T is an AVL tree if
all the nodes have a balance factor of -1, 0, 1
• It is also called as Balanced binary search tree.

AVL Tree Definition:

• An AVL Tree is a type of self-balancing Binary Search Tree.
• It was invented in 1962 by Adelson-Velsky and Landis (hence the name AVL).
• An empty binary tree is an AVL tree, if T is non-empty binary tree with TL & TR as its left
subtree and right subtrees of T is an AVL tree iff:
i)TL&TR are AVL trees
ii) The difference between height of the left and right subtrees of any node is at most 1.
Formally:
Balance Factor (BF) = Height of the Left Subtree − Height of the Right Subtree
For every node in an AVL tree: −1≤BF≤+1

AVL Tree Properties:

BST Property:
Left child < Parent < Right child.

CSE(AI&ML) 20
Height Balance Property:
The difference in height of left and right subtrees of any node is at most 1.
Height:
AVL tree height is always O(log n), where n = number of nodes.

Why AVL Tree ?

• Standard BST can become skewed (like a linked list) → worst-case height = O(n).
• AVL tree maintains balance → search, insert, delete all in O(log n) time.

Advantages AVL Tree:

• Faster search, insert, delete than normal BST.
• Height always bounded by O(log n).

Disadvantages AVL Tree:

• Slightly more complex due to rotations.

Unbalanced factor:
• If BF becomes less than -1 or greater than +1, the tree becomes unbalanced and needs
rotation to restore balance.
• Where the node is unbalanced, that node is called “Pivot node”
Ex:
BF(2) : 0-0=0
BF(13) : 0-0=0
BF(40) : 0-0=0
BF(10) : 1-1=0
BF(30) : 0-1=-1
BF(25) : 0-2=-2
BF(15) : 2-3=-1

CSE(AI&ML) 21
Rotations:
To maintain balance, AVL trees use rotations:
Rotations are of two types:
1) Single rotation
2) Double rotation
1) Single rotation:
i. LL-rotation (Right Rotation)
ii. RR-rotation (Left Rotation)
2) Double rotation:
i. LR-rotation (Left-Right Rotation)
ii. RL-rotation (Right-Left Rotation)
LL-Rotation:
Unbalance occur due to the insertion in the left subtree of the left child of a pivot node. In this
case the following manipulations takes place.
1) Right subtree AR of the left child A of a pivot node P becomes the left subtree of pivot node
P.
2) P becomes right child of A
3) Left subtree AL of A remains same.

Example:

RR-Rotation:
Unbalance occur due to the insertion in the right subtree of the right child of a pivot node. In
this case the following manipulations takes place.

CSE(AI&ML) 22
1) Left subtree BL of the right child B of a pivot node P becomes the right subtree of pivot node
P.
2) P becomes left child of B
3) Left subtree AL of A remains same

Example:

LR-Rotation:
Unbalance occur due to the insertion in the right subtree of the left child of a pivot node. In this
case the following manipulations takes place.
Rotation-1:
1) Left subtree BL of right child B of left child A of a pivot node P becomes the right subtree of
the left child A.
2) Left child A of the pivot node P becomes the left child of B
Rotation-2:
1) Right subtree BR of right child B of left child A of a pivot node P becomes the left subtree of
P.
2) P becomes the right child of B

CSE(AI&ML) 23
Example:

RL-Rotation:
Unbalance occur due to the insertion in the left subtree of the right child of a pivot node. In this
case the following manipulations takes place.
Rotation-1:
1) Right subtree BR of left child B of right child A of a pivot node P becomes the left subtree of
the right child A.
2) Right child A of a pivot node P becomes the right child of B
Rotation-2:
1) Left subtree BL of left child B of right child A of a pivot node P becomes the right subtree of P.
2) P becomes the left child of B

CSE(AI&ML) 24
Example:

Operations:
1) Insertion
2) Deletion
3) Searching
4) Traversal
Insertion:
• A new node is inserted just like in a Binary Search Tree (BST).
• After insertion, the balance factor (BF) of each ancestor node is checked.
• If any node becomes unbalanced (BF > 1 or BF < -1), appropriate rotations are
performed to restore balance.

Note:
For a given height h,
Minimum number of nodes (Nₕ ) in an AVL tree is given by:
Nh=Nh−1+Nh−2+1
Where N0=1, N1=2
Maximum number of nodes = 2h+1-1

CSE(AI&ML) 25
Deletion:
• A node is deleted similar to BST deletion.
• After deletion, balance factors are recalculated up the tree.
• If any node becomes unbalanced, rotations are performed.
Searching:
Same as Binary Search Tree searching:
• If the key is smaller → go to left subtree
• If the key is larger → go to right subtree
• If equal → node found
Traversing:
AVL trees support all tree traversals:
Traversal Type Order Use

Inorder Left → Root → Right Gives elements in sorted order

Preorder Root → Left → Right Used to copy or serialize tree

Postorder Left → Right → Root Used to delete tree

Level-order Level by level Used for BFS traversal

Time complexity:
Operation Time Complexity Description

Insertion O(log n) May involve rotation

Deletion O(log n) May involve rotation

Searching O(log n) Balanced height

Traversal O(n) Visit every node

Examples:
Ex-1: Construct AVL Tree for the following elements 10, 6, 13, 1, 14, 17, 18, 16, 4, 19 and delete
14, 16, 19
Ex-2: Construct AVL Tree for the following elements 7, 14, 2, 5, 10, 33, 56, 30, 15, 25, 66, 70, 4
and delete 10, 15, 66
Ex-3: Construct AVL Tree for the following elements 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75
and delete 35, 45, 55, 65
Ex-4: Construct AVL Tree for the following elements 29, 8, 3, 19, 16, 5, 13, 23, 27, 31 and delete
23, 5, 19

CSE(AI&ML) 26
Red-Black tree:
• It is another Binary Search Tree
• A Red-Black Tree is a type of self-balancing Binary Search Tree (BST) where each node
has an extra color bit: RED or BLACK.
• It maintains balance through coloring and rotation rules.
• The color is based on the properties of Red-Black tree.

Red-Black tree properties:

• A Red-Black Tree must be Binary Search Tree
• Each node is either RED or BLACK.
• The root node is always BLACK.
• Every NULL leaf (external leaf) is considered BLACK.
• If node is RED then its children are BLACK
• No two RED nodes can be adjacent (a RED node cannot have a RED parent or child).
• Every path from a node to its descendant NIL leaves contains the same number of
BLACK nodes.

Note-1: Every Red-Black tree is a Binary Search Tree but

every Binary Search Tree need not to be a Red-Black tree.
Note-2: Every AVL tree is a subset of Red-Black tree but
every Red-Black tree is not an AVL tree.
Note-3: Every perfect binary tree that contains only Black nodes is also a Red-Black tree.
Note-4: The longest path from the root is no more then twice the length of the shortest path.
(The path from the root to its furthest leaf node is no more then twice as long as the path from
root to its nearest leaf node).

Difference between AVL tree and Red-Black tree:

AVL Tree Red-Black Tree
In Red-Black tree maximus 2 rotations would
In AVL tree we need may rotations (some be required to balance the tree. (Some times
times) to balance the tree. rotations would be required, Some times
coloring would be required)
AVL tree is strictly height balanced tree. Red-Black tree is roughly height balanced tree.
AVL tree is more balanced than Red-Black tree. Red-Black tree is less balanced than AVL tree.
Insertion and deletion is faster in Red-Black
Searching is faster in AVL tree.
tree.

CSE(AI&ML) 27
Operations:
• Insertion
• Deletion
• Searching
• Traversing

Insertion:
1) If tree is empty, create a new node as root node with color Black.
2) If tree is not empty, create a new node as leaf node with color Red.
3) If parent of new node is Black then exit.
4) If parent of new node is Red then check the color of parent’s sibling of new node
a) If color is Black or NULL then do suitable rotation and recolor.
b) If color is Red then recolor and also check if parents parent of new node is not
root node then recolor it and recheck.
Deletion:
Step-1 :- Perform Binary Search Tree deletion.
Step-2 :-
Case-1 :-
• If node to be deleted is Red (Leaf node), just delete it.
• If node to be deleted is Black (Leaf node), replace with it’s NULL node which is Black, it
became Double Black
Case-2 :-
• If node to be deleted having only one child, replace parent with child without recoloring.
• If node to be deleted having two child's, replace parent with child(either left or right)
without recoloring. (Same as BST case-3 deletion)
Case-3 :- If root is double black, just remove the double black.
Case-4 :- If double black sibling is black and both of it’s children's are black,
• Remove double black (DB)
• Add black to it’s parent
– If parent is Red, it became black
– If parent is black, it became double black
• Make sibling Red
• If still DB exists, apply other cases.
Case-5 :- If DB’s sibling is Red
• Swap colors of parent and it’s sibling
• Rotate parent in DB’s direction
• Re apply the cases

CSE(AI&ML) 28
Case-6 :- If DB’s sibling is Black, siblings child who is far from DB is black, but near child to DB is
Red.
• Swap colors of DB’s sibling and siblings child who is near to DB.
• Rotate sibling in opposite direction to DB.
• Apply case-7
Case-7 :- If DB’s sibling is Black, far child is Red
• Swap colors of parent and sibling
• Rotate parent in DB’s direction
• Remove DB
• Change color of Red child to Black

Searching:
Same as Binary Search Tree searching:
• If the key is smaller → go to left subtree
• If the key is larger → go to right subtree
• If equal → node found
Traversal:
• Similar to BST that supports three main depth-first traversals:
i. Inorder (L → Root → R)
ii. Preorder (Root → L → R)
iii. Postorder (L → R → Root)

Time Complexity:
Operation Average Case Worst Case
Search O(log n) O(log n)
Insertion O(log n) O(log n)
Deletion O(log n) O(log n)

Advantages:
 Maintains balanced height → faster operations.
 Commonly used in system-level libraries (e.g., C++ STL map, set, Java TreeMap).
 Less rotation overhead compared to AVL Tree.

Disadvantages:
 Implementation is more complex.
 Slightly slower lookup compared to AVL trees (since it allows more imbalance).

CSE(AI&ML) 29
Splay Tree:
• A Splay Tree is a type of self-adjusting Binary Search Tree (BST) in which recently accessed
elements are moved to the root using a process called splaying.
• After every operation (insertion, deletion, or search), the accessed node is “splayed”
(brought to the root) through a series of tree rotations.
• This makes frequently accessed elements quicker to access next time.
Note :- Splay tree & Red-Black tree are roughly height balanced tree whereas AVL tree is strictly
height balanced tree.

Operations:
• Splaying
• Searching + Splaying = Searching
• Insertion + Splaying = Insertion
• Deletion + Splaying = Deletion
• Traversing

Searching:
• Searching Perform a normal BST search.
• If the element is found (or the search ends at a leaf), splay the last accessed node to the
root.
• Makes future access to that element faster.
Case-1 :- Search item is root node.
Case-2 :- Search item is a child of root node.
i. Left child
ii. Right child
Case-3 :- Search item is a grand child of root node.
i. Left child
ii. Right child
Rotations:
• Left child : Right rotation – Zig rotation (or) Zig-right rotation
• Right child : Left rotation – Zag rotation (or) Zig-left rotation
• Grand child(Left Left) : Two Right rotations – Zig-Zig rotation (or) Zig-Zig right rotation
• Grand child(Right Right) : Two Left rotations – Zag-Zag rotation (or) Zig-Zag left rotation
• Grand child(Right Left) : One Right rotation & One Left rotation – Zig-Zag rotation
• Grand child(Left Right) : One Left rotation & One Right rotation – Zag-Zig rotation

CSE(AI&ML) 30
Insertion:
• Insert the element like in a BST.
• After insertion, splay the newly inserted node to the root.
Deletion (Bottom-up Splaying):
To delete an element:
Case-1 :-
• Delete the element.
• Splaying would be performed on it’s parent.
Case-2:-
• Delete the element.
• Splaying would be performed on it’s parent.
• If parent is already a root node, no need to do splaying.
Case-3:-
• If the deleted element is not found in the tree, we need to perform splaying on it’s
descendent.
Case-4:-
• If the deleted element is a root node, simply delete it, and no need to perform splaying.

Deletion(Top-down splaying):
To delete an element:
Case-1:-
1. Splay the node to be deleted to the root.
2. Remove the root.
3. Join the left and right subtrees:
– Splay the maximum node in the left subtree to the root.
– Attach the right subtree as the root’s right child.
Case-2:-
1. Splay the node to be deleted to the root.
2. Remove the root.
3. Join the left and right subtrees:
– Splay the maximum node in the left subtree to the root. If the maximum node in
the left subtree is already in the root no need to do splay
– Attach the right subtree as the root’s right child.
Case-3:-
1. Splay the node to be deleted to the root.
2. Remove the root.
3. Join the left and right subtrees:

CSE(AI&ML) 31
 – If there is no left subtree, the root of the right subtree becomes the root of the
tree.
– If there is no right subtree, then there is no chance to make the left subtree root
as the root of the tree. Find the maximum element of the left subtree and splay
it. Then make that element as the root of the tree.
Time complexity:
Operation Average Case Amortized Time Worst Case
Search O(log n) O(log n) O(n)
Insertion O(log n) O(log n) O(n)
Deletion O(log n) O(log n) O(n)
Traversal O(n) O(n) O(n)

Although a single operation may take O(n) in the worst case, the amortized time (average over
a sequence of operations) is O(log n).

Advantages:
• Fast access to recently used elements (good for caching or repeated access).
• No need to store balance factors or colors (simpler structure).
• Amortized O(log n) time per operation.
• Self-adjusting — automatically brings frequently accessed nodes near the root.

Disadvantages:
• Worst-case time O(n) for a single operation.
• Not strictly balanced — may become skewed temporarily.
• More rotations than Red-Black or AVL trees.
• Not ideal for uniformly accessed data (where every key is equally likely).

CSE(AI&ML) 32
 Unit-3
Multi way Search Trees, Heaps, Searching
Multi way Search Trees: Introduction, B Trees, B Trees ADT, 2-3 Trees, 2-3-4 Tree, B* Tree, B+
Tree
Heaps: Binary Heaps, Binomial heaps, Fibonacci heaps, Comparison of Various Heaps,
Applications
Searching: Introduction, Interpolation Search, Jump search

Definition of m-way Search tree:

An m-way search tree is a generalization of a binary search tree (BST) where each node
can have more than two children — specifically, up to m children and up to m − 1 keys.
In other words:
• A binary search tree is a 2-way search tree.
• An m-way search tree allows up to m branches (children) per node.

Structure of an m-way Search Tree:

For a node in an m-way search tree:
• Each node can have maximum m children.
• Each node can contain maximum m-1 keys.
• Keys within a node are in sorted order K1<K2<K3<⋯<Km-1

Example:
For m = 4 (a 4-way search tree):
• Each node can have 3 keys and 4 children.
• The search space splits into 4 parts at each node — improving efficiency.

B-Tree:
A B-Tree is a self-balancing multiway search tree either empty or if it is not empty it satisfies
the following conditions:
• The root node has atleast two children.
• The data items are stored in leaf nodes.

CSE(AI&ML) 1
 • All the nodes other than root have atleast m/2 children.
• All the leaf nodes (or) external nodes are ended at the same level.
• The non-leaf node stores upto m-1 keys to guide the search.

For a B-Tree of order m:

• Each node can have maximum m children.
• Each node can have minimum children :
– For Leaf : 0
– For Root : 2 children

– For Internal nodes : ⌈m/2⌉ children

• Each node can have maximum m-1 keys.
• Each node can have minimum keys:
– For root : 1
– For all other nodes : ⌈m/2⌉ -1 keys

Operations:
• Searching
• Traversing
• Insertion
• Deletion

Searching:
• Works similar to Binary Search:
– Start from the root.
– Perform binary search among keys in the node.
– If not found, follow the appropriate child.

• Continue until the key is found or a leaf is reached.

Traversing:
• Traversal is similar to inorder traversal in BSTs, but generalized for multiple keys per
node:

CSE(AI&ML) 2
  For each node:
 Traverse the first child.
 Visit key₁.
 Traverse next child.
 Visit key₂ … and so on.

• Inorder traversal gives keys in sorted order.

Insertion:
1) B-Tree is initially empty. Get a node and insert the key value into it, and make it as root
node.
2) To insert a node in a B-Tree of order m can have almost m-1 key elements.
3) When the key value which is to be inserted into a node already has the maximum [Link]
keys, then the following steps are to be followed:
a) Insert the value say X into the list of values in the node in ascending order.

b) Split the list of values into 3 parts P1, P2, P3

 P1 contains first ⌈m/2⌉-1 key values.
 P2 contains ⌈m/2⌉ key values
 P3 contains ⌈m/2⌉+1 key values.
c) With the splitting, the ⌈m/2⌉ element value is to be inserted into the parent node
of the current node. If the parent node is NULL then create a new node. In the
place of current node, two nodes are to be allotted containing the key values in
P1 & P3 respectively.
Examples:
1) 10, 20, 30, 40, 50, 60, 70, 80, 90 of order m-3

2) 2, 1, 5, 6, 8, 4, 7, 9, 10 of order m-3
3) 36, 54, 12, 18, 2, 15, 40, 39 of order m-3
4) 1 to 20 of order m-5
5) 1 to 10 of order m-3
6) 5, 3, 21, 9, 1, 13, 2, 7, 10, 12, 4, 8 of order m-4

7) D, H, Z, K, B, P, Q, E, A, S, W, T, C, L, N, Y, M of order m-5

CSE(AI&ML) 3
Deletion:
Deletion of a key value from a B-Tree by takes place in several situations. Each situation has
unique rule for managing the deletion. There are two main properties which are to be take care
of during deletion are stated as below:
• The root node must have atleast one key value.
• All other nodes(Except the root) must have atleast ⌈m/2⌉-1 key values.

Case-1 : Deletion of a key value from a leaf node

After deleting a key value check whether a node from which a key value has to be deleted
contains minimum [Link] nodes or not.
There are 2 cases again.
a) Removal of a key value leads to the [Link] keys greater than or equal to ⌈m/2⌉-1. It is the
simplest case of deletion. Removal of a key value from the leaf node which doesnot
disturb the requirement of minimum [Link] key elements.
b) Removal of a key value leads to the [Link] keys less than ⌈m/2⌉-1. In such cases we have
to move the key value from the sibling of the node(Borrow a Key From a Sibling). Again
3 situations may be possible in this case.
a) The nearest right sibling contains more than ⌈m/2⌉-1 key values.
b) The nearest left sibling contains more than ⌈m/2⌉-1 key values.
c) Neither the nearest left sibling nor the right sibling contains more than ⌈m/2⌉-1
key values.
When both the siblings are available then which sibling will be selected for moving the key
value from it, is depends on the programmer.
c) If both siblings have only ⌈m/2⌉-1 keys, merging is required.

Steps:
• Merge the leaf node with a sibling.
• Bring down the separator key from the parent.
• Form a single merged node.
• Delete the key inside the merged node.

Case-2 : Deletion of a key value from a non-leaf node

CSE(AI&ML) 4
 Case Condition Action

1 Left child has ≥ min keys Replace with predecessor, delete recursively

2 Right child has ≥ min keys Replace with successor, delete recursively

Both children have min Merge left child + key + right child → delete
3
keys recursively

B Tree ADT:
The B-Tree ADT defines several standard operations, all with a time complexity of O(log n)
• Search: A recursive process starting at the root, comparing the target key against keys in
the current node to determine which child pointer to follow.
• Insertion: Locates the correct leaf node for a new key; if the node becomes full, it splits
at the median, pushing a value up to its parent to maintain the tree's balance.
• Deletion: Removes a key from a leaf or internal node; if removal causes a node to fall
below its minimum key requirement (underflow), it borrows a key from a sibling or
merges with one.

Time complexities:
Operation Time Complexity Description

Search O(logₘ n) Efficient lookup

Insertion O(logₘ n) May involve split

Deletion O(logₘ n) May involve merge/borrow

Traversal O(n) Visits all nodes

(Here m = order of the B-Tree, n = number of keys)

Advantages:
1. Balanced Structure — All leaves at the same level → consistent performance.
2. Efficient Disk Access — Large node size reduces number of disk I/O operations.
3. Fast Searching, Insertion, Deletion — O(logₘ n) time for all.

CSE(AI&ML) 5
 4. Suitable for Large Data Sets — Common in databases and file systems.
5. Sorted Data Storage — Inorder traversal gives sorted output.
6. Automatic Balancing — No need for rebalancing algorithms like AVL/Red-Black.

7. Reduces Height — Higher branching factor → fewer levels → faster access.

Disadvantages:
1. Complex Implementation — Node splitting and merging logic can be tricky.
2. Memory Overhead — Requires extra space for multiple keys and child pointers.
3. Not Ideal for Small Data — Simpler trees (like AVL) are faster in memory.

4. Slower for In-Memory Operations — Optimized for disk-based storage, not RAM.
5. Frequent Node Splitting/Merging — During insert/delete may cause overhead.

B+ tree:
A B+ Tree is an extension of a B-Tree in which all data (records or actual values) are
stored only at the leaf nodes, and internal nodes store only keys to guide the search.
In simple words:
 B-Tree = data stored at both internal and leaf nodes

 B+ Tree = data stored only in leaf nodes, internal nodes only help in searching
It is widely used in database indexing and file systems because it provides fast sequential and
random access.
Structure of B+ Tree:
For a B+ Tree of order m:
• Each internal node can have at most m children.
• Each internal node (except root) must have at least ⌈m/2⌉ children.

• Each internal node contains m−1 keys.

• All leaf nodes appear on the same level and are linked together using pointers (for fast
traversal).
Key points:
1. All actual data entries are stored only in leaf nodes.
2. Internal nodes act only as index nodes.

CSE(AI&ML) 6
 3. Leaf nodes are linked sequentially (like a linked list).
4. Provides efficient range and sequential access.

Operations:
• Searching
• Traversing
• Insertion
• Deletion
Example:

Construct B+ tree with the following elements 1, 4, 7, 10, 17, 21, 31, 25, 19, 20, 28, 42 of order
m-4

Time complexities:
Time
Operation Description
Complexity

Search O(logₘ n) Traverse from root to leaf

Insertion O(logₘ n) Split may propagate upward

Deletion O(logₘ n) May cause merging/borrowing

Traversal O(n) Sequential through leaf links

(Here m = order of the B+ tree, n = total keys)

Advantages:
1. Efficient Searching — Logarithmic time due to balanced height.

2. Faster Range Queries — Leaf nodes linked in sequence enable fast range search.
3. Better Disk Access — Internal nodes smaller (only keys) → fewer I/O operations.
4. All Records at Leaf Level — Makes sequential access simple and predictable.
5. Balanced Tree — All leaves are at same level → consistent performance.
6. Efficient for Indexing — Ideal for database and filesystem indexing.

7. Supports Both Random & Sequential Access.

Disadvantages:

CSE(AI&ML) 7
 1. More Space Usage — Leaf nodes store all data + linked pointers.
2. Insertion/Deletion Complexity — Node splits and merges can be tricky.
3. Extra Overhead — Maintaining linked leaf structure adds pointer management.

4. Redundant Keys — Keys appear both in internal and leaf nodes (in some
implementations).

Diff btw B Tree and B+ Tree:

Feature B-Tree B+ Tree

In both internal and leaf

Data Storage Only in leaf nodes
nodes

Search Speed Slower for range queries Faster for range and sequential access

Leaf Node Linking Not linked Linked sequentially

Redundancy No key duplication Keys may appear twice (internal + leaf)

Traversal Must traverse entire tree Easy — just follow leaf links

Access Type Random access efficient Random + Sequential access efficient

Used In File systems Databases and indexing systems

B* tree:
A B Tree* (B-star tree) is a specialized variant of the B-Tree designed to optimize storage
utilization and reduce the frequency of costly node-splitting operations. It is primarily used in
high-performance file systems and databases.
Brief Notes & Key Characteristics:
Denser Nodes: Unlike a standard B-Tree where non-root nodes must be at least 1/2 full, a B*
Tree requires them to be at least 2/3 full.
Delayed Splitting: Instead of splitting a node immediately when it becomes full, a B* Tree first
attempts a "spill" operation. It checks if a neighboring sibling has free space and redistributes
keys between them.
3-for-2 Split: When both a node and its sibling are completely full, they are split into three
nodes instead of two (as in standard B-Trees), maintaining the 2/3 fullness property.
Root Structure: The root node can have between 2 and 2⌊(2m-2)/3⌋+1

CSE(AI&ML) 8
Operations:
• Searching
• Traversing

• Insertion
• Deletion
Example:
Construct B* tree with the following elements 1, 4, 7, 10, 17, 21, 31, 25, 19, 20, 28, 42 of order
m-4

CSE(AI&ML) 9
Diff btw B Tree, B+ Tree, B* Tree:

Feature B-Tree B+ Tree B* Tree

Internal nodes store only

Data Keys and records stored in
keys, records stored in leaf Similar to B+ Tree
Storage internal and leaf nodes
nodes

Search may end at internal Search always ends at leaf Search always ends
Search Path
node or leaf node node at leaf node

Leaf Node Leaf nodes are linked for

Usually not linked Leaf nodes are linked
Linking sequential access

Space Highest space

Moderate Better than B-Tree
Utilization utilization

Redistributes with
Node
Split into 2 nodes when full Split into 2 nodes when full sibling first, then split
Splitting
into 3 nodes

Minimum
At least 50% full At least 50% full At least 66% full
Occupancy

Range
Slower Faster due to linked leaves Faster
Queries

More efficient for

Complexity Simpler More complex
databases

Advanced database
Applications File systems, indexing Databases, file systems
systems

CSE(AI&ML) 10
Binary Heaps:
• A binary heap is a complete binary tree in which every node satisfies the heap property
which states that:
If B is a child of A, then key(A) ≥ key(B)
• This implies that elements at every node will be either greater than or equal to the
element at its left and right child. Thus, the root node has the highest key value in the
heap. Such a heap is commonly known as a max-heap.
• Alternatively, elements at every node will be either less than or equal to the element at
its left and right child. Thus, the root has the lowest key value. Such a heap is called a
min-heap.
• Please refer unit-4

Binomial Heaps:
• A Binomial Heap is a collection of binomial trees satisfying heap order property.
• It supports efficient merging of heaps.
Binomial Tree:
A Binomial Tree of order k:

• Has 2k nodes
• Height = k
• Root degree = k
Examples of Binomial Trees:

Order Nodes

B0 1

B1 2

B2 4

B3 8

CSE(AI&ML) 11
Properties of Binomial Heap:
1. Each binomial tree satisfies heap property.
2. No two trees have same degree.

3. Trees are arranged in increasing order of degree.

Operations on Binomial Heap:
1. Creation
Create a heap with single node.
Complexity: O(1)

2. Merge (Union):
Two heaps are merged similarly to binary addition.
Steps
1. Merge root lists.
2. Combine trees with same degree.

Complexity : O(log n)
3. Insertion:
Steps
1. Create one-node heap.
2. Union with existing heap.
Complexity : O(log n)
4. Find Minimum:
Check all roots and return minimum.
Complexity : O(log n)
5. Delete Minimum:

Steps
1. Find minimum root.
2. Remove tree.
3. Reverse child list.

CSE(AI&ML) 12
 4. Merge remaining heap.
Complexity : O(log n)
Advantages of Binomial Heap

• Efficient merging
• Good for priority queues
• Flexible structure
Disadvantages
• More complex than binary heap

• Higher constant factors

Fibonacci Heaps:
• A Fibonacci Heap is an advanced heap structure consisting of a collection of heap-
ordered trees.
• It improves amortized running times for many operations.
• Used mainly in advanced graph algorithms.

Structure of Fibonacci Heap

Features:
• Circular doubly linked lists
• Lazy merging
• Trees are not strictly structured

Operations on Fibonacci Heap:

1. Insert:
• Add node directly to root list.
Complexity : O(1) amortized
• 2. Find Minimum:

Pointer to minimum node maintained.

Complexity : O(1)

CSE(AI&ML) 13
3. Union:
• Concatenate root lists.
Complexity : O(1)

4. Extract Minimum:
Steps
1. Remove minimum node.
2. Add children to root list.
3. Consolidate trees.

Complexity : O(log n) amortized

5. Decrease Key:
Steps
1. Reduce key value.
2. Cut node if heap property violated.

3. Cascading cuts may occur.

Complexity : O(1) amortized
Advantages of Fibonacci Heap:
• Extremely efficient decrease-key operation
• Best for graph algorithms
• Efficient merging
Disadvantages:
• Very complicated implementation
• Large memory overhead
• Poor practical performance for small datasets

CSE(AI&ML) 14
Comparison of Various Heaps:

Feature Binary Heap Binomial Heap Fibonacci Heap

Complete Binary Collection of Collection of Heap

Structure
Tree Binomial Trees Ordered Trees

Find Min O(1) O(log n) O(1)

Insert O(log n) O(log n) O(1) amortized

Delete Min O(log n) O(log n) O(log n) amortized

Merge O(n) O(log n) O(1)

Decrease Key O(log n) O(log n) O(1) amortized

Complexity Simple Moderate Complex

Memory Usage Low Moderate High

Practical Usage Very High Medium Low

Applications of heap:
1. Priority Queues

Most important application.

Used in:
• CPU Scheduling
• Printer Scheduling
• Event Simulation

2. Heap Sort
Binary heaps are used in Heap Sort.
3. Graph Algorithms
Dijkstra’s Algorithm - Uses min-priority queue.

CSE(AI&ML) 15
Prim’s Algorithm - Uses heaps for selecting minimum edge.
4. Operating Systems
Used in:

• Process scheduling
• Memory management
5. Network Routing
Routing algorithms use heaps to find shortest paths.
6. Data Compression

Huffman coding uses priority queues based on heaps.

Binary Heap vs Binomial Heap vs Fibonacci Heap:

Binary Heap
• Simple and efficient

• Best for general applications

Binomial Heap
• Better merging capability
• Useful in priority queue merging
Fibonacci Heap

• Best theoretical performance

• Mainly used in advanced algorithms

CSE(AI&ML) 16
Time complexities:

Operation Binary Heap Binomial Heap Fibonacci Heap

Find Min O(1) O(log n) O(1)

Insert O(log n) O(log n) O(1) amortized

O(log n)
Delete Min O(log n) O(log n)
amortized

Merge O(n) O(log n) O(1)

Decrease Key O(log n) O(log n) O(1) amortized

Searching:
Searching is a fundamental operation in data structures. It allows us to find specific data items
within a collection of data.
Many types of searching methods are used to search for data entries in various data structures.
Some of them include −
• Linear Search
• Binary Search
• Interpolation Search
• Jump Search
• Hash Table
• Exponential Search
• Sublist search
• Fibonacci Search

CSE(AI&ML) 17
Linear Search:
• Linear Search is the simplest searching technique where we check each element one by
one in a list/array until we find the target value.
• It is also called sequential search.
Steps:

• Start from the first element.

• Compare each element with the target value.
• If a match is found → Return the index / element.
• If the entire list is checked and no match → Element not found
Advantages :

• Simple to understand and implement

• Works on both sorted and unsorted lists
• Useful for small datasets
• No additional memory required
• Works well when the target is near the beginning

Disadvantages :
• Slow for large datasets
• Not suitable for repeated searches
• Cannot use binary search advantages
• More comparisons

CSE(AI&ML) 18
Binary Search:
Binary Search is an efficient searching algorithm that works on sorted arrays.
It repeatedly divides the search interval into half and eliminates one half based on comparison.
Steps:
1) Start with two pointers:

• low = start of array

• high = end of array
2) Find the middle index → mid = (low + high) / 2
3) Compare target value with arr[mid]:
• If target == arr[mid] → found

• If target < arr[mid] → search left half

• If target > arr[mid] → search right half
4) Repeat until low > high → element not found
Advantages :
• Very fast for large datasets

• Fewer comparisons
• Efficient for repeated searches
• Uses constant memory (iterative version)
Disadvantages :
• Array must be sorted

• Not suitable for linked lists

• Harder to implement than linear search
• Insertion/Deletion costly in sorted arrays

CSE(AI&ML) 19
Interpolation Search:
• Interpolation search, also known as extrapolation search, is a searching technique that
finds a specified value in a sorted array.
• Interpolation Search is an efficient searching technique used to find an element in a
sorted array. It works by estimating where the target value might be located, instead of
always checking the middle element like Binary Search.
• It is especially useful when the data is uniformly distributed.
• in interpolation search, interpolation is used to find an item near the one being
searched for, and then linear search is used to find the exact item.
• Formula: Middle=low+(high-low) ( (key– a[low]) /(a[high]– a[low]))

(or)

Ex : 10, 20, 30, 40, 50, 60, 70, 80 - key=50

• Advantages
1. Faster than Binary Search for uniformly distributed data.
2. Average time complexity is very good: O(log log n).

3. Reduces number of comparisons in large sorted arrays.

4. Useful when values are evenly spaced.
• Disadvantages
1. Works only on sorted arrays.
2. Not efficient for non-uniformly distributed data.

3. Worst case time complexity is O(n).

4. Slightly more complex than Linear Search and Binary Search.
5. Cannot be used efficiently on linked lists.

CSE(AI&ML) 20
Jump Search:
• Jump Search is a searching algorithm used to find an element in a sorted array. Instead
of checking every element one by one, it jumps ahead by fixed steps and then performs
a linear search in the identified block.
• It is faster than Linear Search for sorted data.
Jump Size Formula

For an array of size n, the optimal jump size is: m = √n.

Where:
n = number of elements
m = jump step size
Steps of Jump Search:

1. Ensure the array is sorted.

2. Find jump size = √n.
3. Start from index 0 and jump ahead by step size.
4. Continue jumping until an element greater than or equal to the key is found.
5. Perform linear search in the previous block.

6. If key is found, return position.

7. If not found, report element not present.
Ex : 10, 20, 30, 40, 50, 60, 70, 80, 90 - key=70
Advantages
• Faster than Linear Search on sorted arrays.

• Easy to understand and implement.

• Requires fewer comparisons than Linear Search.
• Efficient for large sorted arrays.
• Better than Binary Search when backward jumps are costly (some storage systems).
Disadvantages

• Works only on sorted arrays.

• Slower than Binary Search in many cases.

CSE(AI&ML) 21
 • Needs extra step calculation (√n).
• Not suitable for linked lists.
• Worst-case still involves linear search inside a block.

CSE(AI&ML) 22
 Unit-4
Graphs, Sorting
Graphs: Introduction, Directed Graphs, Bi connected Components, Representation of Graphs,
Graph Traversal Algorithms, Graph ADT, Applications of Graphs
Sorting: Radix Sort, Heap sort, Shell Sort, Tree Sort

Graph:
A graph is a non-linear data structure that consists of:
• a set of vertices ‘V’(nodes)
• a set of edges ‘E'(connections) linking the vertices.
Formal Definition:
A graph G is defined as: G = (V, E)
Where:
V = set of vertices (v1, v2, v3, v4,-----)
E = set of edges (e1, e2, e3, e4, -------)
(unordered or ordered pairs of vertices)
Ex:
Vertices: A, B, C
Edges: (A-B), (B-C), (A-C)

Graph Terminologies:
1) Vertex (Node) :
A vertex is a point in a graph that represents an object.
Ex: A, B, C
2) Edge :
An edge is a link/connection between two vertices.
Edges can be:
• Directed (one-way)
• Undirected (two-way)
Ex: (A-B), (B-C), (A-C)
Types of graphs :
1) Directed Graph (Digraph) :
A graph where every edge has a direction.
Ex: A → B
2) Undirected Graph :
A graph where edges do not have direction.
Ex: A — B

CSE(AI&ML) 1
3) Weighted Graph:
A graph in which each edge has an associated weight (cost, distance, time, etc.).
• Weighted Directed Graph
• Weighted Undirected Graph
4) Unweighted Graph :
A graph without weights on edges.
• Unweighted Directed Graph
• Unweighted Undirected Graph
5) Degree of a Vertex :
The number of edges connected to a vertex.
Undirected graph:
Degree(v) = number of edges connected to v
Directed graph:
In-degree: Number of edges coming into the vertex
Out-degree: Number of edges going out from the vertex
Ex (For Directed): A → B
Degree of A: Out-degree = 1, In-degree = 0
6) Path :
A sequence of vertices where each adjacent pair is connected by an edge.
Ex: A → B → C
7) Simple Path :
A path in which no vertex is repeated.
8) Cycle :
A path that starts and ends at the same vertex.
Ex: A → B → C → A
Cyclic Graph
A cyclic graph is a graph that contains at least one cycle.
Acyclic Graph
An acyclic graph is a graph that contains no cycles.
9) Connected Graph :
In an undirected graph:
A graph is connected if there is at least one path between every pair of vertices.
10) Disconnected Graph :
A graph containing more than one isolated part.
11) Complete Graph :
A graph where every vertex is connected to every other vertex.
For n vertices, number of edges = n(n−1)/2
12) Subgraph :

CSE(AI&ML) 2
A graph formed using a subset of vertices and edges of another graph.
13) Tree :
A special type of graph with:
• no cycles
• exactly n − 1 edges for n vertices
• connected
14) Directed Acyclic Graph (DAG) :
A directed graph without cycles.
Used in scheduling, dependency graphs, etc.
15) Adjacent Vertices :
Two vertices connected by an edge are said to be adjacent.
Ex: A — B
A and B are adjacent.
16) Incident Edge :
An edge incident on a vertex is the edge that touches that vertex.
17) Isolated Vertex :
An isolated vertex is a vertex with degree 0.
(No edges connected to it.)
18) Pendent Vertex (Leaf Vertex) :
A pendent vertex is a vertex that has degree 1.
(Only one edge is connected to it.)
19) Self-Loop :
An edge that connects a vertex to itself.
Ex: A → A
20) Parallel Edges (Multiple Edges) :
Two or more edges that connect the same pair of vertices in a graph are called parallel edges.
These edges are distinct but connect the same two nodes.

Types of graphs:
1. Simple Graph
2. Multigraph
3. Pseudograph (Multigraph + self-loops permitted)
4. Directed Graph (Digraph)
5. Undirected Graph
6. Weighted Graph
7. Unweighted Graph
8. Complete Graph
9. Connected Graph

CSE(AI&ML) 3
 10. Disconnected Graph
11. Directed Acyclic Graph (DAG)
12. Bipartite Graph (Vertices can be divided into two sets such that: No two vertices within
the same set are connected)
13. Planar Graph
14. Tree

Representation of Graph:
Graphs can be represented in two standard ways:
1) Adjacency Matrix representation
2) Adjacency List
1) Adjacency Matrix representation
A 2D matrix of size n × n (n = number of vertices)
Rules:
• 1 means an edge exists
• 0 means no edge
• For weighted graph → store weight instead of 1
Advantages:
• Very fast to check if an edge exists — O(1)
• Good for dense graphs
Disadvantages:
• Takes O(n²) space even if graph is sparse
2) Adjacency List
Each vertex stores a list of its neighbors.
Advantages:
Space-efficient: O(V + E)
Best for sparse graphs
Disadvantages:
Slower to check if an edge exists — O(k) where k = number of neighbors

Graph Traversal Algorithms:

Two main traversal techniques:
1. Breadth First Search (BFS)
2. Depth First Search (DFS)
1) Breadth First Search (BFS):
Step-1 : Visit start vertex and put it into the Queue (FIFO). Mark it as visited.
Step-2 : Remove a vertex from queue, visits its unvisited adjacent vertices, put newly visited
vertices into the queue.

CSE(AI&ML) 4
Step-3 : Repeat until queue is empty.
2) Depth First Search (DFS):
Step-1 : Visit start vertex and put it into the Stack (LIFO). Mark it as visited.
Step-2 : Visit any adjacent unvisited vertex, mark it as visited, and put it into the Stack.
Step-3 : Continue step-2 until no adjacent vertex is found, pop up a vertex from stack.
Step-4 : Repeat until stack is empty.

Graph ADT:
A Graph Abstract Data Type (ADT) is a non-linear conceptual model that defines a collection of
entities (vertices) and the relationships (edges) between them.
It focuses on what operations can be performed on the data rather than how they are
implemented.
graph(): Creates a new, empty graph
add_vertex(v): Adds a new vertex ‘v’ to the graph.
remove_vertex(v): Removes vertex ‘v’ and all its incident edges.
add_edge(u, v, weight): Adds a connection between vertices ‘u’ and ‘v’, optionally with a weight.
remove_edge(u, v): Removes the connection between ‘u’ and ‘v’.
adjacent(u, v): Checks if there is a direct edge from ‘u’ to ‘v’.
neighbors(v): Returns a list of all vertices connected directly to vertex ‘v’.
get_vertex_value(v) / set_vertex_value(v, val): Retrieves or modifies data associated with a
vertex.

Applications of Graph:
Graphs are a concept that can be found in any field of technology that we use daily without
realizing it:
• Social Networks: The vertices correspond to the users, and the edges represent the
relationships. Communities, influencers, and content recommendation are identified by
an algorithm.
• Computer Networks: Routers and switches are the nodes; connections are the edges.
Graph algorithms are used to route optimally, detect faults, and plan changes.
• Search Engines: Web pages are nodes, and hyperlinks are edges. Google's PageRank
algorithm applies the graph model to rank pages.
• Transportation Systems: Cities or intersections are vertices, and roads are edges. The
shortest path, traffic flow, and route planning problems are solved by graph algorithms.
• Recommendation Systems: Graphs represent users and products; edges indicate
interactions. Algorithms predict user preferences.
• Biology: Proteins, genes, and molecules are nodes; their interactions are edges. Graphs
help in understanding molecular pathways, disease networks, and drug discovery.

CSE(AI&ML) 5
 • AI and Machine Learning: Knowledge graphs are the main characters/entities and the
relationships between them, thus helping natural language understanding, question
answering, and reasoning.
• Game Development: Graphs represent maps, levels, or decision trees for AI pathfinding
and strategic planning.

Bi Connected Components:
• A graph G is said to be Bi Connected qif it is a connected and it contains no “Articulation
Point”.
Articulation Point :
Let G=(V,E) be a connected undirected graph, then an articulation point of graph G is a
vertex whose removal disconnects graph G. This articulation point is a kind of cut vertex.

Sorting:
Sorting is the process of arranging data in a specific order, usually:
Ascending order (small → big) or Descending order (big → small)
Sorting helps in:
• Faster searching
• Better data organization
• Efficient processing (binary search, merging, etc.)

Sorting techniques:
List of Sorts:
1. Bubble Sort
2. Insertion Sort
3. Selection Sort
5. Merge Sort
6. Quick Sort
7. Heap Sort
8. Radix Sort / Bucket Sort
9. Shell Sort
10. Tree Sort
11. Counting Sort
12. External Sort

CSE(AI&ML) 6
Heap Sort:
Priority Queues:
• It is a collection of zero or more elements.
• Each element has a priority.
• There are 2 types of priority queues :
1. Max priority queue.
2. Min priority queue.
• In max priority queue the maximum element remove first.
• In min priority queue the minimum element remove first.

Heap : Binary Heap:

• Heap is a representation of priority queues
• It is always complete binary tree.
• There are 2 types of heaps:
1. Max heap.
2. Min heap.

Max Heap:
• Every node in the tree is greater than its child nodes.
• For every node ‘i’ the value of node is less than or equals to its parent node.(except root
node)
A[parent(i)] >= A[i]
• For parent : i/2
• For left child : 2*I
• For right child (2*i)+1

Min Heap:
• Every node in the tree is less than its child nodes.
• For every node ‘i’ the value of node is greater than or equals to its parent node.(except
root node)
A[parent(i)] <= A[i]
• For parent : i/2
• For left child : 2*I
• For right child (2*i)+1

Operations:
• Insertion

CSE(AI&ML) 7
 • Deletion
• Searching
• Peek / Get root
• Heapify

Insertion (for both max and min):

Step-1 : Create a hole (or) an empty node at the next available position in complete binary tree.
Step-2 : If the element can be placed in the hole by satisfying the heap property and insert it.
Step-3 : Otherwise hole’s parent will be inserted in the hole, and the element to be inserted is
moved up.
Step-4 : Repeat step 2 & 3 by bubbling up the element from leaf to root.
Time Complexity: O(log n)

Deletion of max heap:

• For deleting the elements from the max heap, first we can delete the root element and
adjust the elements of it’s child’s.
• If you want to delete the element from max heap, the first element deleted is the root,
then remove the last element in that, and place it it’s root hole, and satisfying the max
heap property, you can heapify.
Time Complexity: O(log n)
Deletion of min heap:
• For deleting the elements from the min heap, first we can delete the root element and
adjust the elements of it’s child’s.
• If you want to delete the element from min heap, the first element deleted is the root
then remove the last element in that, and place it it’s root hole, and satisfying the min
heap property, you can heapify.
Time Complexity: O(log n)

Applications of heap tree:

1. Building the heap tree
2. Sorting the heap tree
1) Building the heap tree :
1. Take the first element.
2. Take the next element and compare with it’s parent and exchange the elements
– if parent is less than the child (in case of max heap)
– if parent is greater than the child (in case of min heap)
3. Repeat the steps 1 & 2 until all elements are completed.
2) Sorting the heap tree :

CSE(AI&ML) 8
1) Build a heap tree with given data.
2 a) Delete root node from heap.
b) Rebuild the heap tree after the deletion.
c) Place the deleted element in the output.
3) Continue step 2 until the heap tree become empty.

Difference between Max & Min heap:

Feature Max Heap Min Heap

Root contains Maximum value Minimum value

Use case Priority for largest Priority for smallest

Comparison direction Parent ≥ Children Parent ≤ Children

Advantages:
• Time complexity: O(n log n) (all cases)
• In-place (no extra memory)
• No worst-case slowdown
• Good for large datasets
Disadvantages:
• Not stable
• Slower than Quick/Merge Sort in practice
• Not adaptive (doesn’t use sorted data)
• Poor cache performance
Time complexities:
Operation Time Complexity Explanation

New element may move up

Insertion O(log n)
the tree (height = log n).

After removing root, heapify-

Deletion (root delete) O(log n)
down takes log n time.

Heap is not sorted, so you

Search (any element) O(n)
may need to check all nodes.

Peek / Get Max or Min (root) O(1) Root is directly accessible.

Heapify (fixing heap after May require traversing heap

O(log n)
update) height.

CSE(AI&ML) 9
 Building a Heap from an Array O(n) Efficient bottom-up heapify.

Build heap (O(n)) + remove n

Heap Sort O(n log n)
times (n log n).

Space Complexity O(n) Stores all n elements.

Radix Sort:
• Radix sort is the linear sorting algorithm that is used for integers.
• In radix sort, there is digit by digit sorting is performed i.e., started from the least
significant bit to most significant bit.
• The process of radix sort works similar to the sorting of students names according to the
alphabetical order.
Steps:
1. Find the maximum number → determines number of digits
2. Start with units place (1’s digit)
3. Sort numbers using Counting Sort
4. Move to next digit (10’s, 100’s, …)
5. Repeat until all digits are processed
Examples:
• 181, 289, 390,121, 145, 736, 514, 212
• 15, 1, 321, 10, 802, 2, 123, 90, 109, 11
• 170, 45, 75, 90, 802, 24, 2, 66
Advantages
• Faster than comparison sorts when k is small
• Linear time complexity for fixed digit length
• Stable sorting algorithm
• Ideal for large datasets of integers
Disadvantages
• Uses extra memory (not in-place)
• Not suitable for floating-point numbers
• Performance depends on number of digits
Time Complexity:
Case Complexity

Best Case O(nk)

Average O(nk)

CSE(AI&ML) 10
 Worst
O(nk)
Case
Where:
n = number of elements
k = number of digits

Shell Sort:
• Shell sort is the generalization of insertion sort, which overcomes the drawbacks of
insertion sort by comparing elements separated by a gap of several positions.
• It is a sorting algorithm that is an extended version of insertion sort. Shell sort has
improved the average time complexity of insertion sort. As similar to insertion sort, it is a
comparison based and in-place sorting algorithm. Shell sort is efficient for medium sized
data sets.
• In insertion sort, at a time elements can be moved ahead by one position only. To move
an element to a far away position, many elements are required that increase the
algorithms execution time. But shell sort overcomes this drawback of insertion sort. It
allows the moment and swapping of far way elements as well.
• This algorithm first sorts the elements that are far away from each other, then it
subsequently reduces the gap between them. This gap is called as “interval”.
• Shell Sort is an improved version of Insertion Sort that allows the exchange of far-apart
elements to reduce the total number of shifts.
• Proposed by Donald Shell in 1959
• Works by sorting elements at specific intervals (gaps)
• Gradually reduces the gap until it becomes 1 (then behaves like insertion sort)
Key Points:
Instead of comparing adjacent elements (like insertion sort), Shell Sort:
1. Divides the list into sublists using a gap
2. Sorts those sublists
3. Reduces the gap
4. Repeats until gap = 1
Steps:
• Choose initial gap = n/2
• Compare elements gap distance apart
• Perform insertion sort on those elements
• Reduce gap (gap = gap/2)
• Repeat until gap = 1
Examples:

CSE(AI&ML) 11
 • 33, 31, 40, 8, 12, 17, 25, 42
• 35, 33, 42, 10, 14, 19, 27, 44
• 23, 29, 15, 19, 31, 7, 9, 5, 2
Advantages:
• Faster than Insertion Sort
• Efficient for medium-sized datasets
• Reduces large movements early
• In-place sorting (no extra memory)
Disadvantages
• Not stable (equal elements may change order)
• Performance depends on gap sequence
• Not as fast as Quick Sort or Merge Sort for large data

Time Complexity:
Case Complexity

Best Case O(n log n)

O(n log n) (depends on gap

Average
sequence)

Worst Case O(n²)

Tree Sort:
Tree Sort is a sorting algorithm that uses a Binary Search Tree (BST) to sort elements.
Steps:
1. Create an empty BST
2. Insert all elements one by one
3. Perform inorder traversal
4. Store or print elements
Examples:
Advantages
• Produces sorted order naturally
• Easy to implement using BST
• Useful when data is inserted dynamically
Disadvantages
• Worst case O(n²) (if tree becomes skewed)
• Requires extra memory (not in-place)
• Slower than efficient sorts like Quick/Merge Sort

CSE(AI&ML) 12
 Unit-5
Hashing and Collision, Files and their Organization
Hashing and Collision: Introduction, Hash Tables, Hash Functions, Different Hash Functions:
Division Method, Multiplication Method, Mid-square Method, Folding Method;
collisions: Collision Resolution by Open Addressing, Collision Resolution by Chaining

Files and their Organization: Introduction, Data hierarchy, File Attributes, Text and Binary Files,
Basic File Operations, File Organization, Indexing

Introduction:
• Dictionary is one of the important Data Structures that is usually used to store data.
• A dictionary is defined as a general-purpose data structure for storing a group of objects.
• A dictionary is associated with a set of keys and each key has a single associated value.
When presented with a key, the dictionary will simply return the associated value.
• Other names for the Dictionary data structure are associative array, map, symbol table
but broadly it is referred to as Dictionary.

• In Dictionary, the relation between the key and the value is known as the mapping. We
can say that each value in the dictionary is mapped to a particular key present in the
dictionary or vice-versa.
• A dictionary in data structure is used to store the data in the form of key-value pair.

• The dictionary in data structure has an attribute called the key.

• The key is the attribute that helps us locate the data or value in the memory.
• The keys are always unique within a dictionary.
• The dictionary in data structure is usually created using the curly braces as {key: value(s)}.
• Now, the dictionary's key-value pair is first converted into some hash value (using a hash
function). This hash code is then stored in buckets in the memory. The hash code helps in
faster data retrieval as they are always unique.
• A key attribute of the dictionary in data structure follows two rules.

1) The key attribute of the dictionary data structure must be unique and consist of a single
element. (the unique nature helps us in faster and easy retrieval of the corresponding set
of values)

CSE(AI&ML) 1
 2) As no duplicate keys are allowed in the dictionary data structure, whenever a
duplicate key is found, the last assigned value is treated as the final key-value pair. So, if
we insert duplicate keys then our original data is lost.
• C programming language does not provide any direct implementation of Map or
Dictionary Data structure. However, it doesn’t mean we cannot implement one.
• Dictionary can be implemented using arrays, lists, hashing, trees, and tries.

Implementation of dictionary using hashing:

• Hash Table: Hash table is one of the most important data structures that uses a special
function known as a hash function that maps a given value with a key to access the
elements faster.
• It is the efficient method of implementing dictionaries.

• It is one of the data structure to store the pairs (key element,element).

• Each and every position in hash table is treated as a “bucket”.
• It is used to hold (key,value) pair.
• [Link] buckets in hash table equals to the size of the table or array size.
• The hash table is indexed from 0 to table size -1.

Hash table:

CSE(AI&ML) 2
Hashing:
• The process of mapping the key with respective position in the hash table is called
“hashing”.

Hash Function:
• Hash function is one of the mathematical function to insert the element into the hash
table.
• A function h(k) is a mathematical function which calculates the position of ‘k’ in a hash
table.

• The integer value returned by hash function is called hash key.

Methods for creating hash function:

1) Division method.
2) Multiplication method.
3) Mid-square method.

4) Folding method.
5) Truncation method.
6) Extraction / digit analysis method.
1) Division method:
• It is one of the most accepted hash function.

h(k)=key % size
Note: Normally table size chosen as a prime number , but our convenient we can take the table
size as ‘10’.
Advantages:
• Simple to implement.
• Works well when ‘m’ is a prime number.
Disadvantages:

• Poor distribution if ‘m’ is not chosen wisely.

Ex: Consider the elements 84,62,51,96,98,87, are placed in a hash table
Sol: Table size = 10

CSE(AI&ML) 3
 h(k)=key%size
h(84)=84%10=4
h(62)=62%10=2

h(51)=51%10=1
h(96)=96%10=6
h(98)=98%10=8
h(87)=87%10=7

2) Multiplication method:
• The multiplication method for hashing computes a hash value by multiplying a key by a
constant A(0 < A < 1), extracting the fractional part of the product, and multiplying that
by the table size ‘m’.
• The formula is generally : h(k)=⌊m * ((k * A) % 1)⌋
Key Points:
• Multiply key k with a constant A (0 < A < 1)
• Take only the fractional part (ignore integer part)

• Multiply that by table size (m)

• Take floor value (integer part) → that is index
Advantages:
• Provides better distribution in many cases.

CSE(AI&ML) 4
 • Less sensitive to table size.
Disadvantages:
• Slightly more complex to compute.

Examples:
• k = 50, A = 0.6, m = 10
• k = 123, A = 0.618, m = 10
• k = 25, A = 0.7, m = 10
Hash function: h(k)=⌊m * ((k * A) % 1)⌋

• k = 50, A = 0.6, m = 10
h(50)=⌊10 * ((50 * 0.6) % 1)⌋ = ⌊10 * 0.0)⌋ = 0
• k = 123, A = 0.618, m = 10
h(123)=⌊10 * ((123 * 0.618) % 1)⌋ = ⌊10 * 0.014)⌋ = 0
• k = 25, A = 0.7, m = 10

h(25)=⌊10 * ((25 * 0.7) % 1)⌋ = ⌊10 * 0.5)⌋ = 5

3) Mid-square method:
• In mid-square method,
the hash function is defined by h(k) = x,
Where ‘x’ is obtained by selecting an appropriate number from the middle of the square
of the key value ‘k’.
• Based on the size of the hash table ‘x’ value is decided.

• Suppose,
Size = 10,then x will be 1 digit number
Size = 100,then x will be 2 digit number
Size = 1000,then x will be 3 digit number

Ex:- k=40
k^2=40*40=1600

CSE(AI&ML) 5
 h(k)=60.
Advantages:
• Produces a good distribution of hash values.

Disadvantages:
• May require more computational effort.
4) Folding method:
Partition the key into several pieces. Each of the individual parts is combined using any of
the basic arithmetic operations such as addition.
h(k)=k1+k2+k3+- - - - - - -kn
a) Fold shifting method: In this method, the key is broken into segments, and the segments
are simply added together as they are.

Ex:- K=01522756 size=100

K= 01|52|27|56
k1 k2 k3 k4
01+52+27+56=136
h(01522756)=36

b) Fold boundary method:- In this method , Every other segment (typically the first and last
(or) all even-numbered segments) is reversed before addition.

Ex:- K=01522756 size=100

K= 01|52|27|56
k1 k2 k3 k4
10+52+27+65=145
h(01522756)=45

Ex:- K=01522756 size=100

K= 01|52|27|56
k1 k2 k3 k4
01+25+27+65=118
h(01522756)=18

CSE(AI&ML) 6
 Collision:
• The situation in which the hash function returns the same value for more than one
element (or) key.
(or)
• If the key values are mapped with same home bucket then we can get the problem. This
problem is called as ‘collision’.

Ex: 84, 62, 51, 96, 98, 87, 54, 21

CSE(AI&ML) 7
 Collision resolution techniques:
There are two types of collision resolution techniques.
1) Separate chaining (open hashing)

2) Open addressing (closed hashing)

1) Separate chaining:
The hash table is implemented as an array of linked list. Each bucket contains a pointer to
linked list. This method places all the values in the hashes to the same value in its bucket by
a linked list.
Ex: 84, 62, 51, 96, 87, 98, 66, 17, 12
Advantages:
• Collision resolution is simple and efficient.
• We can add more [Link] elements to the chain, table never fill up.

• We can delete the elements, easily.

• The keys of the object to be hash, need not to be unique.
Disadvantages:
• It requires the implementation of a separate data structure for linked list.
• Wastage of space, it uses extra space for links.

• In some languages, creating nodes is expensive and slow down the system
• Direct access of key element is not possible.
• It takes extra execution time.

CSE(AI&ML) 8
 2) Open addressing:
Algorithm:-
1) Find the location at which the element to be inserted.

L= h(key element).
2) If the location is not occupied then insert the element.
3) If the location is occupied find another location using probe sequence and repeat step 2
and step 3.
4) End (or) stop.
The following techniques are used in open addressing:
i. Linear probing

ii. Quadratic probing

iii. Double hashing

i) Linear Probing:
• This technique will resolve hash collision of values by searching the hash table
sequentially for a free location i.e., whenever the collisions occurs the key element can
insert the next free bucket.
if collision not occurs : h(k)= key % size
if collision occurs : h(k)= (key+f(i)) % size

where f(i)=i
• Ex : 52, 36, 74, 82, 76, 32
Disadvantages
• Each element would probe exactly the same partition as its predecessors - Primary
clustering.
• The entries in the hash table are not random, it is continuous fill. It is called primary
clustering.

CSE(AI&ML) 9
 ii) Quadratic Probing:
• It is the another method to resolve the collision in hash table.
• It operates by taking the original hash value and adding successive value of the quadratic
polynomial of h(x).
• It avoids primary clustering (grouping of elements).

• In general, this method probes the bucket at location

if collision not occurs : h(k)= key % size
if collision occurs : h(k)= (key+f(i)) % size
where f(i)=i2
• Ex: 52, 36, 74, 82, 76, 32

Disadvantages
• Although it eliminates the primary clustering, two elements that has same position will
probe the alternate cell position. This is known as Secondary clustering (not group of
elements).
• There is no guarantee for finding an empty cell once the table get more than half full, if
the table is small size.

CSE(AI&ML) 10
 iii) Double hashing:
• Double hashing is a technique used in data structures, particularly in hash tables, to
resolve collisions that occur when multiple keys map to the same hash table index.
• In double hashing, two different hash functions are used to calculate the hash key value
to probe for the next available slot when a collision occurs.
if collision not occurs : h1(k)= key % size

if collision occurs : h2(k)= P - (key % P)

where ‘P’ is the prime number smaller than the size of the table.
After calculating h2(k), We have to insert the element by making h2(k) jumps from the
collision occurred position.
Ex: 89, 18, 49, 58, 69

CSE(AI&ML) 11
 Rehashing:
• Rehashing is the process of increasing the size of a hash table and redistributing the
elements to new buckets based on their new hash values. It is done to improve the
performance of the hash table and to prevent collisions caused by a high load factor.
Reasons for Rehashing:
• Rehash as soon as table is half filled.

• Rehash when insertion fails.

• Rehash when table reaches certain load factor.
• In this technique the table is resized, that is size of the hash table is double by creating a
new table.
• It is preferred, if the size of the table is prime number.
• If the table gets filled, the running time for the operation will take too long and the
insertion might fail for open addressing with quadratic probing.
• A solution is to build another table that is twice big as the original table.
• Scan down the original table.

• Compute the new hash function for each element and insert them with the new table,
the above process is called as "Rehashing".
Ex: 13, 15, 24, 6, 23
Sol: Table size=7 because we have 5 elements, the nearest prime number is 7.

CSE(AI&ML) 12
 Files and their organization
Introduction:
• Now a days, most organizations use data collection applications which collect large
amounts of data in one form or other.
• For example, when we seek admission in a college, a lot of data such as our name,
address, phone number, the course in which we want to seek admission, aggregate of
marks obtained in the last examination, and so on, are collected.
• Similarly, to open a bank account, we need to provide a lot of input. All these data were
traditionally stored on paper documents, but handling these documents had always been
a chaotic and difficult task.
• Similarly, scientific experiments and satellites also generate enormous amounts of data.
• Therefore, in order to efficiently analyse all the data that has been collected from
different sources, it has become a necessity to store the data in computers in the form of
files.
• In computer terminology, a file is a block of useful data which is available to a computer
program and is usually stored on a persistent storage medium. Storing a file on a
persistent storage medium like hard disk ensures the availability of the file for future use.
• These days, files stored on computers are a good alternative to paper documents that
were once stored in offices and libraries.

CSE(AI&ML) 13
 Data hierarchy:
Every file contains data which can be organized in a hierarchy to present a systematic
organization. The data hierarchy includes data items such as fields, records, files, and
database. These terms are defined below.
• A data field is an elementary unit that stores a single fact. A data field is usually
characterized by its type and size. For example, student’s name is a data field that stores
the name of students. This field is of type character and its size can be set to a maximum
of 20 or 30 characters depending on the requirement.
• A record is a collection of related data fields which is seen as a single unit from the
application point of view. For example, the student’s record may contain data fields such
as name, address, phone number, roll number, marks obtained, and so on.
• A file is a collection of related records. For example, if there are 60 students in a class,
then there are 60 records. All these related records are stored in a file. Similarly, we can
have a file of all the employees working in an organization, a file of all the customers of a
company, a file of all the suppliers, so on and so forth.

• A directory stores information of related files. A directory organizes information so that

users can find it easily.
• Fig. 16.1 that shows how multiple related files are stored in a student directory.

CSE(AI&ML) 14
 File attributes:
• Every file in a computer system is stored in a directory. Each file has a list of attributes
associated with it that gives the operating system and the application software
information about the file and how it is intended to be used.
• A software program which needs to access a file looks up the directory entry to discern
the attributes of that file. For example, if a user attempts to write to a file that has been
marked as a read-only file, then the program prints an appropriate message to notify the
user that he is trying to write to a file that is meant only for reading.
• Similarly, there is an attribute called hidden. When you execute the DIR command in DOS,
then the files whose hidden attribute is set will not be displayed. These attributes are
explained in this section.
• File name: It is a string of characters that stores the name of a file. File naming
conventions vary from one operating system to the other.
• File position: It is a pointer that points to the position at which the next read/write
operation will be performed.
• File structure: It indicates whether the file is a text file or a binary file. In the text file, the
numbers (integer or floating point) are stored as a string of characters. A binary file, on
the other hand, stores numbers in the same way as they are represented in the main
memory.
• File Access Method: It indicates whether the records in a file can be accessed sequentially
or randomly. In sequential access mode, records are read one by one. That is, if 60 records
of students are stored in the STUDENT file, then to read the record of 39th student, you
have to go through the record of the first 38 students. However, in random access,
records can be accessed in any order.
• Attributes Flag: A file can have six additional attributes attached to it. These attributes
are usually stored in a single byte, with each bit representing a specific attribute. If a
particular bit is set to ‘1’ then this means that the corresponding attribute is turned on.
Table 16.1 shows the list of attributes and their position in the attribute flag or attribute
byte.

CSE(AI&ML) 15
 • If a system file is set as hidden and read-only, then its attribute byte can be given as
00000111. We will discuss all these attributes here in this section. Note that the directory
is treated as a special file in the operating system. So, all these attributes are applicable
to files as well as to directories.
• Read-only: A file marked as read-only cannot be deleted or modified. For example, if an
attempt is made to either delete or modify a read-only file, then a message ‘access
denied’ is displayed on the screen.

• Hidden: A file marked as hidden is not displayed in the directory listing.

• System: A file marked as a system file indicates that it is an important file used by the
system and should not be altered or removed from the disk. In essence, it is like a ‘more
serious’ read-only flag.
• Volume Label: Every disk volume is assigned a label for identification. The label can be
assigned at the time of formatting the disk or later through various tools such as the DOS
command LABEL.
• Directory: In directory listing, the files and sub-directories of the current directory are
differentiated by a directory-bit. This means that the files that have the directory-bit
turned on are actually sub-directories containing one or more files.

• Archive: The archive bit is used as a communication link between programs that modify
files and those that are used for backing up files. Most backup programs allow the user to
do an incremental backup. Incremental backup selects only those files for backup which
have been modified since the last backup.

CSE(AI&ML) 16
 When the backup program takes the backup of a file, or in other words, when the
program archives the file, it clears the archive bit (sets it to zero). Subsequently, if any
program modifies the file, it turns on the archive bit (sets it to 1). Thus, whenever the
backup program is run, it checks the archive bit to know whether the file has been
modified since its last run. The backup program will archive only those files which were
modified.

CSE(AI&ML) 17
 Text and binary files:
There are two types of computer files—text files and binary files.
A text file, also known as a flat file or an ASCII file, is structured as a sequence of lines of
alphabet, numerals, special characters, etc. However, the data in a text file, whether numeric
or non-numeric, is stored using its corresponding ASCII code. The end of a text file is often
denoted by placing a special character, called an end-of-file marker, after the last line in the
text file.
A binary file contains any type of data encoded in binary form for computer storage and
processing purposes. A binary file can contain text that is not broken up into lines. A binary
file stores data in a format that is similar to the format in which the data is stored in the main
memory.
• Therefore, a binary file is not readable by humans and it is up to the program reading the
file to make sense of the data that is stored in the binary file and convert it into something
meaningful (e.g., a fixed length of record).
• Binary files contain formatting information that only certain applications or processors
can understand. It is possible for humans to read text files which contain only ASCII text,
while binary files must be run on an appropriate software or processor so that the
software or processor can transform the data in order to make it readable. For example,
only Microsoft Word can interpret the formatting information in a Word document.
• Although text files can be manipulated by any text editor, they do not provide efficient
storage. In contrast, binary files provide efficient storage of data, but they can be read
only through an appropriate program.

CSE(AI&ML) 18
 Basic file operations:
The basic operations that can be performed on a file are given in Fig. 16.2.

Creating a File: A file is created by specifying its name and mode. Then the file is opened for
writing records that are read from an input device. Once all the records have been written
into the file, the file is closed. The file is now available for future read/write operations by any
program that has been designed to use it in some way or the other.
Updating a File: Updating a file means changing the contents of the file to reflect a current
picture of reality. A file can be updated in the following ways:
• Inserting a new record in the file. For example, if a new student joins the course, we need
to add his record to the STUDENT file.
• Deleting an existing record. For example, if a student quits a course in the middle of the
session, his record has to be deleted from the STUDENT file.
• Modifying an existing record. For example, if the name of a student was spelt incorrectly,
then correcting the name will be a modification of the existing record.
Retrieving from a File: It means extracting useful data from a given file. Information can be
retrieved from a file either for an inquiry or for report generation. An inquiry for some data
retrieves low volume of data, while report generation may retrieve a large volume of data
from the file.
Maintaining a File: It involves restructuring or re-organizing the file to improve the
performance of the programs that access this file.
• Restructuring a file keeps the file organization unchanged and changes only the structural
aspects of the file (for example, changing the field width or adding/deleting fields).
• On the other hand, file reorganization may involve changing the entire organization of the
file. We will discuss file organization in detail in the next section.

CSE(AI&ML) 19
 File organization:
We know that a file is a collection of related records. The main issue in file management
is the way in which the records are organized inside the file because it has a significant effect
on the system performance. Organization of records means the logical arrangement of
records in the file and not the physical layout of the file as stored on a storage media.
Since choosing an appropriate file organization is a design decision, it must be done
keeping the priority of achieving good performance with respect to the most likely usage of
the file. Therefore, the following considerations should be kept in mind before selecting an
appropriate file organization method:
• Rapid access to one or more records
• Ease of inserting/updating/deleting one or more records without disrupting the speed of
accessing record(s)
• Efficient storage of records
• Using redundancy to ensure data integrity
Although one may find that these requirements are in contradiction with each other, it is
the designer’s job to find a good compromise among them to get an adequate solution for
the problem at hand. For example, the ease of addition of records can be compromised to
get fast access to data. In this section, we will discuss some of the techniques that are
commonly used for file organization.
1. Sequential Organization
2. Relative File Organization

3. Indexed Sequential File Organization

1. Sequential Organization
A sequentially organized file stores the records in the order in which they were entered.
That is, the first record that was entered is written as the first record in the file, the second
record entered is written as the second record in the file, and so on. As a result, new records
are added only at the end of the file.
Sequential files can be read only sequentially, starting with the first record in the file.
Sequential file organization is the most basic way to organize a large collection of records in
a file. Figure 16.3 shows n records numbered from 0 to n–1 stored in a sequential file.

CSE(AI&ML) 20
 Once we store the records in a file, we cannot make any changes to the records. We
cannot even delete the records from a sequential file. In case we need to delete or update
one or more records, we have to replace the records by creating a new file.
In sequential file organization, all the records have the same size and the same field
format, and every field has a fixed size. The records are sorted based on the value of one field
or a combination of two or more fields. This field is known as the key. Each key uniquely
identifies a record in a file. Thus, every record has a different value for the key field. Records
can be sorted in either ascending or descending order.
Sequential files are generally used to generate reports or to perform sequential reading
of large amount of data which some programs need to do such as payroll processing of all the
employees of an organization. Sequential files can be easily stored on both disks and tapes.
Table 16.2 summarizes the features, advantages, and disadvantages of sequential file
organization.

CSE(AI&ML) 21
 [Link] File Organization
Relative file organization provides an effective way to access individual records directly.
In a relative file organization, records are ordered by their relative key. It means the record
number represents the location of the record relative to the beginning of the file. The record
numbers range from 0 to n–1, where n is the number of records in the file. For example, the
record with record number 0 is the first record in the file. The records in a relative file are of
fixed length.

Therefore, in relative files, records are organized in ascending relative record number. A
relative file can be thought of as a single dimension table stored on a disk, in which the

CSE(AI&ML) 22
 relative record number is the index into the table. Relative files can be used for both random
as well as sequential access. For sequential access, records are simply read one after another.
Relative files provide support for only one key, that is, the relative record number. This
key must be numeric and must take a value between 0 and the current highest relative record
number –1. This means that enough space must be allocated for the file to contain the
records with relative record numbers between 0 and the highest record number –1. For
example, if the highest relative record number is 1,000, then space must be allocated to store
1,000 records in the file.

Figure 16.4 shows a schematic representation of a relative file which has been allocated
enough space to store 100 records. Although it has space to accommodate 100 records, not
all the locations are occupied. The locations marked as FREE are yet to store records in them.
Therefore, every location in the table either stores a record or is marked as FREE.
Relative file organization provides random access by directly jumping to the record which
has to be accessed. If the records are of fixed length and we know the base address of the file
and the length of the record, then any record i can be accessed using the following formula:
Address of ith record = base_address + (i–1) * record_length

Note that the base address of the file refers to the starting address of the file. We took i–
1 in the formula because record numbers start from 0 rather than 1.

Consider the base address of a file is 1000 and each record occupies 20 bytes, then the
address of the 5th record can be given as:

1000 + (5–1) * 20
= 1000 + 80
= 1080
Table 16.3 summarizes the features, advantages, and disadvantages of relative file
organization.

CSE(AI&ML) 23
 [Link] Sequential File Organization
Indexed sequential file organization stores data for fast retrieval. The records in an indexed
sequential file are of fixed length and every record is uniquely identified by a key field. We
maintain a table known as the index table which stores the record number and the address
of all the records. That is for every file, we have an index table.
This type of file organization is called as indexed sequential file organization because
physically the records may be stored anywhere, but the index table stores the address of
those records.

CSE(AI&ML) 24
 The ith entry in the index table points to the ith record of the file. Initially, when the file is
created, each entry in the index table contains NULL. When the ith record of the file is written,
free space is obtained from the free space manager and its address is stored in the ith location
of the index table.
Now, if one has to read the 4th record, then there is no need to access the first three
records. Address of the 4th record can be obtained from the index table and the record can
be straightaway read from the specified address (742, in our example). Conceptually, the
index sequential file organization can be visualized as shown in Fig. 16.5.

An indexed sequential file uses the concept of both sequential as well as relative files.
While the index table is read sequentially to find the address of the desired record, a direct
access is made to the address of the specified record in order to access it randomly.

Indexed sequential files perform well in situations where sequential access as well as
random access is made to the data. Indexed sequential files can be stored only on devices
that support random access, for example, magnetic disks.
For example, take an example of a college where the details of students are stored in an
indexed sequential file.

This file can be accessed in two ways:

Sequentially—to print the aggregate marks obtained by each student in a particular course
or
Randomly—to modify the name of a particular student.
Table 16.4 summarizes the features, advantages, and disadvantages of indexed sequential
file organization.

CSE(AI&ML) 25
 Indexing:
An index for a file can be compared with a catalogue in a library. Like a library has card
catalogues based on authors, subjects, or titles, a file can also have one or more indices.
Indexed sequential files are very efficient to use, but in real-world applications, these files
are very large and a single file may contain millions of records. Therefore, in such situations,
we require a more sophisticated indexing technique. There are several indexing techniques
and each technique works well for a particular application. For a particular situation at hand,
we analyse the indexing technique based on factors such as access type, access time,
insertion time, deletion time, and space overhead involved.
There are two kinds of indices:
• Ordered indices that are sorted based on one or more key values.
• Hash indices that are based on the values generated by applying a hash function
1. Ordered Indices

2. Dense and Sparse Indices

3. Cylinder Surface Indexing
4. Multi-level Indices
5. Inverted Indices
6. B-Tree Indices

7. Hashed Indices
[Link] Indices
Indices are used to provide fast random access to records. As stated above, a file may have
multiple indices based on different key fields.
An index of a file may be a primary index or a secondary index.
Primary Index: In a sequentially ordered file, the index whose search key specifies the
sequential order of the file is defined as the primary index. For example, suppose records of
students are stored in a STUDENT file in a sequential order starting from roll number 1 to roll
number 60. Now, if we want to search a record for, say, roll number 10, then the student’s
roll number is the primary index. Indexed sequential files are a common example where a
primary index is associated with the file.
Secondary Index An index whose search key specifies an order different from the sequential
order of the file is called as the secondary index. For example, if the record of a student is

CSE(AI&ML) 26
 searched by his name, then the name is a secondary index. Secondary indices are used to
improve the performance of queries on non-primary keys.
2. Dense and Sparse Indices
In a dense index, the index table stores the address of every record in the file. However,
in a sparse index, the index table stores the address of only some of the records in the file.
Although sparse indices are easy to fit in the main memory, a dense index would be more
efficient to use than a sparse index if it fits in the memory. Figure 16.6 shows a dense index
and a sparse index for an indexed sequential file.
The following Figures a dense index and a sparse index for an indexed sequential file.

Note that the records need not be stored in consecutive memory locations. The pointer to
the next record stores the address of the next record.

By looking at the dense index, it can be concluded directly whether the record exists in
the file or not. This is not the case in a sparse index. In a sparse index, to locate a record, we
first find an entry in the index table with the largest search key value that is either less than
or equal to the search key value of the desired record. Then, we start at that record pointed
to by that entry in the index table and then proceed searching the record using the sequential
pointers in the file, until the desired record is obtained. For example, if we need to access
record number 40, then record number 30 is the largest key value that is less than 40. So
jump to the record pointed by record number 30 and move along the sequential pointer to
reach record number 40.
Thus we see that sparse index takes more time to find a record with the given key. Dense
indices are faster to use, while sparse indices require less space and impose less maintenance
for insertions and deletions.

3. Cylinder Surface Indexing

Cylinder surface indexing is a very simple technique used only for the primary key index
of a sequentially ordered file. In a sequentially ordered file, the records are stored
sequentially in the increasing order of the primary key. The index file will contain two fields—

CSE(AI&ML) 27
 cylinder index and several surface indices. Generally, there are multiple cylinders, and each
cylinder has multiple surfaces. If the file needs m cylinders for storage then the cylinder index
will contain m entries.
Each cylinder will have an entry corresponding to the largest key value into that cylinder.
If the disk has n usable surfaces, then each of the surface indices will have n entries.
Therefore, the ith entry in the surface index for cylinder j is the largest key value on the j th
track of the ith surface. Hence, the total number of surface index entries is m.n.
The physical and logical organization of disk is shown in Fig. 16.7.

Note: The number of cylinders in a disk is only a few hundred and the cylinder index occupies
only one track.
When a record with a particular key value has to be searched, then the following steps are
performed:
• First the cylinder index of the file is read into memory.

• Second, the cylinder index is searched to determine which cylinder holds the desired
record. For this, either the binary search technique can be used or the cylinder index can
be made to store an array of pointers to the starting of individual key values. In either
case the search will take O (log m) time.
• After the cylinder index is searched, appropriate cylinder is determined.

• Depending on the cylinder, the surface index corresponding to the cylinder is then
retrieved from the disk.
• Since the number of surfaces on a disk is very small, linear search can be used to
determine surface index of the record.

CSE(AI&ML) 28
 • Once the cylinder and the surface are determined, the corresponding track is read and
searched for the record with the desired key.
Hence, the total number of disk accesses is three—first, for accessing the cylinder index,
second for accessing the surface index, and third for getting the track address. However, if
track sizes are very large then it may not be a good idea to read the whole track at once. In
such situations, we can also include sector addresses. But this would add an extra level of
indexing and, therefore, the number of accesses needed to retrieve a record will then become
four. In addition to this, when the file extends over several disks, a disk index will also be
added.
The cylinder surface indexing method of maintaining a file and index is referred to as
Indexed Sequential Access Method (ISAM). This technique is the most popular and simplest
file organization in use for single key values. But with files that contain multiple keys, it is not
possible to use this index organization for the remaining keys.
4. Multi-level Indices
In real-world applications, we have very large files that may contain millions of records.
For such files, a simple indexing technique will not suffice. In such a situation, we use multi-
level indices. To understand this concept, consider a file that has 10,000 records. If we use
simple indexing, then we need an index table that can contain at least 10,000 entries to point
to 10,000 records. If each entry in the index table occupies 4 bytes, then we need an index
table of 4 * 10000 bytes = 40000 bytes. Finding such a big space consecutively is not always
easy. So, a better scheme is to index the index table.
Figure 16.8 shows a two-level multi-indexing. We can continue further by having a three-
level indexing and so on. But practically, we use two-level indexing. Note that two and higher-
level indexing must always be sparse, otherwise multi-level indexing will lose its
effectiveness. In the figure, the main index table stores pointers to three inner index tables.
The inner index tables are sparse index tables that in turn store pointers to the records.

CSE(AI&ML) 29
 [Link] Indices
Inverted files are commonly used in document retrieval systems for large textual
databases. An inverted file reorganizes the structure of an existing data file in order to provide
fast access to all records having one field falling within the set limits.
For example, inverted files are widely used by bibliographic databases that may store
author names, title words, journal names, etc. When a term or keyword specified in the
inverted file is identified, the record number is given and a set of records corresponding to
the search criteria are created.
Thus, for each keyword, an inverted file contains an inverted list that stores a list of
pointers to all occurrences of that term in the main text. Therefore, given a keyword, the
addresses of all the documents containing that keyword can easily be located.
There are two main variants of inverted indices:
• A record-level inverted index (also known as inverted file index or inverted file) stores a
list of references to documents for each word
• A word-level inverted index (also known as full inverted index or inverted list) in addition
to a list of references to documents for each word also contains the positions of each
word within a document. Although this technique needs more time and space, it offers
more functionality (like phrase searches)
Therefore, the inverted file system consists of an index file in addition to a document file
(also known as text file). It is this index file that contains all the keywords which may be used
as search terms. For each keyword, an address or reference to each location in the document
where that word occurs is stored. There is no restriction on the number of pointers associated
with each word.

CSE(AI&ML) 30
 For efficiently retrieving a word from the index file, the keywords are sorted in a specific
order (usually alphabetically).
However, the main drawback of this structure is that when new words are added to the
documents or text files, the whole file must be reorganized. Therefore, a better alternative is
to use B-trees.
6.B-Tree Indices
A database is defined as a collection of data organized in a fashion that facilitates
updating, retrieving, and managing the data (that may include any item, such as names,
addresses, pictures, and numbers). Most organizations maintain databases for their business
operations. For example, an airline reservation system maintains a database of flights,
customers, and tickets issued. A university maintains a database of all its students. These real-
world databases may contain millions of records that may occupy gigabytes of storage space.
For a database to be useful, it must support fast retrieval and storage of data. Since it is
impractical to maintain the entire database in the memory, B-trees are used to index the data
in order to provide fast access.

For example, searching a value in an un-indexed and unsorted database containing n key
values may take a running time of 0(n) in the worst case, but if the same database is indexed
with a B-tree, the search operation will run in O(log n) time.

Majority of the database management systems use the B-tree index technique as the
default indexing method. This technique supersedes other techniques of creating indices,
mainly due to its data retrieval speed, ease of maintenance, and simplicity. Figure 16.9 shows
a B-tree index.
Figure 16.9 shows a B-tree index.

CSE(AI&ML) 31
 It forms a tree structure with the root at the top. The index consists of a B-tree (balanced
tree) structure based on the values of the indexed column. In this example, the indexed
column is name and the B-tree is created using all the existing names that are the values of
the indexed column. The upper blocks of the tree contain index data pointing to the next
lower block, thus forming a hierarchical structure. The lowest level blocks, also known as leaf
blocks, contain pointers to the data rows stored in the table.
If a table has a column that has many unique values, then the selectivity of that column
is said to be high. B-tree indices are most suitable for highly selective columns, but it causes
a sharp increase in the size when the indices contain concatenation of multiple columns.

The B-tree structure has the following advantages:

• Since the leaf nodes of a B-tree are at the same depth, retrieval of any record from
anywhere in the index takes approximately the same time.
• B-trees improve the performance of a wide range of queries that either search a value
having an exact match or for a value within specified range.
• B-trees provide fast and efficient algorithms to insert, update, and delete records that
maintain the key order.
• B-trees perform well for small as well as large tables. Their performance does not degrade
as the size of a table grows.
• B-trees optimize costly disk access.

CSE(AI&ML) 32
 [Link] Indices
So far, we have studied that hashing is used to compute the address of a record by using
a hash function on the search key value. If at any point of time, the hashed values map to the
same address, then collision occurs and schemes to resolve these collisions are applied to
generate a new address.
Choosing a good hash function is critical to the success of this technique. By a good hash
function, we mean two things. First, a good hash function, irrespective of the number of
search keys, gives an average-case lookup that is a small constant. Second, the function
distributes records uniformly and randomly among the buckets, where a bucket is defined as
a unit of one or more records (typically a disk block). Correspondingly, the worst hash function
is one that maps all the keys to the same bucket.

However, the drawback of using hashed indices includes:

• Though the number of buckets is fixed, the number of files may grow with time.
• If the number of buckets is too large, storage space is wasted.
• If the number of buckets is too small, there may be too many collisions.
It is recommended to set the number of buckets to twice the number of the search key
values in the file. This gives a good space–performance tradeoff.
A hashed file organization uses hashed indices. Hashing is used to calculate the address
of disk block where the desired record is stored. If K is the set of all search key values and B
is the set of all bucket addresses, then a hash function H maps K to B.
We can perform the following operations in a hashed file organization.

Insertion: To insert a record that has ki as its search value, use the hash function h(ki ) to
compute the address of the bucket for that record. If the bucket is free, store the record else
use chaining to store the record.
Search: To search a record having the key value ki , use h(ki ) to compute the address of the
bucket where the record is stored. The bucket may contain one or several records, so check
for every record in the bucket (by comparing ki with the key of every record) to finally retrieve
the desired record with the given key value.
Deletion: To delete a record with key value ki , use h(ki ) to compute the address of the bucket
where the record is stored. The bucket may contain one or several records so check for every
record in the bucket (by comparing ki with the key of every record). Then delete the record
as we delete a node from a linear linked list.
Note that in a hashed file organization, the secondary indices need to be organized using
hashing.

CSE(AI&ML) 33