ADVANCED DATA STRUCTURES
LABORATORY
1. Introduction
Data Structures form the backbone of computer science and software engineering. While
basic data structures such as arrays, stacks, queues, linked lists, and trees provide
fundamental ways to organize and store data, modern computing problems demand more
efficient, scalable, and intelligent structures. This necessity leads to the study and
implementation of Advanced Data Structures, which are designed to handle complex
operations, large volumes of data, and real-time constraints effectively.
The Advanced Data Structures Laboratory is designed to provide hands-on experience in
implementing, analyzing, and optimizing advanced data structures. This laboratory
complements the theoretical understanding gained in data structures and algorithms courses
by allowing students to translate concepts into working programs. The lab emphasizes
algorithmic thinking, efficiency analysis, and practical problem-solving skills.
Through systematic experiments, students learn how advanced data structures improve
performance in applications such as databases, operating systems, compiler design, artificial
intelligence, networking, and large-scale data analytics.
2. Objectives of the Advanced Data Structures Lab
The primary objectives of the Advanced Data Structures Laboratory are:
1. To understand the need for advanced data structures beyond basic linear and non-
linear structures.
2. To design and implement efficient data structures for complex computational
problems.
3. To analyze time and space complexity of different data structure operations.
4. To develop problem-solving and algorithmic skills using advanced structures.
5. To provide exposure to real-world applications such as indexing, searching, graph
processing, and memory management.
6. To enhance programming skills using languages such as C, C++, Java, or Python.
7. To encourage modular, reusable, and optimized coding practices.
3. Learning Outcomes
Upon successful completion of the Advanced Data Structures Lab, students will be able to:
Implement advanced data structures such as balanced trees, heaps, graphs, and hash
tables.
Apply suitable data structures to solve real-world computational problems.
Analyze the performance of algorithms using asymptotic notations.
Compare different data structures based on efficiency and use cases.
Design optimized solutions for searching, sorting, and graph traversal problems.
Integrate data structures into larger software systems.
4. Overview of Advanced Data Structures
Advanced data structures extend basic structures to improve performance and support
specialized operations. The commonly studied advanced data structures include:
4.1 Balanced Trees
Balanced trees maintain height balance to ensure logarithmic time complexity for operations.
AVL Trees
Red-Black Trees
B-Trees and B+ Trees
4.2 Heaps
Heaps are specialized tree-based structures used primarily for priority queues.
Min Heap
Max Heap
Binomial Heap
Fibonacci Heap
4.3 Hashing Structures
Hashing provides fast data access through key-value mapping.
Hash Tables
Collision Resolution Techniques
Dynamic Hashing
4.4 Graph Data Structures
Graphs represent relationships among entities.
Adjacency Matrix
Adjacency List
Weighted and Directed Graphs
4.5 Disjoint Set (Union-Find)
Used for managing dynamic connectivity problems.
4.6 Tries and String Data Structures
Efficient for prefix-based searching.
Trie
Suffix Tree
Suffix Array
5. List of Experiments (Typical)
The Advanced Data Structures Lab usually consists of the following experiments:
1. Implementation of AVL Tree with insertion and deletion.
2. Implementation of Red-Black Tree operations.
3. Implementation of Binary Heap and Priority Queue.
4. Implementation of Hash Table using chaining and open addressing.
5. Implementation of Graph Traversals (BFS and DFS).
6. Implementation of Minimum Spanning Tree algorithms (Prim’s and Kruskal’s).
7. Implementation of Shortest Path algorithms (Dijkstra’s and Bellman-Ford).
8. Implementation of Disjoint Set operations using Union-Find.
9. Implementation of Trie for dictionary and prefix searching.
10. Implementation of B-Tree or B+ Tree for database indexing.
6. Detailed Description of Selected Experiments
6.1 AVL Tree Implementation
An AVL Tree is a self-balancing Binary Search Tree where the height difference between left
and right subtrees is at most one.
Operations Implemented:
Insertion
Deletion
Rotations (LL, RR, LR, RL)
Advantages:
Guaranteed O(log n) time for search, insert, and delete.
Suitable for applications requiring frequent searches.
6.2 Heap and Priority Queue
A heap is a complete binary tree satisfying the heap property.
Types:
Min Heap
Max Heap
Applications:
CPU scheduling
Dijkstra’s algorithm
Event-driven simulations
Operations:
Insert
Delete
Heapify
6.3 Hash Table Implementation
Hash tables provide constant-time average performance.
Collision Resolution Techniques:
Separate Chaining
Linear Probing
Quadratic Probing
Double Hashing
Applications:
Symbol tables
Caches
Database indexing
6.4 Graph Traversals
Graphs are used to model networks, social connections, and dependencies.
Traversal Algorithms:
Breadth First Search (BFS)
Depth First Search (DFS)
Applications:
Network routing
Web crawling
Cycle detection
6.5 Minimum Spanning Tree Algorithms
A Minimum Spanning Tree connects all vertices with minimum total edge weight.
Algorithms:
Prim’s Algorithm
Kruskal’s Algorithm
Applications:
Network design
Electrical circuit design
Cluster analysis
6.6 Shortest Path Algorithms
These algorithms compute the shortest path between nodes in a graph.
Algorithms:
Dijkstra’s Algorithm
Bellman-Ford Algorithm
Applications:
GPS navigation
Routing protocols
Game development
7. Tools and Programming Environment
The Advanced Data Structures Lab typically uses:
Programming Languages: C, C++, Java, Python
Operating Systems: Windows / Linux
Compilers: GCC, Turbo C++, JDK
Editors/IDEs: VS Code, Eclipse, Code::Blocks
Students are encouraged to write modular code, use meaningful variable names, and include
proper documentation.
8. Time and Space Complexity Analysis
An important component of the lab is analyzing the efficiency of data structures.
Best Case
Average Case
Worst Case
Common notations used:
Big-O (O)
Big-Theta (Θ)
Big-Omega (Ω)
Understanding complexity helps in selecting the appropriate data structure for a given
problem.
9. Applications of Advanced Data Structures
Advanced data structures play a vital role in many domains:
Databases: Indexing using B-Trees and Hashing
Operating Systems: Process scheduling using heaps
Artificial Intelligence: Graph search and state-space representation
Networking: Routing algorithms
Big Data Analytics: Efficient storage and retrieval
Compiler Design: Syntax trees and symbol tables
10. Evaluation Methodology
Student performance in the lab is evaluated based on:
Regular lab attendance
Successful execution of experiments
Viva-voce examinations
Record maintenance
Internal assessments
Evaluation emphasizes both correctness and efficiency of solutions.
11. Safety and Ethical Practices
Follow proper lab rules and discipline.
Avoid plagiarism in lab programs.
Ensure data integrity while performing experiments.
Respect intellectual property and academic honesty.
12. Challenges Faced in Advanced Data Structures Lab
Understanding complex algorithms
Debugging recursive and pointer-based programs
Managing memory efficiently
Visualizing data structures
These challenges help students develop resilience and strong analytical skills.
13. Conclusion
The Advanced Data Structures Laboratory is an essential component of modern computer
science education. It bridges the gap between theory and practice by enabling students to
implement and experiment with sophisticated data structures. Through systematic lab
exercises, students gain a deeper understanding of algorithmic efficiency, problem-solving
strategies, and real-world applications.
The knowledge and skills acquired in this lab prepare students for advanced courses,
research, and professional software development. Mastery of advanced data structures
enhances a student’s ability to design optimized and scalable solutions, making them
competent and industry-ready engineers.
EXPERIMENT 1: AVL TREE (INSERTION &
INORDER TRAVERSAL)
class Node:
def __init__(self, key):
[Link] = key
[Link] = None
[Link] = None
[Link] = 1
def height(node):
return [Link] if node else 0
def balance(node):
return height([Link]) - height([Link]) if node else 0
def right_rotate(y):
x = [Link]
T2 = [Link]
[Link] = y
[Link] = T2
[Link] = max(height([Link]), height([Link])) + 1
[Link] = max(height([Link]), height([Link])) + 1
return x
def left_rotate(x):
y = [Link]
T2 = [Link]
[Link] = x
[Link] = T2
[Link] = max(height([Link]), height([Link])) + 1
[Link] = max(height([Link]), height([Link])) + 1
return y
def insert(node, key):
if not node:
return Node(key)
if key < [Link]:
[Link] = insert([Link], key)
elif key > [Link]:
[Link] = insert([Link], key)
else:
return node
[Link] = max(height([Link]), height([Link])) + 1
b = balance(node)
if b > 1 and key < [Link]:
return right_rotate(node)
if b < -1 and key > [Link]:
return left_rotate(node)
if b > 1 and key > [Link]:
[Link] = left_rotate([Link])
return right_rotate(node)
if b < -1 and key < [Link]:
[Link] = right_rotate([Link])
return left_rotate(node)
return node
def inorder(root):
if root:
inorder([Link])
print([Link], end=" ")
inorder([Link])
root = None
data = [10, 20, 30, 40, 50, 25]
for x in data:
root = insert(root, x)
print("Inorder Traversal:")
inorder(root)
EXPERIMENT 2: MIN HEAP
class MinHeap:
def __init__(self):
[Link] = []
def insert(self, value):
[Link](value)
[Link]()
def display(self):
print([Link])
h = MinHeap()
for x in [5, 3, 8, 1, 2]:
[Link](x)
print("Min Heap:")
[Link]()
EXPERIMENT 3: HASH TABLE (LINEAR PROBING)
SIZE = 10
table = [-1] * SIZE
def insert(key):
index = key % SIZE
while table[index] != -1:
index = (index + 1) % SIZE
table[index] = key
keys = [23, 43, 13, 27]
for k in keys:
insert(k)
print("Hash Table:")
for i in range(SIZE):
print(i, ":", table[i])
EXPERIMENT 4: BREADTH FIRST SEARCH (BFS)
from collections import deque
graph = {
0: [1, 2],
1: [2],
2: [3],
3: []
}
def bfs(start):
visited = set()
queue = deque([start])
[Link](start)
while queue:
v = [Link]()
print(v, end=" ")
for n in graph[v]:
if n not in visited:
[Link](n)
[Link](n)
print("BFS Traversal:")
bfs(0)
EXPERIMENT 5: DEPTH FIRST SEARCH (DFS)
graph = {
0: [1, 2],
1: [3],
2: [],
3: []
}
visited = set()
def dfs(v):
[Link](v)
print(v, end=" ")
for n in graph[v]:
if n not in visited:
dfs(n)
print("DFS Traversal:")
dfs(0)
EXPERIMENT 6: PRIM’S ALGORITHM
INF = 999
graph = [
[0, 2, INF, 6, INF],
[2, 0, 3, 8, 5],
[INF, 3, 0, INF, 7],
[6, 8, INF, 0, 9],
[INF, 5, 7, 9, 0]
]
n = len(graph)
selected = [False] * n
selected[0] = True
mincost = 0
for _ in range(n - 1):
minimum = INF
x = y = 0
for i in range(n):
if selected[i]:
for j in range(n):
if not selected[j] and graph[i][j] < minimum:
minimum = graph[i][j]
x, y = i, j
selected[y] = True
mincost += minimum
print("Minimum Cost:", mincost)
EXPERIMENT 7: KRUSKAL’S ALGORITHM
parent = {}
def find(i):
if parent[i] == i:
return i
return find(parent[i])
def union(i, j):
parent[find(i)] = find(j)
edges = [
(1, 0, 1),
(3, 0, 2),
(2, 1, 2),
(4, 1, 3)
]
[Link]()
vertices = {0, 1, 2, 3}
for v in vertices:
parent[v] = v
mincost = 0
for w, u, v in edges:
if find(u) != find(v):
union(u, v)
mincost += w
print("Minimum Cost:", mincost)
EXPERIMENT 8: DIJKSTRA’S ALGORITHM
INF = 999
graph = [
[0, 4, INF, INF],
[4, 0, 8, INF],
[INF, 8, 0, 7],
[INF, INF, 7, 0]
]
n = len(graph)
src = 0
dist = graph[src][:]
visited = [False] * n
visited[src] = True
for _ in range(n - 1):
min_dist = INF
u = 0
for i in range(n):
if not visited[i] and dist[i] < min_dist:
min_dist = dist[i]
u = i
visited[u] = True
for v in range(n):
if dist[u] + graph[u][v] < dist[v]:
dist[v] = dist[u] + graph[u][v]
print("Shortest distances:", dist)
EXPERIMENT 9: DISJOINT SET (UNION–FIND)
parent = {}
def make_set(n):
for i in range(n):
parent[i] = i
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(a, b):
parent[find(a)] = find(b)
make_set(5)
union(0, 1)
union(1, 2)
print("Find(2):", find(2))
EXPERIMENT 10: TRIE (INSERT & SEARCH)
class TrieNode:
def __init__(self):
[Link] = {}
[Link] = False
class Trie:
def __init__(self):
[Link] = TrieNode()
def insert(self, word):
cur = [Link]
for c in word:
if c not in [Link]:
[Link][c] = TrieNode()
cur = [Link][c]
[Link] = True
def search(self, word):
cur = [Link]
for c in word:
if c not in [Link]:
return False
cur = [Link][c]
return [Link]
t = Trie()
[Link]("data")
[Link]("structure")
print("Search data:", [Link]("data"))
print("Search algo:", [Link]("algo"))