Data Structures

Syllabus
SUBJECT CODE SUBJECT TITLE CORE/ ELECTIVE CREDITS
L T P C
CSE 102 Data Structures C 3 0 2 4

NOTE: The syllabus given herein shall be followed and further additions/deletions are possible
based on the time factor.
Unit I
• Introduction to data structures, Abstract Data Type (ADT) representation and
implementation of ADT, time and space requirements of algorithms.
• Array ADT, representing polynomials, sparse matrices using arrays and their operations.
• Stacks and Queues: Representation and application, implementation of stack and queue
operations.
Unit - II
• Linked lists: Single linked lists, implementation of link list and various operation, Double linked
list and circular list.
Dept. of CSE, SRM University AP 8/3/2021 2
 Syllabus
UNIT – III

Trees: Tree terminology, Binary tree, Binary search tree, Complete Binary Tree
representation, infix to post fix conversion, postfix expression evaluation. General tree, AVL
Tree.

UNIT – IV
Graphs: Graph terminology, Representation of graphs, Path matrix, BFS (breadth first search),
DFS (depth first search), topological sorting, Shortest path algorithms

UNIT – V

• Sorting and Searching techniques:

• Bubble sort, selection sort, Insertion sort, Quick sort, Merge sort, Heap sort, Radix sort,
Heaps & Priority Heaps and Binomial Heaps
• Linear Search and Binary Search methods, Hashing techniques and hash functions.
Dept. of CSE, SRM University AP 8/3/2021 3
 Syllabus
Text Books and other references
Books of Study
1) “Data Structures A Pseudo Approach with C”, Richard F. Gilberg & Behrouz A. Forouzan, Cengage
learning, 2nd edition.

2) “Data structure using C”, Aaron M. Tenenbaum, Y Langsam and Mosche J. Augenstein, Pearson
publication.

Books of References
1. “Fundamentals of data structure in C” Horowitz, Sahani & Anderson Freed, Computer Science
Press.

2. “Data Structures Using C”, Reema Thareja, Oxford Higher Education, 2nd edition.

3. “Fundamental of Data Structures” , (Schaums Series) Tata-McGraw-Hill.

4. “Data Structures & Algorithms; Concepts, Techniques & Algorithms”, G. A. V. Pai, TMG Hill.
Dept. of CSE, SRM University AP 8/3/2021 4
Course Outcomes

On successful completion of this course, you should be able to:

▪ Demonstrate the understanding of ADTs with examples emphasizing their need
▪ Explain a variety of data structures and their implementations.
▪ Identify the right data structure to solve a given problems.
▪ Solve complex problems by implementing learned algorithm design techniques
and data structures.

The lavender colored words are the actions verbs that are carefully chosen from Blooms
Taxonomy which indicate the knowledge, skill set and attuite/behaviors students gain at the
end of the course.
Distribution of Marks
Legends

Symbol Description

Announcements

Notes
Group activity

Reading Material

Lecture Session

Quiz time
Prerequisites for the course

• Students must have knowledge on any programming language, preferably C.

• Coding experience with tools such as code-blocks or gcc compilers on Linux

platforms.
This Week’s Topics

▪ Data Types
▪ Data Structures
▪ Abstract Data Types (ADT)
▪ Why ADTs?
▪ Definition of Algorithm
Definition of Structures
Dictionary meaning of Structure:
▪ The arrangement of and relations between the parts or elements of
something complex.
Or
▪ The way in which the parts of a system or objects are arranged or
organized.

▪ Examples:
▪ The grammatical structure of a sentence.
▪ The structure of this protein is particularly complex.
▪ They have a very new-fashioned management structure.
▪ This institute has a different administration structure.
▪ Many temples in India have a pyramid structures.
Things to ponder …

Does the arrangement or organization of entities or elements matter?

Have a thought … (click here)

Consider an example
Scenario (example-1)
Scenario (example-2)
Getting to the topic

Which one do you like and why, in those two

examples?
The once which:

▪ Takes less time to search

(example-1)

▪ Takes less space (example-2)

Does the arrangement or organization of entities or

elements matter?
Now let’s talk about data
Definition of Data
Dictionary meaning of Data:
▪ Collections of facts from which conclusions may be drawn is known as
Data.

▪ (The meaning insights that are obtained form these conclusion, after
statistical analysis, is called as Information).
Or
▪ Data (singular datum) are individual units of information. A datum
describes a single quality or quantity of some object or phenomenon.
Or
▪ Raw observations made by an entity(Human or Machine) about an
event/Phenomenon either continuously or at particular intervals.
Definition of Data
Examples:

▪ The data was/were collected by various researchers

▪ Now the data is/are being transferred from magnetic tape to hard
disk.

▪ Scientists hope that data from the space probe will pave the way
for a more detailed exploration of Mars.

▪ The system will handle phone calls and data messages as well as
other signals that need high bandwidth.
Example of Data

Examples of Data

What to do with this data?

[Link]
Example of Data

Examples of Data
Example of Data
• What to do with this data?
Data
… and putting them together we have Data Structures.
▪ So far we have seen the definition of structure(s) and Datum (data).
▪ We also have observed that arrangement or organization of elements or
entities are a matter of concern, in terms of:
▪ Space
▪ Time
▪ Let’s now see “why arrangement or organization of data using structures
matter?”
▪ Here we go…
▪ What observation have you made?
▪ In terms of Space? Time was reduced in each case of the algorithm
▪ In terms of Time?
Size of the array (space) is fixed
What motivates you to continue with this course?

▪ Real life problem solving

▪ Example: Learning Styles of my students who have opted ADSA course.

▪ Using computer knowledge (in particular programming)

▪ Optimizing SPACE and TIME resources

What are structures in computer programming aspect?

▪ Arrays
▪ Stacks
▪ Queues
▪ Linked Lists
▪ Adjacency Lists
▪ Adjacency Matrices
▪ Trees
▪ Graphs
Tree
Structure Ring
Structure
 Wondered why the tree is shown inverted?
I will tell you the reason when I teach TREE Data Structure
 Opps…I am sorry
We have a tree that is upside down. So I was correct.s
[Link]
Now about the course Data Structures
… and putting them together we have Data Structures
▪ The course Data Structures deals wit the study of methods, techniques and
tools to organize or structure data.
▪ It deals with the study of “how the data is organized in memory, how
effectively it can be stored, retrieved and manipulated.”
▪ It deals with the design and implementation of efficient algorithms.
▪ Key terms:
▪ Data
▪ Structures
▪ Tools
▪ Algorithm(s)
▪ Efficient – time and space complexity
Definition of Data Structures

Data Structure

▪ Is a collection of elements and the relationships among them.

▪ Is an aggregation of atomic data and composite data into a set with defined
relationships.

▪ It is a tool to organize data so that it can be used effectively.

Types of Data
▪ Data can be of two types:
▪ Atomic: Data that consists of a single piece of information; that is, they
cannot be divided into other meaningful pieces of data.
▪ E.g.: 4552
▪ Composite: Data that can be broken out into subfields that have meaning.
▪ Telephone number:

9 9 7 3 1 2 7 9 0 6

Area Code Exchange User Number

Data Type (primitive)
Data
Data Type (primitive)

▪ A Data Type consists of two parts: a set of data and the operations that can
be performed on the data.

Set of operations
Set of data
+, -, *, /, %, ++, --, bit wise
. . ., -2, -1, 0, 1, 2, . . .
operator. . .

Data type: Integer

Data Type (primitive)

Set of operations
Set of data +, -, *, /
. . ., -2.0, -1.0, 0.0, 1.0, 2.0, . . . But bit-wise and % operation are
not permitted

Data type: Floating

Data Type (primitive)

Set of data Set of operations

\0, . . ., ‘A’, ‘B’, . . ., ‘a’, ‘b’, . . ., ‘~’, ‘$’, ‘#’ … <, >, <=, >=, ==, . . .

Data type: Character

▪ What is a Data Type?
▪ A an entity that is a combination of
1. A certain set (or domain) of values and
2. A set of operations on those values

▪ What are those set of operations, over primitive data types?

