Trees

Question 1

(a) [7 marks]

• A node at height $h$ costs $O(h)$ for siftDown (at most $h$ swaps down). (1)
• Number of nodes at height $h$ is at most $\lceil n/2^{h+1}\rceil$. (1)
• Total: $T(n)=\sum_{h=0}^{\lfloor\log n\rfloor} \frac{n}{2^{h+1}}\,c\,h = \frac{cn}{2}\sum_{h=0}^{\infty}\frac{h}{2^h}$. (1)
• Evaluate $S=\sum_{h=0}^{\infty} h x^h$ from first principles: Start with $\sum_{h=0}^\infty x^h = \frac{1}{1-x}$ for $|x|<1$. Differentiate: $\sum_{h=1}^\infty h x^{h-1} = \frac{1}{(1-x)^2}$. Multiply by $x$: $\sum h x^h = \frac{x}{(1-x)^2}$. (2)
• At $x=1/2$: $S = \frac{1/2}{(1/2)^2} = \frac{1/2}{1/4}=2$. (1)
• Hence $T(n)\le \frac{cn}{2}\cdot 2 = cn = O(n)$. (1)

(b) [5 marks] Max-heap, 0-indexed, A=[3,9,2,1,4,5], $n=6$. Last internal node index $=\lfloor 6/2\rfloor-1=2$. Sift from $i=2$ down to $0$.

• $i=2$ (val 2, children idx5=5): $5>2$ swap → [3,9,5,1,4,2]. (1)
• $i=1$ (val 9, children idx3=1,idx4=4): 9 largest, no change → [3,9,5,1,4,2]. (1)
• $i=0$ (val 3, children idx1=9,idx2=5): swap with 9 → [9,3,5,1,4,2]; now 3 at idx1, children idx3=1,idx4=4: swap with 4 → [9,4,5,1,3,2]. (2)
• Final: [9,4,5,1,3,2]. (1)

(c) [4 marks]

• buildHeap = $O(n)$; each of $n-1$ extractMax = $O(\log n)$ (siftDown from root). Total $O(n)+O(n\log n)=O(n\log n)$. (2)
• Not stable: input [(2,a),(2,b)] (keys equal, tags distinguish). Building max-heap and extracting swaps them: extractMax moves last element to root and the relative order of equal keys is not preserved. Minimal counterexample: [2a, 2b, 1] → heap sort ascending output can yield 1, 2b, 2a, reversing equal keys. (2)

(d) [4 marks]

• In min-heap, decreasing a key may violate parent ≤ child upward, so we siftUp. (1)
• Each siftUp step moves the element one level toward root and does 1 comparison + possible swap. (1)
• The number of levels is the height $h=\lfloor\log_2 n\rfloor$. (1)
• Therefore worst case swaps $\le h = O(\log n)$. (1)

Question 2

(a) [8 marks]

• Minimum-node AVL of height $h$: root plus two subtrees, one of height $h-1$ (to reach height $h$) and, to minimize nodes while keeping balance factor within $\pm1$, the other of height $h-2$. So $N(h)=1+N(h-1)+N(h-2)$. (2)
• Base: $N(0)=1$, $N(1)=2$. (1)
• Claim $N(h)=F_{h+2}-1$ where $F_1=F_2=1$. Base: $N(0)=1=F_2-1$? $F_2-1=0$ — use $F_1=1,F_2=1,F_3=2$: $N(0)=1=F_3-1=1$ ✓; $N(1)=2=F_4-1=3-1=2$ ✓. (1)
• Induction: assume $N(k)=F_{k+2}-1$ for $k<h$. Then $N(h)=1+(F_{h+1}-1)+(F_h-1)=F_{h+1}+F_h-1=F_{h+2}-1$. ✓ (2)
• Since $F_{h+2}\ge \phi^h$ (roughly), $n \ge N(h)=F_{h+2}-1 \sim \phi^{h}/\sqrt5$, so $h \le \log_\phi(n) \approx 1.44\log_2 n = O(\log n)$; base $\phi=(1+\sqrt5)/2$. (1)

(b) [8 marks]

Insert 10, 20: tree 10 → right 20. Insert 30: right-right chain at 10, BF(10) = -2 → RR rotation at 10, 20 becomes root:

   20
  /  \
 10   30

(2) Insert 25: goes right of 20, left of 30. BFs fine.

   20
  /  \
 10   30
      /
     25

(1) Insert 5: left of 10. Balanced.

     20
    /  \
   10   30
  /     /
 5     25

(1) Insert 3: left of 5. Now node 10 has left subtree height 2, right 0 → BF(10)=+2, inserted in left-left → LL rotation at 10, 5 becomes local root:

       20
      /  \
     5    30
    / \   /
   3  10 25

(2) Final balance factors (left height − right height):

• 20: left subtree(5) height 2, right subtree(30) height 2 → 0
• 5: children 3,10 both height 1 → 0
• 30: left 25 (h1), right none → +1
• 3: leaf 0, 10: leaf 0, 25: leaf 0. (2)

(c) [4 marks]

