Advanced Trees
Overview
The three advanced tree structures each solve a distinct problem:
STRUCTURE PROBLEM SOLVED TIME GUARANTEE
────────────────────────────────────────────────────────────────────────
Segment Tree Range queries + point updates O(log n) per op
on an array (sum, min, max)
AVL Tree Self-balancing BST — O(log n) worst case
guaranteed height after for search, insert,
every insert/delete delete
Red-Black Tree Self-balancing BST with fewer O(log n) worst case
rotations per write operation — with lower rotation
used in standard libraries overhead
All three guarantee O(log n) operations.
The difference is the tradeoff between balance strictness and write cost.
Part 1: Segment Tree
What It Solves
Given an array, answer range queries (sum/min/max of elements from index l to r) and handle point updates efficiently. Naive: O(n) per query. Segment tree: O(log n) per query and O(log n) per update.
Array: [1, 3, 5, 7, 9, 11] (indices 0–5)
Segment tree (range sum):
[0,5] = 36
/ \
[0,2] = 9 [3,5] = 27
/ \ / \
[0,1]=4 [2,2]=5 [3,4]=16 [5,5]=11
/ \ / \
[0,0]=1 [1,1]=3 [3,3]=7 [4,4]=9
Each node stores: sum of arr[ql..qr]
Leaf nodes: individual array elements.
Internal nodes: sum of their children.
Query sum [1,4]:
[0,5]: partial overlap → recurse
[0,2]: partial overlap → recurse
[0,1]: no overlap with [1,4]? NO — [0,1] ∩ [1,4] = [1,1] → partial → recurse
[0,0]: no overlap with [1,4] → return 0
[1,1]: full overlap → return 3
[2,2]: full overlap → return 5
[3,5]: partial overlap → recurse
[3,4]: full overlap → return 16
[5,5]: no overlap with [1,4] → return 0
Total: 0 + 3 + 5 + 16 + 0 = 24 ✓ (arr[1]+arr[2]+arr[3]+arr[4] = 3+5+7+9 = 24)
Build, Query, Update
1public class SegmentTree {
2 private int[] tree;
3 private int n;
4
5 public SegmentTree(int[] arr) {
6 n = arr.length;
7 tree = new int[4 * n]; // 4n is safe for any n
8 build(arr, 0, 0, n - 1);
9 }
10
11 // Build — O(n)
12 private void build(int[] arr, int node, int start, int end) {
13 if (start == end) {
14 tree[node] = arr[start]; // Leaf
15 } else {
16 int mid = (start + end) / 2;
17 int left = 2 * node + 1;
18 int right = 2 * node + 2;
19 build(arr, left, start, mid);
20 build(arr, right, mid + 1, end);
21 tree[node] = tree[left] + tree[right]; // Sum of children
22 }
23 }
24
25 // Range sum query [l, r] — O(log n)
26 public int query(int l, int r) {
27 return queryHelper(0, 0, n - 1, l, r);
28 }
29
30 private int queryHelper(int node, int start, int end, int l, int r) {
31 if (r < start || end < l) return 0; // No overlap → identity
32 if (l <= start && end <= r) return tree[node]; // Full overlap → return
33 int mid = (start + end) / 2;
34 int left = queryHelper(2*node+1, start, mid, l, r);
35 int right = queryHelper(2*node+2, mid+1, end, l, r);
36 return left + right; // Partial → recurse both
37 }
38
39 // Point update: set arr[idx] = val — O(log n)
40 public void update(int idx, int val) {
41 updateHelper(0, 0, n - 1, idx, val);
42 }
43
44 private void updateHelper(int node, int start, int end, int idx, int val) {
45 if (start == end) {
46 tree[node] = val; // Leaf: update directly
47 } else {
48 int mid = (start + end) / 2;
49 if (idx <= mid) updateHelper(2*node+1, start, mid, idx, val);
50 else updateHelper(2*node+2, mid+1, end, idx, val);
51 tree[node] = tree[2*node+1] + tree[2*node+2]; // Recompute
52 }
53 }
54
55 public static void main(String[] args) {
56 int[] arr = {1, 3, 5, 7, 9, 11};
57 SegmentTree st = new SegmentTree(arr);
58
59 System.out.println("Sum [0,5]: " + st.query(0, 5)); // 36
60 System.out.println("Sum [1,4]: " + st.query(1, 4)); // 24
61 System.out.println("Sum [2,3]: " + st.query(2, 3)); // 12
62
63 st.update(1, 10); // arr[1] = 10 (was 3)
64 System.out.println("After update[1]=10:");
65 System.out.println("Sum [0,5]: " + st.query(0, 5)); // 43
66 System.out.println("Sum [1,4]: " + st.query(1, 4)); // 31
67 }
68}Output:
Sum [0,5]: 36
Sum [1,4]: 24
Sum [2,3]: 12
After update[1]=10:
Sum [0,5]: 43
Sum [1,4]: 31
Range Minimum Variant
Change the combine operation: sum → min
Build: tree[node] = min(tree[left], tree[right])
Query: return 0 (identity) → return INT_MAX (identity for min)
return min(left_result, right_result) instead of sum
Array: [3, 1, 4, 1, 5, 9, 2, 6]
Min query [2,5]: min(4,1,5,9) = 1
Min query [0,7]: min of all = 1
Lazy Propagation — Range Updates
PROBLEM: update all elements in range [l,r] by adding delta. Without lazy: O(n) — update each leaf individually. With lazy: O(log n) — defer updates until needed. LAZY ARRAY: lazy[node] = pending value to add to all leaves under this node. PUSH DOWN: before accessing children, propagate lazy to them. tree[child] += lazy[node] × (child's range size) lazy[child] += lazy[node] lazy[node] = 0 Range update [1,3] += 5 on [1,3,5,7,9]: Mark lazy at the covering nodes, not individual leaves. Query later: push lazy down only when needed. O(log n) per range update instead of O(n).
Part 2: AVL Tree
The Balance Factor
An AVL tree is a BST that maintains the balance factor (height(left) − height(right)) within {−1, 0, +1} at every node after every insert and delete.
BALANCED AVL (all BF in {-1, 0, +1}):
8 BF=0
/ \
4 12 BF=0 at 4, BF=0 at 12
/ \ / \
2 6 10 14 BF=0 at all leaves
UNBALANCED after inserting 1:
8 BF=+2 ← VIOLATION
/
4 BF=+1
/
2 BF=+1
/
1 BF=0
Left-Left case → Right rotation at 8.
The Four Rotation Cases
CASE LL (Left-Left) — right rotate at violation node:
Violation BF=+2, left child BF=+1:
z(BF=+2) y
/ / \
y(BF=+1) → x z
/
x
Right rotate at z: y becomes new root, z becomes y's right child.
──────────────────────────────────────────────────────────────
CASE RR (Right-Right) — left rotate at violation node:
z(BF=-2) y
\ / \
y(BF=-1) → z x
\
x
Left rotate at z.
──────────────────────────────────────────────────────────────
CASE LR (Left-Right) — left rotate child, then right rotate violation:
z(BF=+2) z(BF=+2) x
/ / / \
y(BF=-1) → x(BF=+1) → y z
\ /
x y
Step 1: Left rotate at y. Step 2: Right rotate at z.
──────────────────────────────────────────────────────────────
CASE RL (Right-Left) — right rotate child, then left rotate violation:
z(BF=-2) z(BF=-2) x
\ \ / \
y(BF=+1) → x(BF=-1) → z y
/ \
x y
Step 1: Right rotate at y. Step 2: Left rotate at z.
MEMORY AID:
LL → single Right rotation
RR → single Left rotation
LR → Left then Right rotation
RL → Right then Left rotation
1public class AVLTree {
2
3 private static class Node {
4 int val, height;
5 Node left, right;
6 Node(int v) { val = v; height = 1; }
7 }
8
9 private Node root;
10
11 private int height(Node n) { return n == null ? 0 : n.height; }
12 private int bf(Node n) { return n == null ? 0 : height(n.left) - height(n.right); }
13
14 private void updateHeight(Node n) {
15 n.height = 1 + Math.max(height(n.left), height(n.right));
16 }
17
18 // Right rotation (fixes LL case)
19 private Node rotateRight(Node z) {
20 Node y = z.left;
21 Node T3 = y.right;
22 y.right = z; // z becomes y's right child
23 z.left = T3; // T3 becomes z's left child
24 updateHeight(z);
25 updateHeight(y);
26 return y; // y is new root
27 }
28
29 // Left rotation (fixes RR case)
30 private Node rotateLeft(Node z) {
31 Node y = z.right;
32 Node T2 = y.left;
33 y.left = z;
34 z.right = T2;
35 updateHeight(z);
36 updateHeight(y);
37 return y;
38 }
39
40 // Balance node after insert — apply appropriate rotation
41 private Node balance(Node z) {
42 updateHeight(z);
43 int bf = bf(z);
44
45 if (bf > 1) {
46 // Left heavy
47 if (bf(z.left) < 0) z.left = rotateLeft(z.left); // LR case
48 return rotateRight(z); // LL or LR
49 }
50
51 if (bf < -1) {
52 // Right heavy
53 if (bf(z.right) > 0) z.right = rotateRight(z.right); // RL case
54 return rotateLeft(z); // RR or RL
55 }
56
57 return z; // Already balanced
58 }
59
60 public void insert(int val) { root = insert(root, val); }
61
62 private Node insert(Node node, int val) {
63 if (node == null) return new Node(val);
64
65 if (val < node.val) node.left = insert(node.left, val);
66 else if (val > node.val) node.right = insert(node.right, val);
67 else return node; // Duplicate — no insert
68
69 return balance(node);
70 }
71
72 // Search — O(log n) guaranteed
73 public boolean search(int val) {
74 Node curr = root;
75 while (curr != null) {
76 if (val == curr.val) return true;
77 else if (val < curr.val) curr = curr.left;
78 else curr = curr.right;
79 }
80 return false;
81 }
82
83 public int height() { return height(root); }
84
85 private void inorder(Node n, java.util.List<Integer> r) {
86 if (n == null) return; inorder(n.left, r); r.add(n.val); inorder(n.right, r);
87 }
88
89 public java.util.List<Integer> inorder() {
90 java.util.List<Integer> r = new java.util.ArrayList<>();
91 inorder(root, r); return r;
92 }
93
94 public static void main(String[] args) {
95 AVLTree avl = new AVLTree();
96 // Inserting in order — would degenerate in a plain BST
97 for (int v : new int[]{10, 20, 30, 40, 50, 25}) {
98 avl.insert(v);
99 }
100 System.out.println("Inorder: " + avl.inorder()); // [10,20,25,30,40,50]
101 System.out.println("Height: " + avl.height()); // 3 (balanced!)
102 System.out.println("Search 25: " + avl.search(25)); // true
103 System.out.println("Search 99: " + avl.search(99)); // false
104 }
105}Output:
Inorder: [10, 20, 25, 30, 40, 50]
Height: 3
Search 25: true
Search 99: false
Part 3: Red-Black Tree
The Five Rules
FIVE RED-BLACK TREE RULES:
Rule 1: Every node is RED or BLACK.
Rule 2: The ROOT is BLACK.
Rule 3: Every NULL (sentinel) leaf is BLACK.
Rule 4: If a node is RED, both its children are BLACK.
(No two consecutive red nodes on any root-to-leaf path)
Rule 5: Every path from a node to any null descendant leaf
has the same number of BLACK nodes (black-height).
These five rules together guarantee: height ≤ 2 × log₂(n+1) = O(log n).
VALID Red-Black Tree (B=Black, R=Red):
10(B) ← root, BLACK (rule 2)
/ \
7(R) 15(B) ← 7 is RED — children must be BLACK (rule 4)
/ \ \
6(B) 9(B) 20(R) ← 6,9 are BLACK children of RED 7 ✓
Black-height from root:
root→7→6→NULL: B + B + B = 3 blacks
root→7→9→NULL: B + B + B = 3 blacks
root→15→20→NULL: B + B + B = 3 blacks ✓ (rule 5 satisfied)
WHY THE RULES GUARANTEE O(log n) HEIGHT:
Shortest path: all black nodes = black-height (bh)
Longest path: alternating R-B = 2 × bh (rule 4 prevents consecutive reds)
So: max height ≤ 2 × min height → height = O(log n)
Insertion Cases
After inserting a RED node, fix violations using recolor and rotations.
Uncle = parent's sibling.
CASE 1: Uncle is RED
Recolor parent and uncle to BLACK; grandparent to RED.
Move up and check grandparent.
Before: G(B) After: G(R)
/ \ / \
P(R) U(R) → P(B) U(B)
/ /
N(R) N(R) ← continue from G
CASE 2: Uncle is BLACK, N is inner child (LR or RL)
Rotate to convert to Case 3.
LR case: G(B) After left rotate at P: G(B)
/ /
P(R) → N(R)
\ /
N(R) P(R) ← now Case 3
CASE 3: Uncle is BLACK, N is outer child (LL or RR)
Rotate grandparent; swap colors of parent and grandparent.
LL case: G(B) After right rotate at G: P(B)
/ / \
P(R) → N(R) G(R)
/
N(R)
AVL vs RED-BLACK: SIDE-BY-SIDE COMPARISON
Property AVL Tree Red-Black Tree
──────────────────────────────────────────────────────────────
Balance criterion |h(L) - h(R)| ≤ 1 Max path ≤ 2 × min path
Height guarantee ≤ 1.44 log₂(n) ≤ 2 log₂(n+1)
Search speed Faster (shorter height) Slightly slower
Rotations per insert O(log n) worst case At most 2
Rotations per delete O(log n) worst case At most 3
Write performance Worse Better
Memory per node Height field 1-bit colour flag
Used in Read-heavy databases Java TreeMap, C++ std::map,
Linux kernel, Python 3.9+ dicts
Best for Lookup-intensive General-purpose ordered map/set
Segment Tree vs Prefix Sum vs Fenwick Tree
PROBLEM: range sum queries + point updates on an array.
Prefix Sum Fenwick Tree Segment Tree
──────────────────────────────────────────────────────
Build O(n) O(n) O(n)
Range query O(1) O(log n) O(log n)
Point update O(n) O(log n) O(log n)
Range update O(n) O(n) O(log n)*
Space O(n) O(n) O(n)
Implementation Simplest Moderate More code
*with lazy propagation
USE WHEN:
Prefix sum: No updates needed; only queries
Fenwick tree: Point updates + range sum queries (simpler code than segment tree)
Segment tree: Range updates OR non-sum queries (min, max, GCD, AND, OR)
OR when you need lazy propagation
Complexity Summary
Segment Tree
| Operation | Time | Space | Notes |
|---|---|---|---|
| Build | O(n) | O(n) | Allocate 4n array |
| Range query | O(log n) | O(log n) | Recursion stack depth |
| Point update | O(log n) | O(log n) | Update leaf + ancestors |
| Range update (lazy) | O(log n) | O(n) | Extra lazy array |
AVL Tree
| Operation | Time | Space | Notes |
|---|---|---|---|
| Search | O(log n) | O(1) | Height ≤ 1.44 log n |
| Insert | O(log n) | O(log n) | At most O(log n) rotations |
| Delete | O(log n) | O(log n) | Rebalance up to root |
| Height | O(1) | O(1) | Stored in each node |
Red-Black Tree
| Operation | Time | Space | Notes |
|---|---|---|---|
| Search | O(log n) | O(1) | Height ≤ 2 log n |
| Insert | O(log n) | O(1) | At most 2 rotations |
| Delete | O(log n) | O(1) | At most 3 rotations |
Common Mistakes
Segment tree: allocating only 2n instead of 4n nodes. For n that is not a power of 2, the tree can have gaps that require more than 2n nodes. Always allocate 4n to be safe. For competitive programming: use 4 * MAXN as the tree array size.
Segment tree: returning 0 for no-overlap in a minimum query. The identity for sum is 0; for minimum it is Integer.MAX_VALUE (or +∞). Returning 0 as the identity for minimum queries produces wrong results when 0 is in the array. Match the identity to the operation.
AVL: forgetting to update height after rotation. After performing a rotation, both the old root (now a child) and the new root must have their heights recalculated. Order matters: update the lower node first, then the higher node.
AVL: determining the rotation case using only balance factor at the violation node. The rotation case (LL, RR, LR, RL) depends on BOTH the violation node's balance factor AND its child's balance factor. BF(z)=+2 with BF(z.left)=+1 → LL; BF(z)=+2 with BF(z.left)=−1 → LR. Check both.
Red-Black: treating NULL pointers as missing instead of BLACK sentinel leaves. Rule 5 (equal black-height) counts NULL leaves as BLACK nodes. A leaf's two null children each contribute one black to the path length. Forgetting to count null children as black nodes leads to incorrect black-height calculations.
Interview Questions
Q: Why is a segment tree built in O(n) even though it has O(n) nodes each needing O(1) work?
Building a segment tree fills the tree bottom-up. Each internal node's value is computed from its two already-computed children in O(1). Since there are O(n) nodes total and each takes O(1) work, the total is O(n). This is the same argument as Floyd's heap-build algorithm — bottom-up processing avoids redundant work.
Q: What are the four AVL rotation cases and when is each triggered?
After an insertion creates a balance factor violation of ±2 at node z: LL (left-left) — z has BF=+2 and z.left has BF=+1 → single right rotation at z. RR (right-right) — z has BF=-2 and z.right has BF=-1 → single left rotation at z. LR (left-right) — z has BF=+2 and z.left has BF=-1 → left rotate at z.left, then right rotate at z. RL (right-left) — z has BF=-2 and z.right has BF=+1 → right rotate at z.right, then left rotate at z.
Q: Why do standard libraries (Java TreeMap, C++ std::map) use Red-Black trees instead of AVL trees?
Both guarantee O(log n) operations. The difference is in write performance. AVL trees may require O(log n) rotations after an insert or delete to restore strict balance (height difference ≤ 1 at every node). Red-Black trees require at most 2 rotations per insert and 3 per delete. For general-purpose ordered maps and sets where insertions and deletions are frequent, Red-Black's lower rotation overhead wins. AVL trees are preferred when the workload is read-heavy (many lookups, few modifications) because AVL's stricter balance gives a shorter tree height.
Summary
Segment Tree
Stores aggregates (sum, min, max) of array ranges in a complete binary tree. Each node covers a range; leaves are single elements. Query visits O(log n) nodes using three cases: no overlap (return identity), full overlap (return node value), partial overlap (recurse both children). Point update touches O(log n) ancestors. Build takes O(n) using bottom-up construction. Lazy propagation extends this to O(log n) range updates.
AVL Tree
A BST with the invariant that every node's balance factor (height(left) − height(right)) is within {−1, 0, +1}. Insertions and deletions restore the invariant using single or double rotations. Four cases: LL → right rotate; RR → left rotate; LR → left rotate child + right rotate violation; RL → right rotate child + left rotate violation. Guarantees height ≤ 1.44 log₂(n) → O(log n) search. O(log n) rotations per insert/delete.
Red-Black Tree
A BST with five colouring rules ensuring no path from root to null leaf is more than twice as long as the shortest path. Rules 4 (no consecutive reds) and 5 (equal black-height) together bound height at 2 log₂(n+1) = O(log n). Insert requires at most 2 rotations. Delete requires at most 3. Lower rotation overhead than AVL for write-heavy workloads — used in Java TreeMap, C++ std::map, Linux kernel scheduler.
Choose based on workload:
- ›Range queries on an array → Segment Tree
- ›Read-heavy ordered map → AVL Tree
- ›General-purpose ordered map/set → Red-Black Tree
A segment tree for an array of n elements has how many nodes?