TAOCP 5.2.3 Exercise 35

Section 5.2.3: Sorting by Selection

Exercise 35. [26] If UP links are added to a leftist tree (see the discussion of triply linked trees in Section 6.2.3), it is possible to delete an arbitrary node P from within the priority queue as follows: Replace P by the merger of LEFT(P) and RIGHT(P); then adjust the DIST fields of P's ancestors, possibly swapping left and right subtrees, until either reaching the root or reaching a node whose DIST is unchanged.

Prove that this process never requires changing more than $O(\log N)$ of the DIST fields, if there are $N$ nodes in the tree, even though the tree may contain very long upward paths.

Verified: no
Solve time: 13m47s

Setup

A leftist tree is a binary tree where each node (x) has a field (\operatorname{DIST}(x)) defined as [ \operatorname{DIST}(x) = \begin{cases} 0 & \text{if } x \text{ is external (null)}, \ 1 + \min\bigl(\operatorname{DIST}(\text{LEFT}(x)), \operatorname{DIST}(\text{RIGHT}(x))\bigr) & \text{otherwise}, \end{cases} ] and the leftist property (\operatorname{DIST}(\text{LEFT}(x)) \ge \operatorname{DIST}(\text{RIGHT}(x))) holds for every internal node.

Deleting a node (P) from such a tree (with UP links) is done by

1. replacing (P) with the merge (M = \text{merge}(\text{LEFT}(P), \text{RIGHT}(P))),
2. walking up the ancestors via UP links, recomputing (\operatorname{DIST}) at each step and swapping children if necessary to restore the leftist property,
3. stopping when the root is reached or when an ancestor’s (\operatorname{DIST}) remains unchanged.

We must prove that the number of (\operatorname{DIST}) fields altered in step 2 is (O(\log N)), where (N) is the total number of nodes.

Solution

Let the ancestors of (P) be (A_1, A_2, \dots, A_m) with (A_1) the parent of (P), (A_{i+1}) the parent of (A_i), and (A_m) the root. For (i = 1,\dots,m) let (S_i) be the sibling of (A_i) (the other child of (A_{i+1}); for (i=m) we may regard (S_m) as an external node with (\operatorname{DIST}=0)). Denote (s_i = \operatorname{DIST}(S_i)). Let (d_i) be the old (\operatorname{DIST}(A_i)) and (y_i) the new value after the update. Set (y_0 = \operatorname{DIST}(M)), the (\operatorname{DIST}) of the merged tree that replaces (P).

When updating (A_i) its two children are the already updated child (which is (A_{i-1}) with new (\operatorname{DIST}) (y_{i-1}) for (i>1), or (M) with (\operatorname{DIST}) (y_0) for (i=1)) and the unchanged sibling (S_i) with (\operatorname{DIST}) (s_i). The new (\operatorname{DIST}) is therefore [ y_i = 1 + \min(y_{i-1}, s_i) \qquad (i = 1,\dots,m). ] The old values satisfied the same recurrence with initial value (d_0 = \operatorname{DIST}(P)): [ d_i = 1 + \min(d_{i-1}, s_i) \qquad (i = 1,\dots,m). ]

The process stops at the first (i) (or at the root) where (y_i = d_i). Unrolling the recurrences gives [ y_i = \min\bigl( y_0 + i,; 1+s_{i-1},; 2+s_{i-2},; \dots,; i+s_0 \bigr), ] [ d_i = \min\bigl( d_0 + i,; 1+s_{i-1},; 2+s_{i-2},; \dots,; i+s_0 \bigr). ] Let (M_i = \min_{1\le k\le i}(k + s_{i-k})). Then (y_i = \min(y_0+i, M_i)) and (d_i = \min(d_0+i, M_i)). Without loss of generality assume (y_0 \le d_0) (the other case is symmetric). Then (y_i \ne d_i) iff (M_i > y_0 + i). Since (M_i = i + \min_{0\le j\le i-1}(s_j - j)), this condition is equivalent to [ \min_{0\le j\le i-1}(s_j - j) > y_0. ] Thus (y_i \ne d_i) holds precisely for (i = 1,2,\dots, L) where (L) is the largest integer such that (s_j - j > y_0) for all (j < L). (If the condition fails for (j=0) then (L=0) and no ancestor changes.)

We now bound (L). For any (j) with (s_j - j > y_0) we have (s_j \ge j+1) (because (y_0 \ge 0)). The subtree (S_j) is a leftist tree with (\operatorname{DIST} = s_j). A standard property of leftist trees (easily proved by induction using the leftist property) is that a tree with (\operatorname{DIST} = d) contains at least (2^d - 1) nodes. Hence [ \operatorname{size}(S_j) \ge 2^{s_j} - 1 \ge 2^{j+1} - 1. ]

The sibling subtrees (S_0, S_1, \dots, S_{L-1}) are disjoint (they are attached to distinct ancestors along the path from (P) to the root) and their total size is at most (N). Therefore [ N \ge \sum_{j=0}^{L-1} \operatorname{size}(S_j) \ge \sum_{j=0}^{L-1} (2^{j+1} - 1) = 2^{L+1} - 2 - L. ] This inequality implies (2^{L+1} \le N + L + 2), so (L = O(\log N)). Consequently the number of (\operatorname{DIST}) fields that change is at most (L = O(\log N)).

This completes the proof. ∎

Verification

The key inequality (\operatorname{size}(S_j) \ge 2^{s_j} - 1) is verified independently by induction on (d = \operatorname{DIST}). For (d=0) the tree is external (size 0) and (2^0-1=0). For (d>0), let the root have children (L) and (R). By definition (d = 1 + \min(\operatorname{DIST}(L), \operatorname{DIST}(R))) and the leftist property gives (\operatorname{DIST}(L) \ge \operatorname{DIST}(R)). Hence (\operatorname{DIST}(R) = d-1) and (\operatorname{DIST}(L) \ge d-1). By induction (\operatorname{size}(R) \ge 2^{d-1}-1) and (\operatorname{size}(L) \ge 2^{d-1}-1). Therefore [ \operatorname{size}(T) = 1 + \operatorname{size}(L) + \operatorname{size}(R) \ge 1 + 2(2^{d-1}-1) = 2^d - 1. ]

The recurrence for (y_i) and the stopping condition are tested on a small example: let (P) be a leaf ((y_0=0)), its parent (A_1) have sibling (S_0) a leaf ((s_0=1)), and (A_1)’s sibling (S_1) have (s_1=2). Then (s_0-0=1>0) so (y_1\ne d_1); (s_1-1=1>0) so (y_2\ne d_2); the exponential size bound limits the number of such siblings to (O(\log N)). This matches the derived bound.