(a) Before the rotation the keys in order are: T1 (they are left of x), then x, then T2, then y, then T3. T2 sits in the left subtree of y, so its keys are smaller than y, and in the right subtree of x, so they are larger than x: x < T2 < y. After the rotation y(x(T1, T2), T3) reads T1, x, T2, y, T3 from left to right: the same sequence. A binary tree is a search tree exactly when its in-order sequence is sorted, so a rotation can never break the search-tree property. ∎

(b) x now has the children T1 and T2: height(x′) = 1 + max(h1, h2), balance factor h2 − h1. y has the children x′ and T3: height(y′) = 1 + max(1 + max(h1, h2), h3), balance factor h3 − (1 + max(h1, h2)).

(c) Right rotation at x with left child y (the mirror image of (a)–(b)): the subtrees are T1 = y.left, T2 = y.right, T3 = x.right. Balance(x) = −2 means height(y) − h3 = 2, so 1 + max(h1, h2) = h3 + 2, i.e. max(h1, h2) = h3 + 1. Balance(y) ≤ 0 means h1 ≥ h2, so h1 = h3 + 1 and h2 ∈ {h3, h3 + 1}. After the rotation x′ = (T2, T3) has balance factor h3 − h2 ∈ {0, −1}, and y′ = (T1, x′) has balance factor (1 + max(h2, h3)) − h1 = (h2 + 1) − (h3 + 1) = h2 − h3 ∈ {0, 1}. Both are in {−1, 0, 1}. ∎ After an insertion the case is more specific. Before the insertion x was not too tall, and y had height h3 + 1; the insertion made T1 one level higher (it went into T1), so before it T1 had height h3, and y leaned left only now, so h2 = h3. Then x′ has height h3 + 1, y′ has height 1 + max(h3 + 1, h3 + 1) = h3 + 2, and before the insertion x had height 1 + max(h3 + 1, h3) = h3 + 2: the same. The ancestors of x see no change in height, so none of them is out of balance: one rebalancing step (a single or a double rotation) repairs the whole tree after an insertion, which is what the "Predict" of video 1 says (checked for all heights below 8 in test_ex6_claims.py).

(d) Insert 30, 10, 20: the keys form the zig-zag 30 → 10 → 20 and the root 30 leans left by 2, its left child 10 leans right. One right rotation at 30 gives 10(-,30(20,-)): the new root 10 has height(right) − height(left) = 2 − 0 = +2; the zig-zag just moved to the other side. In the left-right case balance(y) = +1: h2 = h1 + 1 and height(y) = h3 + 2, so h2 = h3 + 1, h1 = h3, and one right rotation gives y′ the balance factor (h3 + 2) − h3 = +2 as computed in (b). Double rotation: let z = y.right with subtrees of heights hl and hr; its height is h2 = h3 + 1, so max(hl, hr) = h3 and, as z is a valid AVL node, hl, hr ∈ {h3 − 1, h3}. Rotating y left puts z above y, rotating x right puts z above x: the result is z(y′, x′) with y′ = (T1, zl) and x′ = (zr, T3). Their heights are 1 + max(h3, hl) = h3 + 1 and 1 + max(hr, h3) = h3 + 1; their balance factors hl − h3 ∈ {−1, 0} and h3 − hr ∈ {0, 1}; and z has two subtrees of height h3 + 1, factor 0. All nodes are in {−1, 0, 1} and the subtree has height h3 + 2 again. ∎

(a) A tree of height h has a subtree of height exactly h − 1 (the higher one); by the AVL rule the other subtree has height h − 1 or h − 2. The number of nodes is 1 plus the sizes of the two subtrees, and a subtree of height g has at least N(g) nodes (N is increasing). So N(h) ≥ 1 + N(h − 1) + N(h − 2), and equality is reached by putting a thinnest tree of height h − 1 on one side and a thinnest tree of height h − 2 on the other (it is a valid AVL node: the heights differ by 1). ∎

(b) N(0) = 0, N(1) = 1, N(2) = 2, N(3) = 4, N(4) = 7, N(5) = 12, N(6) = 20, N(7) = 33, N(8) = 54, N(9) = 88, N(10) = 143: the counts of video 1 (each is one more than the two before it added together). Claim N(h) = F(h + 2) − 1: for h = 0 and 1, F(2) − 1 = 0 and F(3) − 1 = 1; if it holds for h − 1 and h − 2 then N(h) = (F(h + 1) − 1) + (F(h) − 1) + 1 = F(h + 2) − 1. ∎ (Checked up to h = 59, and that N(h) really is the minimum over all AVL shapes for h ≤ 7.)