▪ Addition
▪ Multiplication
▪ Division
▪ Subtraction
▪ Modulus
▪ Increment
▪ Decrement
▪ Bit-wise operations etc.
Data Structure
An aggregation of atomic and composite data into a set with defined logical
relationships between individual elements of data is called data structure.

Atomic Data
Data Structure Composite Data

Defined relationships

Data Structures A Pseudocode Approach with C by Richard F. Gilberg & Behrouz A. Forouzan
Non-primitive Data Types
▪ User defined data types are known as non-primitive data types, which are derived
from or obtained by combining primitive data types.
▪ Specifically, the set of values and the operations necessary to perform on those
set of values are defined by the user (the programmer, you), not the program
itself.
▪ Examples:
1. Structures – obtained by combining different data types such as int, char, float.
▪ E.g. Struct Student {
char Name;
int Roll_No;
float CGPA;
};
2. Unions
3. Enumeration
Abstract Data Type
• A protype or a blueprint or a template.
• These are similar to non-primitive (user defined) data types that define operations on
values using FUNCTIONS without specifying the actual implementation details of the
FUNCTIONS and without mentioning how the operations are performed by the
FUNCTIONS. However, you are told what are the operation (names of the operations)
that are available to you.

• Example:
• Do you know how you laptop (or PC) reads the data from the keyboard?
• Specifically, do you know the code to read the keyboard?
• The keyboard ADT has
• A Data Structure = Set of characters + set of operations that that can be used to read that
data structure.
• Do you have this question in your mind?
• “The keyboard has characters, integers, special symbols, floating point number (of course you
enter them form KB) which are different data types, then how can we perform operations on
data types of different type?”
Abstract Data Type
• Excellent, you are on the track
• Using ADT we can convert one type of data structure to different data
structure such as integer and strings.

• Why we need these blueprints or skeletons? Why ADT?

• With ADTs users are not concerned with the HOW the task is done but rather
with WHAT is can do.
• In other words, the ADT consists of a set of definitions (in the form of
functions) that allow programmers to use the functions while hiding the
implementation details.
• Only the abstract (summary) information is given to the user.
Abstract Data Type

The generalization of operations with unspecified implementations is known

as abstraction.

The concept of abstraction means:

1. We know what a data type can do.
2. How it is done is hidden
Abstract Data Type
Implementation of ADT

• Multiple ways of implementing of ADTs

• Ex, a stack ADT can be implemented using either
1. arrays or
2. linked lists.
• i.e., Stack data structure (non-primitive) which in itself is a ADT is
implemented using array data structures or linked lists data structures
which are in themselves non-primitive.
Abstract Data Type
• Why study ADT?

• The program which uses data structures is called the client program, it has
access to the ADT i.e, the interface.
• The program which implements the data structures is known as the
implementation.

• Connect these lines to the content explained by Forouzan in his book

Abstract Data Type
• Advantages:
• Start from excel sheet sorting example.
• The users of excel sheet need not always be programmers, for instance
accountants.
• Without actually knowing the details of “How the sorting algorithm works, which
sorting algorithms is used etc.” they just use it. Because they need not know how
it works.
• Suppose you develop a more efficient algorithm than the existing sorting
algorithms then Microsoft might reach you to get the implementation details and
integrate that algorithm with the next version of the MS office and release it to
the users, of course if you negotiate with Microsoft team to use your IP. In this
process, the user – the accountant has no knowledge what update is made. The
accountant still has the same interface that he/she was using in the previous
version. This is another advantage.
• But then to whom the internal implementation details are necessary?
• It is you and me, the developers (the programmers).
Types of Data Structure

Types of Data
Structures

Primitive DS Liner DS
Non Primitive DS Non-linear DS
Other operations

▪ Traversing – accessing each data element exactly once so that certain item in
data structure may be processed.

▪ Searching – finding the location of the data element.

▪ Insertion – adding new data element

▪ Deletion – removing an data element

▪ Sorting – arranging the data in a specified order e.g., ascending / descending

▪ Merging – combining data elements from two or more data structures.

Which data structure to choose for the problem at hand?

▪ How to determine the best Data Structure for our need?

▪ Do the following:
▪ Analyse the problem
▪ Determine the basic operations
▪ Select the DS that best meets our needs
Recap
Recap
We have earlier studied the following linear data structures such as:
▪ Arrays
▪ Stacks
▪ Linked Lists
▪ Queues

▪ What else other data structures have you studied ?

▪ Non-linear data structures

▪ These include:
▪ Trees, Graphs, Tables, Sets.
48
 STACKS

▪ Stack is basically a data object .

▪ A stack is a data structure in which
items can be inserted only from one
end and get items back from the same
end.
▪ There , the last item inserted into
stack, is the first item to be taken
out from the stack.
▪ In short its also called Last in First
out [LIFO]. (The last element inserted
will be the first to be retrieved)

49
STACKS

Practical daily life : a

pile of heavy books kept in
a vertical box, dishes kept
one on top of another

In computer world : In
processing of subroutine
calls and returns ; there is
an explicit use of stack of
return addresses.

Also in evaluation of
arithmetic expressions ,
stack is used.
 STACKS Operations
Primary operations defined on a stack:

▪ PUSH: add an element at the top of the list.

▪ POP : remove the at the top of the list.

▪ Also "IsEmpty()" and IsFull()" function, which tests whether a stack is empty
or full respectively.

Implementations of stacks using

▪ Using Arrays

▪ Using Linked list

 STACKS – PUSH and POP operations
▪ Primary operations: Push and Pop
▪ Push Stack full
top
▪ Add an element to the top of the stack D
▪ Pop C
▪ Remove the element at the top of the stack B
▪ "IsEmpty()" and IsFull" functions A

empty stack push an element push another pop push another

top top top

B B
C
top top
A A A A

top 52
STACK Implementation Using Array

▪ Need to declare an array_size ahead of time

