Mastering Data Structures: The Ultimate Revision Guide

From Linear Basics to Non-Linear Efficiency

Whether you are preparing for a coding interview or brushing up on Computer Science fundamentals, understanding the distinction between Linear and Non-Linear Data Structures is crucial. In this guide, we break down the mechanics of Linklists, Stacks, Queues, and the complexity of Trees and AVL Trees.

https://youtu.be/svBWmkKS2MI

1. Linear Data Structures: Sequential Logic

In linear data structures, elements are arranged in a sequence where each element is connected to its previous and next adjacent elements.

Linked Lists

A Linked List consists of nodes where each node contains data and a pointer (reference) to the next node in the sequence.

• Best for: Dynamic memory allocation and frequent insertions/deletions.

• Key Fact: Unlike arrays, linked lists do not require contiguous memory locations.

Stacks (LIFO)

The Stack follows the Last-In, First-Out principle. Imagine a stack of plates; the last one you put on top is the first one you take off.

• Operations: Push() (add) and Pop() (remove).

• Use Case: Undo mechanisms in editors and function call management in recursion.

Queues (FIFO)

A Queue follows the First-In, First-Out principle. It’s like a line at a grocery store—the first person in line is the first to be served.

• Operations: Enqueue() (add to rear) and Dequeue() (remove from front).

• Use Case: CPU scheduling and handling website traffic.

2. Non-Linear Data Structures: Hierarchical Logic

In non-linear structures, data is not arranged sequentially. Instead, an element can be connected to several other elements, representing a hierarchical relationship.

Trees

A Tree is a collection of nodes connected by edges, starting from a single Root node.

• Binary Tree: Each node has at most two children (Left and Right).

• Terminology: Parent, Child, Leaf (node with no children), and Subtree.

VL Trees (Self-Balancing)

A standard Binary Search Tree (BST) can become “skewed,” losing its efficiency. An AVL Tree solves this by being self-balancing.

• The Balance Factor: For any node, the height difference between the left and right subtrees must be -1, 0, or +1.

• Rotations: If a tree becomes unbalanced after insertion or deletion, it performs LL, RR, LR, or RL rotations to maintain $O(\log n)$ search time.

3. Comparison Table: Linear vs. Non-Linear

4. Key Takeaways for Revision

• Stacks are LIFO; Queues are FIFO.

• Linked Lists are preferred over arrays when the size of data is unknown.

• Trees represent hierarchical data (like a file system).

• AVL Trees ensure that the search time complexity remains O(\log n) by staying balanced.

Data Structures (CLO-2)

Objective: Use non-linear data structures to solve computing problems.

Topics Covered

● Binary Search Tree (BST)
● Tree Balancing Technique (AVL Tree)

Instructions

● Attempt all questions.
● Provide step-by-step explanation, diagrams, and code (C++ preferred) where
required.
● Emphasis will be on problem-solving using trees, not only definitions.
● Draw trees neatly (hand-drawn or software-based).

Question 1: University Student Record System (BST Application)

A university maintains student records based on student ID. The system must support fast
searching, insertion, and deletion.
Scenario
You are tasked to design a system where:
● Each student has a unique ID.
● Records are inserted dynamically.
● The system frequently searches for specific students.

Tasks

1. Construct a Binary Search Tree (BST) using the following student IDs:
50, 30, 70, 20, 40, 60, 80

2. Show the tree structure after each insertion.

3. Perform the following operations and update the tree:

• Delete student with ID = 30
• Search for a student with ID = 60

4. Explain why BST is suitable for this system.

5. Write a C++ program to implement:

• Insertion
• Deletion
• Search in BST

Question 2: E-Commerce Product Ranking System (AVL Tree Need)

An e-commerce platform ranks products based on sales score. Data is continuously updated, causing an imbalance in a normal BST.

Scenario

Frequent insertions result in degraded performance due to skewed trees.

Tasks

1. Insert the following product scores into a BST:
10, 20, 30, 40, 50

2. Draw the resulting tree and explain why it becomes unbalanced.

3. Convert this BST into an AVL Tree by applying appropriate rotations:

• Identify imbalance cases
• Apply rotations step-by-step

4. Draw the balanced AVL Tree after each rotation.

5. Explain how AVL improves search efficiency over BST.

Question 3: Hospital Emergency System (AVL Rotations in Real-Time)

A hospital prioritizes patients based on severity level (higher value = higher priority).

Scenario

Patients arrive in the following order:
30, 20, 10, 25, 28

This causes multiple imbalances in the tree.

Tasks

1. Insert the values into an AVL tree step-by-step.

2. Identify and label each imbalance case:
○ LL (Left-Left)
○ RR (Right-Right)
○ LR (Left-Right)
○ RL (Right-Left)

3. Apply appropriate rotations and redraw the tree after each step.

4. Explain how AVL ensures logarithmic time complexity in emergency systems.

5. Write a C++ implementation of AVL Tree insertion with rotations.

Question 4: File System Directory Management (BST vs AVL Analysis)

A file system stores directories using hierarchical structures.

Scenario

Two systems are implemented:
● System A uses BST
● System B uses AVL Tree
Files are inserted in sorted order, causing worst-case behavior in BST.

Tasks

1. Insert the following directory IDs in both BST and AVL:
5, 10, 15, 20, 25, 30
2. Draw both trees.

3. Compare:
○ Height of BST vs AVL
○ Search time complexity
○ Performance in worst-case scenarios

4. Explain which structure is better for:
○ Large-scale file systems
○ Real-time applications

5. Justify your answer with technical reasoning.

Marking Scheme

Criteria Marks
Concept Understanding: 2
Tree Construction & Diagrams: 2
Algorithm & Logic: 2
Code Implementation: 1
Explanation & Justification: 3
Total 10 Marks