(c) F(1) = 1 ≥ φ⁻¹ and F(2) = 1 ≥ φ⁰. If F(k) ≥ φ^(k−2) and F(k + 1) ≥ φ^(k−1), then F(k + 2) = F(k + 1) + F(k) ≥ φ^(k−1) + φ^(k−2) = φ^(k−2)(φ + 1) = φ^(k−2) · φ² = φ^k. ∎ Hence n ≥ N(h) = F(h + 2) − 1 ≥ φ^h − 1, so φ^h ≤ n + 1 and h ≤ log_φ(n + 1). Since log_φ x = log₂ x / log₂ φ and 1 / log₂ φ = 1 / 0.6942 = 1.4404…, an AVL tree is never more than about 44% taller than a perfect tree (video 1: "about 1.44 times log₂ n").

(d) N(28) = F(30) − 1 = 832,039 ≤ 1,000,000 < N(29) = F(31) − 1 = 1,346,268, so an AVL tree with a million keys has at most 28 levels. A perfect tree needs ⌈log₂(1,000,001)⌉ = 20. The bound of (c) gives log_φ(1,000,001) = 28.71, i.e. also 28 after rounding down: for this n it is exact. So even in the worst case an AVL tree is 40% taller than a perfect one (28 against 20), well below "twice as tall".