▪ Associated with each stack is TopOfStack
▪ for an empty stack, set TopOfStack to -1
▪ Push
▪ (1) Increment TopOfStack by 1.
▪ (2) Set Stack[TopOfStack] = X
▪ Pop
▪ (1) Set return value to Stack[TopOfStack]
▪ (2) Decrement TopOfStack by 1
▪ Any time TopOfStack is equal to size of array then stack is full.
▪ These operations are performed in constant time
53
STACK Implementation Using Array
Push ( )
Description:
Here STACK is an array with MAX locations.
TOP points to the topmost element
ITEM is the value to be inserted.
void push(int value){
If(Top == max) then if(top == SIZE-1)
print: overflow printf("\nStack is Full!!! Insertion is
Else not possible!!!");
set Top = Top +1 else{
set STACK[Top] = ITEM top++;
print: ITEM inserted stack[top] = value;
End of IF printf("\nInsertion success!!!");
}
}
Algorithm for PUSH operation
C code for PUSH operation 54
 STACK Implementation Using Array
Pop ( ):
Description:
Here STACK is an array with MAX locations.
TOP points to the top most element.

If(Top == -1) then void pop(){

print: underflow if(top == -1)
Else printf("\nStack is Empty!!! Deletion is
set ITEM = STACK[Top} not possible!!!");
set Top = Top - 1 else{
print: ITEM deleted printf("\nDeleted : %d", stack[top]);
End of IF top--;
}
}
Algorithm for POP operation
C code for POP operation
STACK Implementation Using Array

Peek() is one of a stack operation that prints the value of the top most
element of the stack without deleting that element from the stack.
The next two slides have the complete C code for Stack operations
STACK Implementation Using Array
#include<stdio.h>
#define SIZE 10
void push(int);
void pop();
void display();
Void peek();
int stack[SIZE], top = -1;
void main()
{
int value, choice;
while(1){
printf("\n\n***** MENU *****\n");
printf("1. Push\n 2. Pop\n 3. Peek\n [Link] \n 5. Exit");
printf("\nEnter your choice: ");
scanf("%d",&choice);
58
STACK Implementation Using Array
switch(choice){
case 1: printf("Enter the value to be insert: ");
scanf("%d",&value);
push(value);
break;
case 2: pop();
break;
case 3: peek();
break;
case 4: display();
break;
case 5: exit(0);
default: printf("\nWrong selection!!! Try again!!!");
}
}
}
STACK Implementation Using Array
void push(int value){
if(top == SIZE-1)
printf("\nStack is Full!!! Insertion is not possible!!!");
else{
top++;
stack[top] = value;
printf("\nInsertion success!!!");
}
}
void pop(){
if(top == -1)
printf("\nStack is Empty!!! Deletion is not possible!!!");
else{
printf("\nDeleted : %d", stack[top]);
top--;
}
} 60
STACK Implementation Using Array
void peek(){
if(top == -1)
printf("\nStack is Empty!!!");
else{
int i;
printf("\nStack top most element is: %d\n“,stack[top]);
}}
void display(){
if(top == -1)
printf("\nStack is Empty!!!");
else{
int i;
printf("\nStack elements are:\n");
for(i=top; i>=0; i--)
printf("%d\n",stack[i]);
}} 61
 void push(int value){
#include<stdio.h>
if(top == SIZE-1)
#define SIZE 10
printf("\nStack is Full!!! Insertion is not possible!!!");
void push(int);
else{
void pop();
top++;
void display();
stack[top] = value;
void peek();
printf("\nInsertion success!!!");
int stack[SIZE], top = -1;
}}
void main()
{
void pop(){
int value, choice;
if(top == -1)
while(1){
printf("\nStack is Empty!!! Deletion is not possible!!!");
printf("\n\n***** MENU *****\n");
else{
printf("1. Push\n 2. Pop\n 3. Peek\n [Link] \n 5. Exit");
printf("\nDeleted : %d", stack[top]);
printf("\nEnter your choice: ");
top--;
scanf("%d",&choice);
}}
switch(choice){
case 1: printf("Enter the value to be insert: ");
void peek(){
scanf("%d",&value);
if(top == -1)
push(value);
printf("\nStack is Empty!!!");
break;
else{
case 2: pop();
int i;
break;
printf("\nStack top most element is: %d\n",stack[top]);
case 3: peek();
}}
break;
case 4: display();
void display(){
break;
if(top == -1)
case 5: exit(0);
printf("\nStack is Empty!!!");
default: printf("\nWrong selection!!! Try again!!!");
else{
}
int i;
}
printf("\nStack elements are:\n");
}
for(i=top; i>=0; i--)
printf("%d\n",stack[i]);
}}
STACK Implementation Using Array
▪ Application of stack in REVERSING a string.

▪ Now modify the code to solve the given problem.

▪ Write a C program to reverse a given string.

▪ The string is:

▪ “MADAM”
▪ “SRM UNIVERSITY AP”
▪ 123456789

▪ Class activity: Student’s have to do online and give the results.

Stacks Using Linked List
STACK Implementation Using Linked List

Basics of linked list

STACK Implementation Using Linked List

Data Structures A Pseudocode Approach with C by

Richard F. Gilberg & Behrouz A. Forouzan,
2nd Edition, Cengage Learning
STACK Implementation Using Linked List

Data Structures A Pseudocode Approach with C by Richard F. Gilberg & Behrouz A. Forouzan, 2 nd Edition, Cengage Learning
STACK Implementation Using Linked List

Data Structures A Pseudocode Approach with C by

Richard F. Gilberg & Behrouz A. Forouzan, 2nd Edition, Cengage Learning
Application Of Stack
1. Reverser a string (already covered in earlier slides)

2. Converting an infix expression to postfix expression.

3. Converting an infix to prefix expression

4. Evaluation of arithmetic expression – postfix expression.

5. Evaluation of arithmetic expression – prefix expression.

6. Backtracking (4-queen problem or 8-queen problem).

7. Recursion: game – Tower of Hanoi.

8. To check that every right brace, bracket, and parentheses must correspond to
its left counterpart e.g. [( )] is legal, but [( ] ) is illegal. To determine such
problem we use parenthesis.
Application Of Stack
2. Converting an infix expression to postfix expression:
Application Of Stack

Precedence and Associative of operators

Operators Precedence
(, {, [ ], }, ) 7
-, +, NOT (Binary) 6
^ (exponentiation) 6
*, / 5
+, - (Arithmetic) 4
<, >, <=, !=, >= 3
AND 2
OR, XOR 1
Application Of Stack
Infix to Postfix using stack (competitive exam stye)
Given: (A+B)/(C-D)
Given: (A + B) *C
Step 1: (E1) * (E2), where E1 = AB+
Step 1: (E) * C, where E = AB+
and E2 = CD-
Step 2: EC *
Step 2: E1 E2 /
Step 3: Replace E. i.e., we have AB+C*
Step 3: Replace E1 E2 . i.e., we have
AB+CD-/
Example : Conversion of infix expression to postfix

73
For detailed explanation refer to class video recordings
Application Of Stack
Infix to Postfix using stack (manual method)

For detailed explanation refer to class video recordings

Application Of Stack
Pseudo code: Infix to postfix
conversion
Stack ADT (Abstract Data Type)

▪ The examples you did so far, on Stack, used several stack operations – namely,
PUSH, POP, PEEK, CREATE_STACK, PRINT_STACK etc.

▪ While we could write them each time we needed them, this would certainly be an
inefficient use of our time.

▪ In earlier lab we have seen how the STACK defined to reverse a set of
characters was not working if the inputs were a set of integers.

▪ Because, the data type of characters is different for that of integers and we
had to modify the program to suit our needs.
.
Stack ADT (Abstract Data Type)

▪ However, a good program must be self adaptive – irrespective of nature of

inputs type it must work without too much of modifications.

▪ Therefore, we need a way to overcome this issue and save our time.

▪ How to resolve this issue?

▪ Using ADTs

▪ In our case, we need, therefore, a stack abstract data type that we can put in a
library and call whenever we need it.

▪ Therefore, we develop a stack abstract data type in this section.

Stack ADT (Abstract Data Type)
The stack data structure:

▪ The stack ADT implementation in C is straightforward.

▪ Rather than store data in each node, we store a pointer to the data.
▪ It is the application program’s responsibility to allocate memory for the data
and pass the address to the stack ADT.

▪ Within the ADT, the stack node looks like any linked list node except that it
contains a pointer to the data rather than the actual data.

▪ Because the data pointer type is unknown, it is stored as a pointer to void.

▪ The head node and the data nodes are encapsulated in the ADT. The calling
function’s only view of the stack is a pointer to the stack structure in the ADT,
which is declared as a type definition.
Stack ADT (Abstract Data Type)
… The stack data structure:

▪ We name this stack type STACK.

▪ This design is very similar to C’s

FILE structure.

▪ To create a stack, the programmer

defines a pointer to a stack as shown
in the following example and then
calls the create stack function.

▪ The address of the stack structure

is returned by create stack and
assigned to the pointer in the calling
function.
Stack ADT (Abstract Data Type)
Stack ADT (Abstract Data Type)
Stack ADT (Abstract Data Type)
Explain how to create library
Application Of Stack
Evaluation of Postfix expression

Class Activity:
Given expression: Try this now.
- * 3 + 16 2 1 12 6
Ans: 52

Example: Evaluation of postfix expression

For detailed explanation refer to class video recordings 84

 Stack Related Applications Using Arrays

Stack Related Applications Using Linked List Will be

Covered in Unit II
Application Of Stack
1. Reverser a string (already covered in earlier slides)

2. Converting an infix expression to postfix expression.

See Class Video Recordings
3. Converting an infix to prefix expression

4. Evaluation of arithmetic expression – postfix expression.

5. Evaluation of arithmetic expression – prefix expression.

6. Backtracking (4-queen problem or 8-queen problem).

7. Recursion: game – Tower of Hanoi.

8. To check that every right brace, bracket, and parentheses must

correspond to its left counterpart e.g. [( )] is legal, but [( ] ) is illegal.
To determine such problem we use parenthesis.
Application Of Stack

▪ Backtracking (4-queen problem or 8-queen problem).

▪ Recursion: game – Tower of Hanoi.

▪ To check that every right brace, bracket, and parentheses must

correspond to its left counterpart e.g. [( )] is legal, but [( ] ) is illegal.
To determine such problem we use parenthesis.
Arrays

88
Array ADT

▪ If you recall the information related to Arrays from your earlier semester,
then let’s consider few aspects related to Arrays.

▪ A set of memory locations to store array element – the ARRAY itself.

▪ How many elements to store in that ARRAY – the size of the array.

▪ Information about the index that is pointing to the last element in the
array – call it LastIndex.
Offset

Size 10 0 1 2 3 4 5 6 7 8 9

LastIndex 6 12 17 4 5 22 28 79

ArrPtr 200 200 201 202 203 204 205 206 207 208 209
Addresses
Array ADT
▪ Value = 10
▪ Loc or index = 8, 5, 7, 14, 9, -1
▪ Case1: If index is < 0 or > Size is true, then print “Invalid index, please
enter the valid loc or index.”
▪ Case2: If index == LastIndex+1 is true, ArrPtr[LastIndex+1]=value.
▪ Case3: If LastIndex+1 == Size, then print array is full
▪ Case4: If index < LastIndex, then move the elements towards right
until the index of interest is free.
▪ Save the LastIndex address in i. that is I = 7
▪ Case5: If index >= LastIndex+2
Offset

Size 10 0 1 2 3 4 5 6 7 8 9

LastIndex 6/7 12 17 4 5 22 28 79

ArrPtr 200 200 201 202 203 204 205 206 207 208 209
Addresses
Array ADT
▪ Operations on Array Offset

0 1 2 3 4 5 6 7 8 9
▪ CreateArray
12 17 4 5 22 28 79

200 201 202 203 204 205 206 207 208 209
Addresses
▪ RetreiveItem RetreiveItem(3);
// Here 3 is the index of the element that we want to retreiive

StoreItem(3);
▪ StoreItem
// Here 3 is the index of the element that we want to retreiive

▪ ModifyArray // The element at specified index is modified.,

// Count number of elements in an array
▪ CountArrayItems
//Remove an element at given index.
▪ RemoveArrayItem Then move all elements in position
Array ADT

▪ Let’s create this structure Size 10

LastIndex 6
ArryPtr 200
▪ CreateArray()

▪ For the rest, please see the class video recording

Application of Arrays

▪ Polynomial Expression

▪ Sparse Matrix

▪ Will be covered post mid-1

Array ADT
Array ADT

Program development cycle

1) Understanding the problem

2) Write pseudocode (i.e, the algorithm)

3) Write the code/program

