Unit 2 of 4 · BCA Sem 3

Unit 2: Advanced trees

Data Structures-II notes · PTU syllabus (UGCC2510)

4 min read5 topics10 exam questions
On this page
  1. Unit summary
  2. AVL (height-balanced) trees
  3. M-way search trees and B-trees
  4. B+ trees
  5. Red-black trees
  6. Heap trees
  7. Key terms
  8. Quick revision
  9. Important questions

Unit summary

An ordinary BST can become lopsided and slow. Advanced trees keep themselves balanced or are designed for disk storage. This unit covers AVL trees, M-way trees, B-trees, B+ trees, red-black trees and heaps.

After this unit you can

  • Calculate balance factors and perform AVL rotations
  • Explain M-way search trees, B-trees and B+ trees
  • State the properties of red-black trees
  • Build max-heaps and min-heaps and explain heap sort

PTU syllabus topics

  • Height-balanced (AVL) trees — insertion and deletion
  • M-way trees
  • B-Trees
  • B+ Trees
  • Red-Black trees
  • Heap trees
1

Topic 1

AVL (height-balanced) trees

An AVL tree (Adelson-Velsky and Landis) is a BST in which, for every node, the heights of the left and right subtrees differ by at most 1.

  • Balance factor (BF) = height(left subtree) − height(right subtree); it must be −1, 0 or +1.
  • After an insertion or deletion makes some BF equal to ±2, the tree is rebalanced with rotations.
ComparisonAVL rotations
Imbalance caused by
Fix

LL

Insertion in the left subtree of the left child

Single right rotation

RR

Insertion in the right subtree of the right child

Single left rotation

LR

Insertion in the right subtree of the left child

Left rotation, then right rotation

RL

Insertion in the left subtree of the right child

Right rotation, then left rotation

Example

Inserting 30, 20, 10 into an empty AVL tree makes node 30 have BF = +2 (LL case); a right rotation makes 20 the root with children 10 and 30.

Exam tip

Match the four AVL imbalance cases to their rotation: LL → single right rotation; RR → single left rotation; LR → left rotation on the child, then right rotation; RL → right rotation on the child, then left rotation.

2

Topic 2

M-way search trees and B-trees

An M-way search tree lets a node hold up to M − 1 keys and have up to M children, so the tree is much shorter — ideal for data stored on disk. A B-tree of order m is a balanced M-way search tree in which:

  • Every node has at most m children and m − 1 keys.
  • Every node except the root has at least ⌈m/2⌉ children.
  • The root has at least 2 children (unless it is a leaf).
  • All leaves are at the same level.
  • Keys within a node are sorted.

When a node overflows during insertion, it splits and the middle key moves up to the parent.

Example

Building a B-tree of order 3 (at most 2 keys per node): insert 10 and 20 → one node [10, 20]. Insert 30 → [10, 20, 30] overflows, so it splits: the middle key 20 moves up as the new root, with children [10] and [30]. Insert 40 → [30, 40]. Insert 50 → [30, 40, 50] overflows; 40 moves up to the root, which becomes [20, 40] with three leaves [10], [30] and [50] — all at the same level.

3

Topic 3

B+ trees

A B+ tree is a variation of the B-tree used in databases and file systems:

  • All data records (keys with data) are stored in the leaves; internal nodes hold only keys for navigation.
  • Leaves are linked together, so range queries and sequential access are fast.
ComparisonB-tree vs B+ tree
B-tree
B+ tree

Data stored in

All nodes

Leaf nodes only

Leaf links

No

Leaves linked in sequence

Range search

Slower

Fast

Used in

General indexing

Database and file-system indexes

Example

Why databases use B+ trees: all records are in the leaf nodes, and the leaves are linked. A query for roll numbers 100 to 200 finds 100 by going down the tree once and then follows the leaf links, without returning to the root.

Exam tip

B-tree: keys and data in all nodes. B+ tree: data only in leaves, which are linked for range queries.