(a) Insertion. The key goes into a leaf, so no leaf moves. A node with four keys a < b < c < d splits into the nodes [a b] and [d] on the same level, and c goes into the parent, which gains a key and a child. If the parent now has four keys it splits in the same way, one level up. If the root splits, a new root is created above the two halves: every leaf gets one level deeper at the same moment. Deletion. The key is taken out of a leaf. An empty node is repaired by a transfer (a key moves from a sibling through the parent into the empty node; nodes stay on their levels) or a fuse (the empty node, a sibling and the parent's key between them become one node on the same level; the parent loses a key and a child). If the root loses its only key, the fused node is its only child and becomes the root: every leaf gets one level shallower. So all leaves are at the same depth always, and the depth changes only by a root split (+1) or by a root that disappears in a fuse (−1). ∎

(b) With d levels every level i has at least 2^(i−1) nodes (every internal node has at least 2 children) and each node has at least one key: n ≥ 1 + 2 + … + 2^(d−1) = 2^d − 1. Every level has at most 4^(i−1) nodes with at most 3 keys: n ≤ 3 · (4^d − 1)/3 = 4^d − 1. Hence 2^d ≤ n + 1 and 4^d ≥ n + 1: ⌈log₄(n + 1)⌉ ≤ d ≤ ⌊log₂(n + 1)⌋. n = 1,000: log₄(1,001) = 4.98 and log₂(1,001) = 9.97: between 5 and 9 levels. n = 1,000,000: 9.97 and 19.93: between 10 and 19 (video 2; measured: 6 levels for the keys 1 … 1,000 in order). ∎

(c) Encode a 2-node as a black node, a 3-node [k1 k2] as a black k2 with the red child k1 on its left (or black k1 with the red child k2 on its right), a 4-node [k1 k2 k3] as a black k2 with the red children k1 and k3; the subtrees below the (2,4) node hang under the right places. (i) The root of the binary tree is the top of the root node: black. (ii) A red node is a key that shares its parent's (2,4) node; its children are the tops of the (2,4) children, which are black: no red node has a red child. (iii) A path from the root to an empty child goes down one (2,4) level after another and meets exactly one black node, the top of the node, on each level; all leaves are at the same depth d, so every such path contains exactly d black nodes. These are the three rules of a red-black tree; the checks run on random (2,4) trees in test_ex6_claims.py. ∎ Both ways of writing a 3-node are valid and both occur (video 3: "on the left or on the right").

(d) A path has at most d black nodes and, as there are no two reds in a row, at most one red node in each (2,4) level: at most 2d nodes, so the height is ≤ 2d ≤ 2·⌊log₂(n + 1)⌋ ≤ 2 log₂(n + 1) (video 3: 31 levels for the keys 1 … 100,000 in order, limit 33). The AVL tree guarantees ≈ 1.44 log₂ n (Exercise 2), so it is the better balanced tree: lookups visit fewer nodes. The red-black tree is more relaxed and pays less to keep the invariant: an insertion needs at most 2 rotations and a deletion at most 3 (video 3), and most repairs are recolourings, whereas an AVL deletion may need a rotation on every level on the way up. That is why a library tree map (Java's TreeMap) is red-black.

(a) Keys: the start times. Values: the end times. book(s, e): floorEntry(s) (the booking that starts last at or before s) and ceilingEntry(s) (the first booking that starts at or after s); accept only if the floor ends at or before s and the ceiling starts at or after e (intervals are half-open, so touching is fine), then put(s, e). In the reference code: Ex6Designs.Calendar (a TreeMap) and the bisect version in ex6_designs.py.

(b) Suppose a booking B overlaps [s, e): B.start < e and B.end > s. Case B.start ≤ s. The floor F is the booking with the greatest start ≤ s, so F.start ≥ B.start. If F ≠ B, then B starts before F, and because bookings do not overlap B must end before F starts: B.end ≤ F.start ≤ s, which contradicts B.end > s. So B = F. Case B.start > s. The ceiling C has the smallest start ≥ s, so C.start ≤ B.start < e; if C ≠ B then C starts in [s, e), so C itself overlaps the new interval. Either way the floor or the ceiling overlaps. ∎ The assumption that the existing bookings do not overlap each other is used in the first case ("B ends before F starts"); with overlapping bookings a long early booking could hide behind a short one and we would have to look further.

(c) With a balanced tree: two searches and one insertion, O(log n) per request. With a sorted array: the two searches are binary searches, O(log n), but inserting shifts on average half of the entries: O(n). Video 4: for 9,999 distinct random keys the sorted lists moved 24,909,043 entries and the AVL tree needed 121,667 comparisons in total (both languages). Trace: (15, 25): the floor (10, 20) ends at 20 > 15 → refused. (25, 35): the ceiling (30, 40) starts at 30 < 35 → refused. (20, 30): the floor (10, 20) ends at 20 ≤ 20 and the ceiling (30, 40) starts at 30 ≥ 30 → accepted. (0, 100): there is no floor, the ceiling (10, 20) starts at 10 < 100 → refused.

(d) Start with the candidate time t. If the floor booking is still running at t, move the candidate to its end. Then look at the next bookings in order (ceilingEntry, then higherEntry): while the next booking starts before candidate + L, move the candidate to the end of that booking and take the next one. Cost: O(log n + k) where k is the number of bookings that were skipped; the next-booking steps are O(log n) each in the worst case but O(1) amortised in an iterator. With each tree node also storing the largest gap in its subtree it becomes O(log n); that is an augmented tree (reference code: next_free / nextFree, checked against a brute-force search).

(a) The in-order successor of an inner key k at position i is the smallest key of the subtree behind child i + 1: go to that child and keep taking the first child down to a leaf; because all leaves are at the same depth, this walk ends in a leaf, whose first key is the successor. It is larger than every key in the left subtrees (it is in the right subtree of k) and smaller than the other keys of the right subtree, so putting it in k's place keeps the order. Deleting it from the leaf is then the leaf case.

(b) Let n be the empty node and p its parent.

(c) A transfer changes the contents of three nodes on two levels but not their levels. A fuse merges two nodes of the same level into one; the other leaves are untouched. Only when the root loses its last key does the tree get shorter, and then every leaf gets one level shallower (Exercise 3(a)). ∎

(d) Insert 4, 6, 12, 15, 3, 5, 10, 8, 11, 13, 18: [5 10 12] / [3 4] [6 8] [11] [13 15 18] after three splits. Remove 3: the leaf [3 4] still has a key: [5 10 12] / [4] [6 8] [11] [13 15 18]. Remove 12 (an inner key): replace it by its successor 13, the first key of the leaf [13 15 18], which keeps 15 and 18: [5 10 13] / [4] [6 8] [11] [15 18]. Remove 15: [5 10 13] / [4] [6 8] [11] [18]. Remove 4: the leaf [4] is empty; it has no left sibling and the right sibling [6 8] has two keys: transfer: 5 comes down, 6 goes up: [6 10 13] / [5] [8] [11] [18]. Remove 8: [8] is empty and its neighbours [5] and [11] have one key each: fuse with the left sibling: [5] + 6 + nothing = [5 6]; the parent loses the key 6 but keeps two: [10 13] / [5 6] [11] [18]. Final: 6 keys, 2 levels, 1 transfer and 1 fuse (video 2; test_exercise_5_the_example_of_video_2).

(e) Going down to the leaf touches at most d nodes (d levels). At every level on the way back up at most one repair is needed, and a repair looks at the node, one or two siblings and the parent: a constant number of nodes of at most 4 keys. The repairs move up only while the parent underflows (fuse). Total: O(d) = O(log n) nodes, d ≤ log₂(n + 1).

Reference: solutions/py/ex6_rotate.py, solutions/java/Ex6Rotate.java. Name the pieces before you touch a link: y = x.left, p = x.parent, the middle subtree y.right. Then change, in this order, x.left (to the middle subtree) and the parent link of the middle subtree (if it exists), y.right = x and x.parent = y, y.parent = p, and finally the link in p (p.left or p.right, whichever was x). The usual mistakes: forgetting middle.parent = x (the tests walk the tree and compare every parent link), forgetting that the middle subtree may be empty, forgetting the root case (p is None), and updating p.left when x was p.right. rotate_left is the mirror image.

Reference: solutions/py/ex6_avl.py, solutions/java/Ex6Avl.java. update(n) must be called on the node that moved down (x) before the node that moved up (y): y's height uses x's (see Exercise 10). rebalance first calls update(n), then looks at balance(n) and at the balance of the heavy child: if the child leans the other way, rotate the child first. The insert returns the new root of the subtree and calls rebalance on the way back up on every node of the path (about log n nodes), so an insertion costs O(log n). Numbers the tests check: the four cases need 1, 1, 2, 2 rotations; inserting 1 … 7 gives the counts 0, 0, 1, 1, 2, 3, 4 and the tree 4(2(1,3),6(5,7)); the keys 1 … 1,000 give height 10 and 1 … 2,000 give height 11; the keys 1 … 1,023 cost 1,013 rotations (observation, checked for all 2^k − 1 keys with k ≤ 11: 2^k − 1 − k rotations).

Reference: solutions/py/ex6_sortedmap.py, solutions/java/Ex6SortedMap.java. first and last walk down the left or the right edge. floor(key): start at the root; if the current key equals key return it; if it is smaller it is a candidate — remember it and go right to look for a closer one; if it is larger go left. The answer is the last candidate remembered (or none). ceiling is the mirror image. One path from the root: O(height). sub_map(lo, hi): visit n; go left only if lo < n.key (otherwise every key on the left is < lo); add n if lo <= n.key < hi; go right only if n.key < hi. The cost is at most 2·h + k nodes for k results: a visited node outside the range lies on the search path of lo (its key is below lo: we only walked right) or of hi (its key is at least hi: we only walked left), two paths of at most h nodes, and every other visited node is one of the k results (checked in the tests: 300 random ranges on a balanced tree of height 10). A plain traversal of the whole tree would cost n.

The bug. rebalance repairs a left-heavy node with a right rotation and a right-heavy node with a left rotation, whatever the child looks like. For the zig-zag cases (left-right and right-left) the first rotation of the child is missing. Insert 30, 10, 20: the root 30 leans left, its left child 10 leans right; one right rotation at 30 gives 10(-,30(20,-)), whose root has balance +2 (Exercise 1(d)). The keys are still in order, and — look at this — all stored heights are correct, so a check that reads node.height never notices. Why small examples hide it. Straight-line cases (left-left, right-right) are handled correctly, and sorted insertion produces only those: the usual test "insert 1 … 1,000 and the height is 10" passes (the stored and the real height are 10). The tree is wrong only when a zig-zag occurs, and even then not for every input: of all insertion orders of 1 key, 2 keys, 3, 4, 5, 6, 7 keys the numbers of orders that end with a node of balance ±2 are 0, 0, 2, 0, 8, 272, 1,184 (out of 1, 2, 6, 24, 120, 720, 5,040): the two bad orders for three keys are 1, 3, 2 and 3, 1, 2, and all 24 orders of four keys happen to be fine. A test that tries every order of four keys would have said "correct". The test_ex6_read.pyEx6ReadTest.java tests count them. The fix. In the left-heavy case: if balance(n.left) > 0: n.left = rotate_left(n.left) before rotate_right(n), and the mirror image on the right (the code of Exercise 7). With it all orders of up to 7 keys, and the keys 1 … 1,000, give valid trees. Habits: recompute the balance factors from the real tree (do not trust the stored heights), and test the four cases separately.

The bug. In rotate_right / rotate_left the two update calls are in the wrong order: update(y) (the node that moves up) is called before update(x) (the node that moves down and is now y's child). y's new height is then computed from x's old height, which is too large. Insert 10, 20, 30: after the left rotation the root 20 has the children 10 and 30, real height 2, but it stores 1 + max(1, 3) = 4 (x = 10 still carried the height 3 of the old top). The claim "the rotations keep the stored heights up to date" is false. Why small examples hide it. A wrong height does no harm until an ancestor reads it to compute its balance factor; with few keys there is no such ancestor, or the error does not tip a decision. The real shape is a valid AVL tree for all insertion orders of up to 5 keys (0 bad orders among the 1, 2, 6, 24 and 120 orders); the first failures are at 6 keys (192 of 720 orders, for instance 1, 3, 4, 2, 5, 6) and at 7 keys 1,056 of 5,040, including the simplest test of all, the keys 1, 2, …, 7 in order. The stored heights, by contrast, are wrong already at 3 keys (4 of the 6 orders: the four that need a rotation). With 1 … 1,000 in order the tree has real height 14 (a correct AVL tree: 10) and the root stores 16. Insertion still runs in O(log n) per step but the height guarantee is lost: the invariant "balance factors in −1, 0, 1" is broken and the stored heights are not the real ones. The fix. Update the node that went down first: update(x) then update(y) (the order of Exercise 7's rotations). With it every order of up to 7 keys gives a valid AVL tree with correct stored heights, and the keys 1 … 1,000 give height 10. Habits: assert, after every insertion, that every stored height equals the height recomputed from the children, and test with sorted input and random input with more keys than your shape tests have.