4) Then do the testing and debugging.

5) Validation.
Something Interesting…

1. 1 circle
2. 120 points on circle(circumference)
3. 1000 lines (chords)
4. 3 hours work

Video

Pic1

Pic2

Pic3
Algorithm Analysis

Let’s see what an Algorithm is and what

is meant by Algorithm Analysis means
Queues
• Like a stack, a queue is also a list. However, with a queue, insertion is done at one
end, while deletion is performed at the other end.
• Accessing the elements of queues follows a First In, First Out (FIFO) order.
• Like customers standing in a check-out line in a store, the first customer in is
the first customer served.

Example :
1. PRACTICAL EXAMPLE : A line at a ticket counter for buying tickets operates on
above rules.

2. IN COMPUTER WORLD : In a batch processing system, jobs are queued up for

99
processing.
Queue Operations
Primary operations defined on a Queue:
[Link] : This is used to add elements into the queue at the back end.
[Link] : This is used to delete elements from a queue from the front end.
[Link] "IsEmpty()" and "IsFull()" can be defined to test whether the queue is Empty or full.

Implementations of stacks using

1. array
2. linked list

Remove Insert
(Dequeue) front rear (Enqueue)

100
Queue Operations
• There are several different algorithms to implement Enqueue and Dequeue
• When enqueuing, the front index is always fixed and the rear index moves forward
in the array.
rear rear rear rear rear

3 3 6 3 6 9 6 9 9

front front front front front

Enqueue(3) Enqueue(6) Enqueue(9) Dequeue() Dequeue()

rear = -1

front=-1
Queue Implementation

Enqueue & Dequeue

102
Queue Implementation Using Array
Insert ( ): or EnQueue():
Description: Here QUEUE is an array with N locations. FRONT and REAR points to the front and rear of the QUEUE. ITEM is
the value to be inserted.

void enQueue(int value){

if(rear == SIZE-1)
printf("\nQueue is Full!!! Insertion is not possible!!!");
else{
if(front == -1)
front = 0;
rear++;
queue[rear] = value;
printf("\nInsertion success!!!");
}
}
Queue Implementation Using Array
Delete ( ): or DeQueue():
Description: Here QUEUE is an array with N locations. FRONT and REAR points to the front and rear of the QUEUE.

void deQueue(){
if(front == rear)
printf("\nQueue is Empty!!! Deletion is not possible!!!");
else{
printf("\nDeleted : %d", queue[front]);
front++;
if(front == rear)
front = rear = -1;
}
}
#include<stdio.h> void enQueue(int value){
#define SIZE 10 if(rear == SIZE-1)
void enQueue(int); printf("\nQueue is Full!!! Insertion is not possible!!!");
void deQueue(); else{
void display(); if(front == -1)
int queue[10], front = -1, rear = -1; front = 0;
rear++;
void main() {
queue[rear] = value;
int value, choice;
printf("\nInsertion success!!!");
while(1){ }}
printf("\n\n***** MENU *****\n"); void deQueue(){
printf("1. Insertion\n2. Deletion\n3. Display\n4. Exit"); if(front == rear)
printf("\nEnter your choice: "); printf("\nQueue is Empty!!! Deletion is not possible!!!");
scanf("%d",&choice); else{
switch(choice){ printf("\nDeleted : %d", queue[front]);
case 1: printf("Enter the value to be insert: "); front++;
scanf("%d",&value); if(front == rear)
enQueue(value); front = rear = -1;
break; }}
case 2: deQueue(); void display(){
break; if(rear == -1)
case 3: display(); printf("\nQueue is Empty!!!");
break; else{
int i;
case 4: exit(0);
printf("\nQueue elements are:\n");
default: printf("\nWrong selection!!! Try again!!!");
for(i=front; i<=rear; i++)
} printf("%d\t",queue[i]); 105
}} }}
Trees Basics
▪ Data will be represented in multiple levels

▪ Now we will discuss a non-linear data Father & Mother

structure called TREE

▪ Each level contains a single data or

collection of data
Child
Child
▪ Trees are mainly used to represent data
containing a hierarchical relationship
between elements, for example, records,
family trees and table of contents
Grand Children
Grand Children
▪ Consider a parent-child relationship

106
Natural View of a Tree

Leaves

Branches

Root

107
Computer Scientist’s View of a Tree

Root Leaves
Branches Father & Mother

Branches
Child
Child

Root

Grand Children
Grand Children

Intermediate nodes or
108
Leaves inner nodes
Types of Trees
Some of the popular tree types are: Operation on Trees

▪ Binary Tree ▪ Traversing

▪ Binary Search Trees ▪ Search
▪ AVL ▪ Insertion
▪ Red-black trees ▪ Deletion
▪ B-trees
Applications of Trees
▪ B+ trees
▪ To evaluate arithmetic expressions
▪ General
▪ Used in searching and sorting operations
▪ Orchids
▪ Implement the file systems of several OSs
▪ Heaps
109
Trees Basics

A tree is an abstract model of a hierarchical structure that consists

of nodes with a parent-child relationship
A
▪ Tree is a sequence of nodes
▪ There is a starting node known as a root node
B C D
▪ Every node other than the root has a parent node
▪ Nodes may have any number of children
▪ It is an acyclic connected graph E F G
▪ A Tree contains no loops and no cycles
▪ There is no more than one edge between any pair of nodes
Trees Basics

▪ A TREE is a data structure that consists of a finite set of elements,

called nodes, and a finite set of directed edges or directed lines, called
branches, that connect the nodes without forming any loop.

▪ The node is represented with a circle and a symbol enclosed within it to

identify a node. These circles are linked using directed edges.
Tree Terminology

▪ Root-node: A node without parent (A) OR in a nonempty tree, the first node is
called the root.

▪ Siblings-nodes share the same parent. Nodes D & E are siblings; nodes F and G
are siblings & nodes I & J are siblings.

▪ Leaf-node: Nodes without children (E,G, H, I,J).

▪ Internal node: Node with at least one child (A, B, C, D,F). Other way is all
non-leaf nodes are internal nodes

[Link]
Tree Terminology

▪ Ancestors of a node: parent, grandparent, grand-grand-parent, etc.

