## 3 Algorithm Extended-Lazy
### Executions of Extended-Lazy for deletions
(See Figure 8.) In this case, the cost of Repair is 1. If \(\ell\) is locally rich, the number of locally rich levels decreases by one and at most one critical-level may appear, which means that we may need to apply Repair once more. Otherwise, the number of locally rich levels increases by one and a critical-level does not appear. If \(\ell\) is a hole-level and \(\ell\) is a bottom of a tank \(v\)(=tank[\(\ell\), \(t\)]), then there is a vertex \(u\) that is the leftmost level-\(\ell\) descendant of \(v\). Recall that the code virtually assigned to \(v\) is actually a code for level \(\ell\) and is assigned to \(u\). We release this code \(c\) using FreeTail(\(t\)) and perform AppendLeft(\(\ell,c\)). (See Figure 9.) In this case, the cost of Repair is 1. If \(t\) is locally rich, the number of locally rich levels decreases by one and at most one critical-level may appear, which means that we may need to apply Repair once more. Otherwise, the number of locally rich levels increases by one and a critical-level does not appear. Finally, if \(\ell\) is a rich-bottom-level, then we will do the same operation, namely, release the code \(c\) from the tank, and execute AppendLeft(\(\ell,c\)). (See Figure 10.) In this case, the cost of Repair is 1. If \(t\) is locally rich, the number of locally rich levels decreases by one and at most one critical-level may appear, which means that we may need to apply Repair once more. Otherwise, the number of locally rich levels increases by one and a critical-level does not appear. **Lemma 3**. : Extended-Lazy _preserves the semi-compactness on deletions._  
Proof. : Similarly as Lemma 2, we will check that the five conditions (i) through (v) of semi-compactness are preserved for each application of Cases (II), (IV), (VI), and (VIII). For Cases (I), (III), (V), and (VII),  
Figure 8: Repair for a hole-level \(\ell\) which is not a bottom of a tank. Figure 10: Repair for a rich-bottom-level \(\ell\). Figure 9: Repair for a hole-level \(\ell\) which is a bottom of a tank \(v\). at most one critical-level may appear but the five conditions (i) through (v) must be preserved at all other levels. We also need to verify these facts for Repair, but this can be done similarly, and we will omit it here. It is relatively easy to show that condition (i) is preserved because removing codes, and applying AppendRich, AppendPoor, FreeTail, and AppendLeft preserve the orthogonality. So, in the following, we will check conditions (ii) through (v). Similarly as Cases (1) and (3) in the proof of Lemma 2, we check conditions for each group of levels. **Case (I):**:  
* Nothing changes. Thus, all the conditions remain satisfied. * Only the rightmost assigned vertex turns unassigned by removing \(c\), and applying FreeTail(\(\ell(c)\)) and AppendLeft(\(\ell(c),c^{\prime}\)). Therefore, condition (ii) remains satisfied. Since \(\ell(c)\) does not belong to any tank, conditions (iii), (iv), and (v) also remain satisfied. * Conditions (iii) and (iv) remain satisfied because no tank is removed or created. In the following, we show that there is at most one level that breaks the conditions (ii) or (v). Since the rightmost dead vertex \(v\) at level \(\ell(c)\) turns non-dead and \(v\) is the left child of its parent \(v^{\prime}\), \(v^{\prime}\) turns from dead to non-dead. Also, if \(v^{\prime}\) was the rightmost dead vertex at level \(\ell(c)+1\) and is the left child of its parent \(v^{\prime\prime}\), \(v^{\prime\prime}\) turns from dead to non-dead. Otherwise, \(v^{\prime\prime}\) remains dead. In this way, we can apply the same argument to the upper levels. Then there is a level \(\ell^{*}\) such that one vertex turns from dead to non-dead at each level from \(\ell(c)\) to \(\ell^{*}\), and nothing changes at levels \(\ell^{*}+1\) or higher. Clearly, levels \(\ell^{*}+1\) or higher do not break the conditions.