Unit 2: Advanced trees
Data Structures-II notes · PTU syllabus (UGCC2510)
On this page
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
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.
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.
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.
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.
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.
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.
Topic 5
Heap trees
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.
- 1Build a max-heap from the array
- 2Swap the root with the last element
Largest goes to the end
- 3Reduce heap size by one
- 4Heapify the root
Restore the heap property
- 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
- Q1.Define an AVL tree and balance factor.
- Q2.When is an LR rotation needed?
- Q3.List the properties of a B-tree of order m.
- Q4.Differentiate between a B-tree and a B+ tree.
- Q5.State two rules of a red-black tree.
- Q6.Differentiate between a max-heap and a min-heap.
Long-answer questions
- Q1.Construct an AVL tree by inserting 10, 20, 30, 25, 28, 27, 5 and show every rotation.
- Q2.Explain B-trees with insertion and node splitting, using an example of order 3 or 5.
- Q3.Explain red-black trees and their properties.
- 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.