▪ Descendant of a node: child, grandchild, grand-grandchild, etc.

▪ Level: The level of a node is its distance from the root node.
▪ Level of a root is 0.
▪ Children of a root are at level 1.
▪ Their children are at level 2 and so on.
Tree Terminology

Root A Level 0
The dashed
B is the parent
line is the path
of D and E
B E is the right C Level 1
D is the left
child of B child of B

D E
F G Level 2

A sub-tree with I J Level 3

F as its root
Tree Terminology
▪ Height (also known as Depth) of a tree: Maximum level of any leaf node in the
tree plus one
▪ By definition, height of an empty tree is -1.
▪ E.g., Height of the tree shown in figures = 4
▪ This tree has 3 levels (l=3):
▪ Root node A at level 0
▪ Nodes B and C at level 1
▪ Nodes D, E, F and G at level 2
▪ Nodes H, I and J at level 3
▪ Therefore, Height of the tree = highest level of the tree + 1
▪ i.e., H = 3 + 1 = 4.
Tree Terminology
▪ Subtree: Tree consisting of a node and its
descendants. A

▪ In figure, the sub-tree of B D

▪ B: has node E at its member C
▪ C: has nodes H and I as its members
E G
▪ D: has node G as member H F

▪ Also, we see that the tree has 3 sub-trees.

▪ Sub-tree_1 with nodes B and E
▪ Sub-tree_2 with nodes C, H and F
▪ Sub-tree_3 with nodes D and G
Tree Terminology
Degree of a node: The number of branches
associated with a node is the degree of the
node. Denoted by deg(node_ID)
A
▪ Deg(A) = 3
B D
▪ Deg(B) = 2
C
▪ Deg(C) = 3
▪ Deg(D) = 2 E G
H F
▪ Deg(E) = 1
▪ Deg(F) = 1
▪ Deg(G) = 1
▪ Deg(H) = 1
Tree Terminology

In degree of the node:

▪ If the branch is directed toward the node, it is an indegree branch.

▪ Represented as InDeg(node_ID).
A
▪ E.g., InDeg(A) = 0
B D
▪ InDeg(B) = InDeg(C) = InDeg(D) = 1 C

▪ InDeg(E) = InDeg(H) = InDeg(F) = InDeg(G) = 1

E H G
F
Tree Terminology
Out degree of the node:

▪ If the branch is directed away form the node, it is an outdegree branch.

A
▪ It is denoted by OutDeg(nodeID).
B D
▪ E.g., OutDeg(A) = 3
C
▪ OutDeg(B) = OutDeg(D) = 1
E H G
▪ OutDeg(C) = 2 F

▪ OutDeg(E) = OutDeg(F) = OutDeg(G) = OutDeg(H) = 0

▪ NOTE: The sum of the indegree and outdegree branches of a node is the
degree of the node.
Tree Terminology

The sum of the indegree and outdegree branches of a node is the

degree of the node.
Tree Terminology

B D
C

E H G
F
Limitations of BST
log2(n)
▪ The minimum height of a BST _______

▪ The maximum height of a BST _______

n

▪ Want to confirm?

▪ Then insert the following seven (n=7) nodes into a BST:

▪ 45, 36, 63, 27, 39, 54, 72.

▪ What is the height of the BST you got?

▪ Now, insert the following seven (n=7) nodes into a BST:

▪ 27, 36, 39, 45, 54, 63, 72.

▪ Now what is the height of the BST?

▪ Hope you are now confirmed with first two points.

Limitations of BST

▪ The size of the input remains same (= 7 nodes) in both the cases.

▪ But then the trees’ size differs, why?

▪ It depends on the order in which the nodes are inserted.

Gap identified or limitation of BST:

▪ Therefore, is there a way to reduce the height of the tree from h to lesser a
lesser value, say log2(n)?

▪ YES!. They are AVL trees.

AVL Trees
▪ AVL tree is a self-balancing binary search tree developed by G. M.
Adelson-Velsky and E. M. Landis.

▪ In AVL tree, the heights of the two sub-trees of a node may differ by at most
one.

▪ Due to this property, the AVL tree is also known as a height-balanced tree.

▪ Advantage: Insert and Delete operations take, on average, take O(log (n)) time.

▪ The structure of an AVL tree is same as that of a BST but with an extra
information – BalanceFactor (or depth difference)

▪ Balance Factor (BF) = HLST – HRST; where HLST and HRST are height of left
sub-tree and right sub-tree respectively.
AVL Trees

▪ Left-heavy tree: HLST – HRST = 1

▪ Right-heavy tree: HLST – HRST = -1

▪ Balanced tree: HLST – HRST =0

AVL Trees

▪ Test your understanding:

▪ Determine the depth factors as questioned.
1
45
1 0
36 63

0 0 0
1
27 39 54 72

18
0
AVL Trees
45 45

36 63 63
36

27 54 72 54
39 27 39 72

BF of Node 27 = 0 0
70 BF of Node 27 =
BF of Node 39 = 0 0
BF of Node 39 =
BF of Node 36 = 0 0
BF of Node 36 =
BF of Node 54 = 0 0
BF of Node 54 =
BF of Node 70 = 0 0
BF of Node 72 =
BF of Node 72 = 1 0
BF of Node 63 =
BF of Node 63 = -1 0
BF of Node 45 =
BF of Node 45 = -1
AVL Trees
▪ Insertions and deletions may disturb the balance of a tree.

▪ So what to do?

▪ Rebalancing is necessary.

▪ This is achieved using the following four types of rotations:

▪ LL rotation (Left Left)

▪ RR rotation (Right Right)

▪ LR rotation (Left Right)

▪ RL rotation (Right Left)

AVL Trees
▪ During insertion, the new node is inserted as the leaf node, so it will always
have a balance factor equal to zero.

▪ The only nodes whose balance factors will change are those which lie in the path
between the root of the tree and the newly inserted node.

▪ The possible changes which may take place in any node on the path are as
follows:

▪ Initially, the node was either left- or right-heavy and after insertion, it
becomes balanced.
▪ Initially, the node was balanced and after insertion, it becomes either left-
or right-heavy.
▪ Initially, the node was heavy (either left or right) and the new node has
been inserted in the heavy sub-tree, thereby creating an unbalanced
sub-tree. Such a node is said to be a critical node.
AVL Trees
45 -1 45 0

36 0 63 -1 36 1 63 -1

27 0 54 0 72 1 0 54 0 1
39 0 27 -1 39 72

70 0 70 0
30 0
Insert 30

▪ Initially, the node was either left- or right-heavy and after insertion, it
becomes balanced.
AVL Trees
45 -1
45 0
36 0 63 -1
36 0 63 0

54 0 1
27 0 54 0 72 0 27 0 39 0 72
39 0

71 0

Insert 71

▪ Initially, the node was balanced and after insertion, it becomes either
left- or right-heavy.
AVL Trees
45 0 45 1
36 2 63 -1
36 1 63 -1

0 54 0
27 -2 39 72
0 54 0 1 1
27 -1 39 72

70 0
70 0 30 1
30 0

Insert 29
029
▪ Initially, the node was heavy (either left or right) and the new node has been
inserted in the heavy sub-tree, thereby creating an unbalanced sub-tree.
▪ Such a node is said to be a critical node.
AVL Trees
▪ Is the tree imbalanced after you inserted a 45 -2
new node?
▪ If yes, then follow the mentioned steps. 36 0 63 -2

1. Determine the critical node: A Critical

node is the nearest ancestor node on the
0 54 0 2
path from the inserted node to the root 27 0 39 72
whose balance factor is neither –1, 0, nor 1.
▪ Example: In the tree given above, the
critical node is 72. 70 -1

2. The second task in rebalancing the tree is 0

to determine which type of rotation has to Newly inserted node 71
be done.
AVL Trees
▪ There are four types of rebalancing rotations and application of these
rotations depends on the position of the inserted node with reference to
the critical node.
▪ The four categories of rotations are:

▪ LL rotation The new node is inserted in the left sub-tree of the left
sub-tree of the critical node.

▪ RR rotation The new node is inserted in the right sub-tree of the right
sub-tree of the critical node.

▪ LR rotation The new node is inserted in the right sub-tree of the left
sub-tree of the critical node.

