## 3 Algorithm Extended-Lazy
### Executions of Extended-Lazy for insertions
Since the levels \(\ell(c)\) and higher remain poor, there is no vertex of level \(\ell(c)\) which \(c\) can be assigned to and the bandwidth which is not used at the levels \(\ell(c)\) and higher is 0. Then, we calculate the bandwidth which is not used at the levels lower than \(\ell(c)\). We call the vertex \(v\) a _free-root_ if \(v\) and its all the children are assignable, and its parent is not assignable. Let \(T\) denote the set of free-roots. The non-used bandwidth is the total bandwidth of the vertices of \(T\). Each free-root should be the right child of its parent. For, if a free-root is the left child of its parent \(p\), the right child of \(p\) is also assignable because of the compactness. Therefore, \(p\) is assignable, which contradicts the definition of free-root. Suppose that there are more than one free-roots \(f\) and \(f^{\prime}\) at the same level \(\ell\), and suppose that \(f^{\prime}\) lies to the right of \(f\). As discussed above, both \(f\) and \(f^{\prime}\) are the right children of their parents. Since both \(f\) and \(f^{\prime}\) are assignable (and non-dead), all vertices between them are non-dead because of the compactness. In particular, the vertex \(f^{\prime\prime}\) immediately left of \(f^{\prime}\) is non-dead. Since \(f^{\prime}\) is assignable and \(f^{\prime\prime}\) is non-dead, the parent \(p^{\prime}\) of \(f^{\prime}\) and \(f^{\prime\prime}\) has no assigned descendants. Moreover, since \(f^{\prime}\) is assignable, \(p^{\prime}\) has no assigned ancestors. Then \(p^{\prime}\) is assignable, which again contradicts the definition. Hence, in a compact assignment, there is at most one free-root at each level. The total bandwidth is then at most \(2^{0}+2^{1}+\cdots+2^{\ell(c)-1}\), which is smaller than \(2^{\ell(c)}\). As we have mentioned previously, we excluded inputs in which the total bandwidth of all codes which should be assigned exceeds the capacity. Hence, Case (7) does not occur if the semi-compactness is preserved. (Actually, we do not have to exclude this case because our algorithm preserves the semi-compactness and detects this situation, and in such a case, our algorithm can simply reject the insertion.) The following lemma proves the correctness of Extended-Lazy on insertions. **Lemma 2**. : Extended-Lazy _preserves the semi-compactness on insertions._  
Proof. : In order to prove this lemma, we have to show that the five conditions (i) through (v) of semi-compactness are preserved after an insertion is served. It is relatively easy to show that (i) is preserved because Extended-Lazy uses only AppendRich, AppendPoor, and FreeTail, each of which preserves the orthogonality even by a single application. So, we show that conditions (ii) through (v) are satisfied after the execution of each of Cases (1) through (6), provided that (i) through (v) are satisfied before the execution. **Case (1):** It is not hard to see that conditions (iii) through (v) remain satisfied because no tank is created or removed. We check that condition (ii) is satisfied for each group of levels \([0,\ell(c))\), \(\ell(c)\), and \((\ell(c),h]\). \([0,\ell(c))\): Condition (ii) remains satisfied because nothing changes. \(\ell(c)\): Since we only append \(c\) to the leftmost non-dead vertex at \(\ell(c)\), condition (ii) remains satisfied. \((\ell(c),h]\): Let \(v\) be the vertex to which the code \(c\) is assigned. Note that by AppendRich(\(\ell(c),c\)), some of ancestors of \(v\) may turn from non-dead to dead. Suppose that vertex \(v_{s}\) of level \(s\) (\(s>\ell(c)\)) turned from non-dead to dead. Then, by the above observation, \(v_{s}\) is an ancestor of \(v\). Next, let \(v^{\prime}\) be the vertex which is immediately left of \(v\). Then, since \(v^{\prime}\) was dead, \(v_{s}\) is not an ancestor of \(v^{\prime}\). As a result, the ancestor of \(v^{\prime}\) at level \(s\) is the vertex, say \(v^{\prime}_{s}\), immediately left of \(v_{s}\), which implies that \(v^{\prime}_{s}\) was dead. Thus, condition (ii) remains satisfied at any level.