4

Topic 4

Red-black trees

A red-black tree is a self-balancing BST in which each node is coloured red or black, following these rules:

  • The root is black, and every leaf (NULL) is black.
  • A red node cannot have a red child (no two reds in a row).
  • Every path from a node to its descendant leaves has the same number of black nodes.

These rules keep the tree approximately balanced (height at most 2 log(n + 1)), so operations take O(log n). It needs fewer rotations than an AVL tree on insertions and deletions.

Example

Why balance matters: inserting 1 to 7 in order into a plain BST makes a chain of height 7. A red-black tree recolours and rotates nodes, keeping height near log₂ n, so searches stay fast.

Exam tip

Rules: root black, no two reds in a row, equal black height on every path.

5

Topic 5

Heap trees

GraphMin-heap: every parent is smaller than its children
820123525

Stored as an array [8, 20, 12, 35, 25]: children of index i are 2i+1 and 2i+2. Insert and delete-min take O(log n)

A heap is a complete binary tree that satisfies the heap property:

  • Max-heap: every parent ≥ its children; the largest value is at the root.
  • Min-heap: every parent ≤ its children; the smallest value is at the root.

Heaps are stored in arrays and are used for priority queues and heap sort.

Example

Inserting into a max-heap stored in an array: heap = [50, 30, 40, 10, 20] (index 0 to 4). Insert 45 at the end (index 5). Its parent is at (5 − 1) ÷ 2 = index 2, value 40; 45 > 40, so swap → [50, 30, 45, 10, 20, 40]. The new parent is index 0, value 50; 45 < 50, so stop. The heap property is restored in at most log₂ n swaps.

Exam tip

For a heap stored in an array from index 0: the children of node i are at 2i + 1 and 2i + 2, and its parent is at (i − 1) ÷ 2 (integer division). If the array starts at index 1, use 2i, 2i + 1 and i ÷ 2.

ProcessHeap sort
  1. 1Build a max-heap from the array
  2. 2Swap the root with the last element

    Largest goes to the end

  3. 3Reduce heap size by one
  4. 4Heapify the root

    Restore the heap property

  5. 5Repeat until one element remains

Heap sort runs in O(n log n) time in all cases.

Key terms

AVL tree
A BST whose node balance factors are −1, 0 or +1
Balance factor
Height of left subtree minus height of right subtree
B-tree
A balanced M-way tree with all leaves at the same level
B+ tree
A B-tree variant storing data only in linked leaves
Heap
A complete binary tree with the max- or min-heap property

Quick revision

  • AVL BF ∈ {−1, 0, +1}; rotations LL, RR, LR, RL.
  • B-tree of order m: max m − 1 keys per node; split on overflow.
  • B+ tree: data only in leaves, leaves linked — used in databases.
  • Red-black: no two consecutive reds; equal black height.
  • Heap sort is O(n log n).

Important exam questions

Practice questions written to the PTU exam pattern for this unit's syllabus: short answers (Section A style) and long answers (Sections B and C style).

Short-answer questions

  1. Q1.Define an AVL tree and balance factor.
  2. Q2.When is an LR rotation needed?
  3. Q3.List the properties of a B-tree of order m.
  4. Q4.Differentiate between a B-tree and a B+ tree.
  5. Q5.State two rules of a red-black tree.
  6. Q6.Differentiate between a max-heap and a min-heap.

Long-answer questions

  1. Q1.Construct an AVL tree by inserting 10, 20, 30, 25, 28, 27, 5 and show every rotation.
  2. Q2.Explain B-trees with insertion and node splitting, using an example of order 3 or 5.
  3. Q3.Explain red-black trees and their properties.
  4. Q4.Explain heap sort with an example and find its complexity.

Stuck on this unit?

Message SBS on WhatsApp for help with Data Structures-II, or to ask about studying BCA at Synetic.

WhatsApp us