▪ RL rotation The new node is inserted in the left sub-tree of the right
sub-tree of the
AVL Trees
For three nodes having the values 27, 36 and 45. The red node is the critical
node (CN)
There could be the following choices of trees based on the input sequence.
45 45 27
27 36

36
27 45 36
27 45
27
36 36 45
Which is the best one and why?

Hint: Think in terms of BF

Then can we change the first four into the form that looks like the fifth one?
AVL Trees - Insertion
1. LL rotation The new node is inserted in the left sub-tree of
the left sub-tree of the critical node.
45
• Given the nodes of a tree. BF = 2

• Insert node 27.

36
BF = 1
• How does your tree look like?

• Now determine the BFs.

27
BF = 0
• Is it balanced?

• No. Then …?

• Perform LL rotation.
AVL Trees - Insertion
1. LL rotation The new node is inserted in the left sub-tree of
the left sub-tree of the critical node.

BF = 0 Middle node becomes

become root of
36 sub-tree and root of
the sub-tree becomes
the right child of new
root.

BF = 0 27 45
BF = 0
AVL Trees - Insertion
2. RR rotation The new node is inserted in the right sub-tree
of the right sub-tree of the critical node.
27 BF = -2
• Given the nodes of a tree.

• Insert 45.
36 BF = -1
• How does your tree look like?

• Now determine the BFs.

45
BF = 0
• Is it balanced?

• No. Then …?

• Perform RR rotation.
AVL Trees - Insertion
2. RR rotation The new node is inserted in the right sub-tree
of the right sub-tree of the critical node.

Middle node becomes

BF = 0 become root of
sub-tree and root of
36 the sub-tree becomes
the left child of new
root.
BF = 0
27 45 BF =
AVL Trees - Insertion
3. LR rotation The new node is inserted in the right sub-tree of
the left sub-tree of the critical node.
BF = 2
• Given the nodes of a tree. 45

• Insert 36.

27 BF = -1
• How does your tree look like?

• Now determine the BFs.

36
• Is it balanced?
BF = 0
• No. Then …?

• Perform LR rotation.
AVL Trees - Insertion
3. LR rotation The new node is inserted in the right sub-tree of
the left sub-tree of the critical node.
Step-1: Step-2:
BF = 2 • From newly BF = 2 • Now apply LL 36
45 inserted node transformation
45
(say 36) go one
step back • That is
perform right 27 45
towards root
27 BF = -1 36
(say 27). rotation
BF = 1 keeping middle
• Now perform 27 node as new
rotate left root.
36 BF = 0
considering
BF = 0 both the nodes
together (36
and 27)
AVL Trees - Insertion
4. RL rotation The new node is inserted in the left sub-tree of
the right sub-tree of the critical node (here it is 27)

• Given the nodes of a tree.

BF = -2
• Insert 36. 27

• How does your tree look like?

45 BF = 1
• Now determine the BFs.

• Is it balanced?
36 BF = 0
• No. Then …?

• Perform RL rotation.
AVL Trees - Insertion
4. RL rotation The new node is inserted in the left sub-tree of
the right sub-tree of the
Step-1: BF = -2
• From newly Step-2: 36
BF = -2 inserted node 27 • Now apply RR
27
(say 36) go one transformation
step back BF = -1
towards root • That is 27 45
36
45 BF = 1 (say 45). perform left
rotation
• Now perform 45 keeping middle
rotate right node as new
36 BF = 0 considering BF = 0 root.
both the nodes
together (36
and 45)
AVL Trees - Deletion
▪ Deletion in ALV tree follows the same rules as the deletion in BST.

▪ However, this time the balance of the AVL tree is checked. If it is imbalanced
the rebalancing is necessary

▪ Deletion cases:
1. Case1: If the node to be deleted has no children, i.e., it is a leaf node, then
you are done.
2. Case2: If the node to be deleted has either left or right sub-tree (LST or
RST), then link that ST with the parent of the deleted node.
3. Case3: If the node to be deleted has both sub-trees then replace the
position of the deleted node with
a. either the largest node of LST
b. or smallest node of the RST
AVL Trees - Deletion
▪ Once the deletion and linking is done, update the BFs.
▪ If the tree is imbalanced, then do rebalancing.

▪ Rebalancing cases:
1. R0 -> LL rotation 4. L0 -> RR rotation
2. R+1 -> LL rotation 5. L+1 -> RL rotation
3. R-1 -> LR rotation 6. L-1 -> RR rotation
▪ How to interpret those 6 cases?
▪ Steps:
▪ After updating the BFs, find the critical node (CN).
▪ Now determine the BF of the left child, for instance, of CN. Let us say its
BF = -1
▪ Suppose the deleted node, for instance, is to the right of the CN ,then
choose L (for left)
▪ Now put together, read it as L-1 case. Implies RR rotation must be peformed.
AVL Trees - Deletion
Examples:
In the given AVL tree, delete the following nodes: 52, 36 and 61.
+1
55
0
+1
45
0 63
0
36 51
0
0 0 0 0 61
18 39 47 52
AVL Trees - Deletion
Since 52 has no children, we just need to update the BF and determine the BF.

+1 +1
55 55
0 0
+1 +1
45 45
0 0 63
0 63 +1

36 36 51
51 0
0 0 0 61
0 0 0 0 61 0
18 18 39
39 47 47
52
▪ Node 52 has no children, so we just need to update the BF and determine the
balancing criteria.
▪ The updated BFs indicate that the tree is balanced and no rebalancing in
necessary.
AVL Trees - Deletion
Delete 36:
Since 36 has two children, its position can be replaced by either largest node in
LST or smallest node in RST.
Let us choose largest node in LST
+1 +1
55 55
0 0
+1 +1
45 45
0 63 -1 63
0 +1
18
36 51 51
0 0
0 0 0 61 0 0 61
18 39 39 47
47

▪ The updated BFs indicate that the tree is balanced and no rebalancing in
necessary.
AVL Trees - Deletion
Delete 61: +1 +2
55 55
0 0
+1 0
45 45
-1 63 -1
+1 +1 63
18 18
51 51
0
0 0 61 0 0
39 47 39 47
▪ After updating the BFs, we find that node 55 becomes the CN.
▪ Now check for the rule patterns as follows:
1. Node deleted was on to the right of CN, so it is R.
2. The child of CN has BF = 0 (i.e., node 45’s BF is 0), so the combination is R 0.
3. So perform LL rotation.
Note: For rotations we need 3 nodes. Starting from node CN and downwards
towards the leaf, choose 3 nodes that are in RR pattern.
AVL Trees - Deletion
After rotations the tree is as shown below with BF updated.
-1
45

18 -1 55 +1

0 39 51 +1 63 0

47 0
AVL Trees

For more practice, solve the problems

given as class homework.
Red-Black Trees

▪ We know that a BST of height h can support any of the basic dynamic-set
operations – such as SEARCH, PREDECESSOR, SUCCESSOR, MINIMUM,
MAXIMUM, INSERT, DELETE – in O(h) times., where h = n.

▪ We have seen how AVL trees can perform better on these operation with
worst-case time complexity of O(log2(n)).

▪ In this session, we shall study another such height balancing trees known
as RED-BLACK Trees.
Red-Black Trees
History:
▪ In 1972, Rudolf Bayer invented a data structure that was a special order-4
case of a B-tree.
▪ These trees maintained all paths from root to leaf with the same number
of nodes, creating perfectly balanced trees.
▪ However, they were not binary search trees. Bayer called them a
"symmetric binary B-tree" in his paper [1] and later they became popular as
2-3-4 trees or just 2-4 trees.
▪ In a 1978 paper, "A Dichromatic Framework for Balanced Trees", [2] the
authors derived the red-black tree from the symmetric binary B-tree.
▪ The color "red" was chosen because it was the best-looking color produced
by the color laser printer available to the authors while working at Xerox
PARC. Another response from Guibas states that it was because of the red
and black pens available to them to draw the trees.
[1] Rudolf Bayer (1972). "Symmetric binary B-Trees: Data structure and maintenance algorithms". Acta Informatica. 1 (4): 290–306.
[2] Leonidas J. Guibas and Robert Sedgewick (1978). "A Dichromatic Framework for Balanced Trees". Proceedings of the 19th Annual
Symposium on Foundations of Computer Science. pp. 8–21
Red-Black Trees
▪ A red-black tree is a BST with one extra bit of storage per node: its color,
which can be either RED or Black.

