Homework: Homework 6. Binary Search Trees

Assigned

• October 27, 2026

Due

• November 6, 2026 10:00pm

Collaboration

Make sure you review and understand the policies on the syllabus before you discuss your work on this assignment with anyone.

Submitting

You will submit your compiled pdf on Gradescope. Everything must be typed in \(\Latex\) If you are asked to design an algorithm, please provide: (a) the pseudocode or precise description in words of the algorithm, (b) an explanation of the intuition for the algorithm, (c) a proof of correctness, (d) the running time of your algorithm and (e) justification for your running time analysis.

1. 12.2-4 Suppose that the search for a key k in a BST ends at a leaf. Consider 3 sets: A the keys to the left of the path, B the keys on the path, and C the keys to the right of the path. Claim: for any $a\in A$, $b\in B$. $c\in C$ $a\leq b\leq c$. Give a smallest possible counterexample

2. 12.3-5 Is deletion commutative. I.e. does deleting x than y always give the same tree as deleting y then x?

3. 13.1-6 What is the largest number of internal nodes in a red-black tree with black-height k? The smallest number?

4. 13.1-8 Argue that in a red-black tree a red node cannot have exactly one non-nil child.

5. 13.4-1 Show that if node y in RB-delete is red then no black-heights change.

Bonus. 13.2-5 Right conversion using Right-Rotate