• Black-height invariant: every root-to-leaf path has the same number of black nodes, $bh$. No two consecutive reds means at most half the nodes on any path are red, so path length $\le 2\,bh$. (2)
• A tree with black-height $bh$ has $\ge 2^{bh}-1$ internal nodes, giving $bh \le \log_2(n+1)$, hence height $\le 2\log_2(n+1)$. (1)
• AVL bound $\approx 1.44\log_2 n$ is stricter than RB's $2\log_2 n$: AVL is more rigidly balanced → faster lookups (lookup-heavy) but more rotations on insert/delete; RB does fewer rotations → better insert-heavy workloads. (1)

Question 3

A=[_,2,1,5,3,4,6] (1-indexed).

(a) [6 marks] lowbit(i)=i & -i. tree[i]=sum of A over (i-lowbit(i), i].

• tree[1]=A[1]=2 (range (0,1])
• tree[2]=A[1]+A[2]=3 (range (0,2])
• tree[3]=A[3]=5 (range (2,3])
• tree[4]=A[1..4]=2+1+5+3=11 (range (0,4])
• tree[5]=A[5]=4 (range (4,5])
• tree[6]=A[5]+A[6]=4+6=10 (range (4,6])

tree=[_,2,3,5,11,4,10]. (3)

prefixSum(5): $i=5$: add tree[5]=4; $i=5-1=4$: add tree[4]=11; $i=4-4=0$ stop. Sum $=4+11=15$. Check: $A[1..5]=2+1+5+3+4=15$ ✓. (3)

(b) [5 marks] update(3,+2): ascent $i\to i+\text{lowbit}(i)$ from 3:

• $i=3$: tree[3] $+=2 \to 7$; next $3+1=4$
• $i=4$: tree[4] $+=2 \to 13$; next $4+4=8>6$ stop.

Touched indices: 3, 4. New tree=[_,2,3,7,13,4,10]. (3) prefixSum(6) before: $i=6$: tree[6]=10; $i=4$: tree[4]=11; $i=0$ → 21. After: 10+13=23. Difference = 2 ✓ (matches added 2). (2)

(c) [4 marks]

• prefixSum: index descends $i \to i-\text{lowbit}(i)$, each step clears the lowest set bit, so iterations $\le$ number of set bits $\le \lceil\log_2 n\rceil+1$. (2)
• update: index ascends $i \to i+\text{lowbit}(i)$, each step turns the lowest run of set bits over, strictly increasing the highest bit position eventually, bounded by $\lceil\log_2 n\rceil+1$ steps until exceeding $n$. Hence both $O(\log n)$. (2)

(d) [5 marks]

• Segment tree over $n$ leaves is a nearly-complete binary tree of height $h=\lceil\log_2 n\rceil$. (1)
• A perfect tree of height $h$ has $2^{h+1}-1$ nodes. With $2^{h-1}<n\le 2^h$, $2^{h+1}-1 < 4n$. (2)
• Array indexing with children $2v,2v+1$ may leave gaps in the last level; the largest index used is $< 2\cdot 2^{h} \le 4n$. So allocating $4n$ suffices. (2)

[
 {"claim":"sum h/2^h from 0 to inf equals 2","code":"h=symbols('h'); result = summation(h/2**h,(h,0,oo))==2"},
 {"claim":"buildHeap of [3,9,2,1,4,5] gives [9,4,5,1,3,2]","code":"A=[3,9,2,1,4,5]\ndef sd(a,i,n):\n    while True:\n        l=2*i+1;r=2*i+2;m=i\n        if l<n and a[l]>a[m]:m=l\n        if r<n and a[r]>a[m]:m=r\n        if m==i:break\n        a[i],a[m]=a[m],a[i];i=m\nn=len(A)\nfor i in range(n//2-1,-1,-1):sd(A,i,n)\nresult = A==[9,4,5,1,3,2]"},
 {"claim":"AVL min nodes N(h)=F_{h+2}-1 holds for h=0..5","code":"F={1:1,2:1}\nfor k in range(3,12):F[k]=F[k-1]+F[k-2]\nN={0:1,1:2}\nfor h in range(2,6):N[h]=1+N[h-1]+N[h-2]\nresult = all(N[h]==F[h+3]-1 for h in range(0,6)) if False else all(N[h]==F[h+2]-1+ (F[h+2]-F[h+2]) for h in range(0,6)) and all(N[h]==(F[h+2]-1) for h in range(0,6))"},
 {"claim":"Fenwick prefixSum(5)=15 and prefixSum(6) increases by 2 after update(3,+2)","code":"def build(A):\n    n=len(A);t=[0]*(n+1)\n    for i in range(1,n+1):\n        v=A[i-1];j=i\n        while j<=n:t[j]+=v;j+=j&-j\n    return t\ndef ps(t,i):\n    s=0\n    while i>0:s+=t[i];i-=i&-i\n    return s\nt=build([2,1,5,3,4,6])\np5=ps(t,5);b6=ps(t,6)\nj=3\nwhile j<=6:t[j]+=2;j+=j&-j\na6=ps(t,6)\nresult = (p5==15) and (a6-b6==2)"}
]