▪ An RB tree, therefore, contains 5 fields per node:

▪ Color
▪ Key
▪ Left pointer
▪ Right pointer
▪ Parent pointers

▪ If a child or the parent of a node does not exist, the corresponding pointer
attribute of the node contains the value NIL.

▪ By constraining the node colors on any simple path from the root to a leaf,
red-black trees ensure that no such path is more than twice as long as any
other, so that the tree is approximately balanced.
Red-black Trees
NOTE: We shall regard these NILs as being pointers to leaves (external nodes)
of the binary search tree and the normal, key-bearing nodes as being internal
nodes of the tree.

A red-black tree is a binary tree that satisfies the following red-black

properties trees:

1. Every node is either red or black.

2. The root is black.
3. Every leaf (NIL) is black.
4. If a node is red, then both its children are black.
5. For each node, all simple paths from the node to descendant leaves contain the
same number of black nodes.

NIL or NULL is important to know the 5th property else it is most of the time
skipped.
Red Black Trees
Cases:
▪ Case-1: If the tree is empty, create a new node as the root node and color it
black (by default the new node inserted is always RED). Else call case-2

▪ Case-2: If the tree is not empty, create a new node as the leaf node and color
it RED. If the new node’s parent is BLACK then exit. Else call case-3.

▪ Case-3: If the parent of new node if RED, then check the color of parent’s
sibling (uncle’s color):
▪ Sub-Case-3a: If uncle’s color is RED, then recolor both parent’s and uncle’s
colors. Then check the color of grandparent. Recolor grandparent’s color if
it is not the ROOT node and recheck recursively until done.
▪ Sub-Case-3b: If uncle’s color is BLACK or if it is NUL then do appropriate
rotations and then recolor accordingly (swap the colors of --- and uncle
after rotation).
Examples: See handwritten notes
Deletion in RED-Black Trees
Cases:
▪ Case-1: If the node to be deleted is a RED leaf node, then just delete it. Assign
its parent a BLACK NIL node.

▪ Case-2: If a node to be deleted has 2 non-NIL children, then replace the node
with its in-order successor and delete the successor node.

▪ Case-3: If node to be deleted is BLACK but has one RED child then replace it
with that child’s value and change the color of the child to BLACK

▪ Case-4: If the node to be deleted is BLACK and has two BLACK children, then
this is a double-black situations and this has SIX (6) subcases.
Deletion in RED-Black Trees
Sub-Cases:
▪ Case-4a:

Root

NIL NIL NIL NIL

NIL NIL
Deletion in RED-Black Trees
Deletion in RED-Black Trees
Deletion in RED-Black Trees
Deletion in RED-Black Trees
Deletion in RED-Black Trees
Deletion in RED-Black Trees
Deletion in RED-Black Trees
Deletion in RED-Black Trees
Deletion in RED-Black Trees
Deletion in RED-Black Trees
Deletion in RED-Black Trees
Splay Trees

▪ Splay trees were invented by Daniel Sleator and Robert Tarjan.

▪ A splay tree is a self-balancing binary search tree with an additional

property-that recently accessed elements can be re-accessed fast.

▪ It is said to be an efficient binary tree because it performs basic operations

such as insertion, search, and deletion in O(log(n)) amortized time.

▪ A splay tree consists of a binary tree, with no additional fields.

▪ When a node in a splay tree is accessed, it is rotated or ‘splayed’ to the root,

thereby changing the structure of the tree.
Splay Trees
▪ Since the most frequently accessed node is always moved closer to the starting
point of the search (or the root node), these nodes are therefore located
faster.

▪ A simple idea behind it is that if an element is accessed, it is likely that it will

be accessed again.

▪ In a splay tree, operations such as insertion, search, and deletion are combined
with one basic operation called splaying.

▪ Splaying the tree for a particular node rearranges the tree to place that node
at the root.

▪ A technique to do this is to first perform a standard binary tree search for

that node and then use rotations in a specific order to bring the node on top.
Splay Trees
Operations on Splay Trees

▪ We shall discuss the four main operations that are performed on a splay tree.

▪ These include splaying, insertion, search, and deletion.

Splaying
▪ When we access a node N, splaying is performed on N to move it to the root.

▪ To perform a splay operation, certain splay steps are performed where each
step moves N closer to the root.

▪ Splaying a particular node of interest after every access ensures that the
recently accessed nodes are kept closer to the root and the tree remains
roughly balanced, so that the desired amortized time bounds can be achieved.
Splay Trees

Each splay step depends on three factors:

▪ Whether N is the left or right child of its parent P.

▪ Whether P is the root or not, and if not.

▪ Whether P is the left or right child of its parent, G (N’s grandparent).

▪ Depending on these three factors, we have one splay step based on each factor.
Splay Trees

P N

N P
T3 T1

T1 T2
T2 T3
Zig Step:
▪ The zig operation is done when P (the parent of N) is the root of the splay
tree.

▪ In the zig step, the tree is rotated on the edge between N and P.

▪ Zig step is usually performed as the last step in a splay operation and only
when N has an odd depth at the beginning of the operation.
Splay Trees
P N
G

P G
T4 N P
T1

N
T3 T1 T2 T3 T4 G
T2

T1 T2
T3 T4
Zig-Zig Step:
▪ The zig–zig operation is performed when P is not the root.
▪ In addition to this, N and P are either both right or left children of their
parents.
▪ Figure shows the case where N and P are the left children.
▪ During the zig–zig step, first the tree is rotated on the edge joining P and its
parent G, and then again rotated on the edge joining N and P.
Splay Trees
G G N

P
T4 P G
N T4
T1 N
P T1 T2 T3 T4
T3
T2 T3

T1 T2
Zig-Zag Step:
▪ The zig–zag operation is performed when P is not the root.
▪ In addition to this, N is the right child of P and P is the left child of G or
vice versa.
▪ In zig–zag step, the tree is first rotated on the edge between N and P,
and then rotated on the edge between N and G.
Splay Trees
Inserting a Node in a Splay Tree

▪ Although the process of inserting a new node N into a splay tree begins in
the same way as we insert a node in a binary search tree, but after the
insertion, N is made the new root of the splay tree.

▪ The steps performed to insert a new node N in a splay tree can be given as
follows:
▪ Step 1 Search N in the splay tree. If the search is successful, splay at
the node N.

▪ Step 2 If the search is unsuccessful, add the new node N in such a way
that it replaces the NULL pointer reached during the search by a
pointer to a new node N. Splay the tree at N.

▪ See the class video for an example problem.

Splay Trees
Searching for a Node in a Splay Tree

▪ If a particular node N is present in the splay tree, then a pointer to N is

returned; otherwise a pointer to the null node is returned.

▪ The steps performed to search a node N in a splay tree include:

▪ Search down the root of the splay tree looking for N.
▪ If the search is successful, and we reach N, then splay the tree at N
and return a pointer to N.
▪ If the search is unsuccessful, i.e., the splay tree does not contain N,
then we reach a null node. Splay the tree at the last non-null node
reached during the search and return a pointer to null .

▪ See the class video for an example problem.

Splay Trees
Deleting a Node from a Splay Tree

▪ To delete a node N from a splay tree, we perform the following steps:

▪ Search for N that has to be deleted. If the search is unsuccessful,
splay the tree at the last non-null node encountered during the search.

▪ If the search is successful and N is not the root node, then let P be the
parent of N. Replace N by an appropriate descendent of P (as we do in
binary search tree). Finally splay the tree at P.

▪ See the class video for an example problem.

Splay Trees
The advantages of using a splay tree are:
▪ A splay tree gives good performance for search, insertion, and deletion operations.

▪ This advantage centers on the fact that the splay tree is a self-balancing and a
self-optimizing data structure in which the frequently accessed nodes are moved
closer to the root so that they can be accessed quickly.

▪ This advantage is particularly useful for implementing caches and

▪ garbage collection algorithms.

▪ Splay trees are considerably simpler to implement than the other self-balancing
binary search trees, such as red-black trees or AVL trees, while their average case
performance is just as efficient.
▪ Splay trees minimize memory requirements as they do not store any book-keeping
data.

▪ Unlike other types of self-balancing trees, splay trees provide good performance
(amortized O(log n)) with nodes containing identical keys.
Splay Trees
The disadvantages of using a splay tree are:

▪ While sequentially accessing all the nodes of a tree in a sorted order, the resultant tree
becomes completely unbalanced.

▪ This takes n accesses of the tree in which each access takes O(log n) time.

▪ For example, re-accessing the first node triggers an operation that in turn takes O(n)
operations to rebalance the tree before returning the first node.
▪
▪ Although this creates a significant delay for the final operation, the amortized
performance over the entire sequence is still O(log n).

▪ For uniform access, the performance of a splay tree will be considerably worse than a
somewhat balanced simple binary search tree.

▪ For uniform access, unlike splay trees, these other data structures provide worst-case
time guarantees and can be more efficient to use.
Problem Statement
Title: Querying in Wireless Sensor
Networks (WSN):

▪ Consider a scenario where WSN is

deployed to provide service to users
but owned by a person X – call him/her
as service provider.

▪ Specifically, we assume these are

deployed in habitat monitoring
applications to detect the
environmental conditions such as
floods, fire, snow, location of animals.

▪ What if fire accident happens?

Problem Statement
Cell
▪ Then the service provider or the cloud or
owner must immediately locate Block
(identify) the spot where the fire has
occurred and immediately send the
fire extinguishing personnel to put off
the fire.
Can we use any of the data
structure concepts that we
▪ Howstudied
to locate
sothe
far spot in effective
to locate the
manner? In the
sensor nodesense, in the least
of interest in
possible
thetime?
least possible time to
reach the fire spot and
▪ Assuming
takethat the entrance
necessary to the
actions?
field or target region is where our
robo is situated in the diagram.
Tracks
Sector
Problem Statement
▪ Ground work – the design steps for
development of the algorithm and
identification of appropriate data
structure to solve the given problem.

▪ Step 1: We a mechanism to identify

C11 C10
individual sensors (ID of sensor nodes) or
a group of sensors situated in same area C3 C2
(area ID). C9
C4 C1
▪ Here, we can mark in terms of sector, C5 C8
track and then finally the block/cell.
C7
▪ Once the cell is identified our job of C6

identification of the spot is done. Else

within each cell we need to identify
individual sensor node in case we need
to some inspection related to hardware
maintenance issue.
Problem Statement
▪ Step 2: Assume that each cell has equal number of sensor nodes (unlike in
the figure which shows unequal number of sensor nodes in each cell), say 5
sensors and each node having the following attributes and size of data:
▪ ID - 4 bytes
▪ Its depth from the BS - 4 bytes
▪ Its distance from the BS – 4 bytes
▪ Coordinates – 4+4 (for r and theta)
▪ Neighbor Details (such as IDs, depth values, distance values,
coordinates) (4 + 4 + 4 + 8 + 4 (number of neighbors))

▪ Total size of the details = 4 + 4 + 4 + 8 + 4 + 4 + 4 + 8 + 4 = 44 bytes.

Problem Statement
Sl. No. ID (4B) Depth (4B) Distance (4b) Radius (4B) Theta (4B) Neighbor …
1 1
2 2
3 3
4 4
5 5
.
.
.
1000 1000
Assume that the service provider X has, this data base which contains the
details of each node in the sensor network. Now to know the location of
the node(s) that reported fire accident, the service provider’s algorithm
has search the node that reported this event and then extract its location
(Radius and Theta) and then send the location coordinates to the robo to
put off the fire.
Problem Statement
▪ Assume that in worst case the node with ID 956 has identified the fire
accident in the forest. Then the algorithm has to make 955 comparisons to
find the ID of the node in the table and then retrieve the coordinates.

▪ Therefore, worst case time required to get the ID of a node is O(n), where n
is number of nodes in the network.

▪ Can we reduce this search time?

▪ Yes, if we choose binary search over the liner search. Then the worst case
search time is O(log2(n)).

▪ This suggests that we can use TREES as data structures to store the
information (that is given in the table) and then perform the following
operations: insert, delete, search, sort, find min and max, etc.
Problem Statement
▪ Now that you have identified the right data structure – the trees, your next
job is to identify the appropriate tree that can help us to solve our problem.

▪ Assuming that you have studied the following trees: Binary trees, Binary
Search Trees, AVL, Trees, Red-Black Trees, Splay Trees, Fibonacci Heaps,
B-Trees and B+ Trees, choose the right one to solve the problem.

▪ After identifying the right choice, give explanation why that is the best
choice to solve the given problem and why not other choices.

▪ Write a C++ program to simulate the tree that you identified as the right
choice and show how it solves our problem (the task of identifying the location
of the sensors with minimum time).

▪ How to write the report?

▪ See the pdf shared in RUBRICS shared with you all.
Extra materia for my reference.
 Father & Mother

Grand
Child Children

Grand Children Grand Child

Extra material
Trees Basics
▪ Data will be represented in multiple levels

▪ Now we will discuss a non-linear data Father & Mother

structure called TREE

▪ Each level contains a single data or

collection of data
Child Grand Children
▪ Trees are mainly used to represent data
containing a hierarchical relationship
between elements, for example, records,
family trees and table of contents
Grand Children Child
▪ Consider a parent-child relationship

198
 Logical Relationships
The structures of the data can be viewed in two ways:
▪ Physically:
▪ The physical data structure refers to the physical arrangement of the data
on the secondary storage device, usually disk.
▪ Typically, this physical structure is the concern of specialists who design
DBMSs.
▪ Analysts, programmers, and users are generally less concerned with the
physical structure than with the logical structure.

Note: You can skip this slide in case you are aware of the topic.
 Logical Relationships

▪ Logically:
▪ The logical data structure concerns how the data "seem" to be arranged and the
meanings of the data elements in relation to one another
▪ This structure, or model, is generally defined in terms of a schema - an overall
conceptual view of the logical relationships between the data elements in the system.
▪ It includes the names of the major elements, their attribute (features), and the logical
relationships between them

Note: You can skip this slide in case you are aware of the topic.
 Logical Relationships
▪ The figure below shows a schema of auto
(vehicle) parts store.
▪ It illustrates that relationships exist between Part # Description Cost
part numbers, types of cars, models, and
manufactures.
▪ The connecting lines indicate links and the
arrows the type of relationship.
Model
▪ For example, in this schema, manufacturer is
linked to part number, and the relationship in
one-to-many (a double-headed arrow implies
many and single-headed arrow one).
▪ That is, one manufacturer produces many part Type of Vehicle
numbers, but each part number has only one
manufacturer. There are also indirect links
indicated.
▪ A part number, for example, is linked to type Manufacturer
of vehicle through model.
 Abstract Data Type
▪ An Abstract Data Type (ATD) is an abstraction (idea) of a data structure which
provides only the interface to which a data structure must adhere to.
▪ The interface does not give any specific details about how something should be
implemented or in what programming language.
▪ Example
Abstraction (ADT) Implementation (DS)
List Dynamic array and Linked list
Queue Linked list based queue, Array based queue
and Stack base queue.
Map Tree map, Hash map or Hash table
Vehicle Golf card or bicycle or smart car

[Link]
Recap

From Kongani Sumanth (AP18110010413) CSE-G to Everyone:

11:22 AM
WhatsApp group link:

[Link]

Signal group link:

[Link]
PLTGE29FJfNpXEhADyWwmjdko5bVUr0qvz5RM
 8
45 45
2 7
36 63 63
36

4 6
27 54 72 54
1 39 3 27 39 72

5
70
1
 Objective: The objective(s) of this experiment is:
1) Reverse the given string with the help of
stacks that are implemented using arrays.

Once the file is uploaded, please click on the

SUBMIT button to make sure that the file is
submitted.

Please avoid the following verbs

Understand
Learn
Know
Form Syllabus copy + the slides that are shared in today’s lab.

Mid-1 pattern

15 MCQ * 1 = 15 marks

3 descriptive questions out of which you are supposed to

answer any 2.
2 * 5 = 10
15+10 =25

Reg_no [Link]