## 3 Algorithm Extended-Lazy
### Executions of Extended-Lazy for insertions
Then, execute AppendPoor(\(\ell(c),c\)) and receive a code \(c^{\prime\prime}\) of level \(s\). By a similar observation as Case (3), we can see that \(\ell(c)<s\leq t\). Then, assign \(c^{\prime\prime}\) to the vertex which was tank[\(b,t\)] using AppendRich(\(t,c^{\prime\prime}\)). (Note that tank[\(s,t\)] is created if \(s\
eq t\).) Since \(\ell(c)\) was poor, \(c\) was assigned to a left child. Hence \(\ell(c)\) is currently locally rich. Execute AppendRich(\(\ell(c),c^{\prime}\)), which creates tank[\(b\), \(\ell(c)\)] if \(\ell(c)\
eq b\). The execution of this case costs 3, and the number of locally rich levels does not change. Here we give one remark. Suppose that \(\ell(c)\) does not belong to a tank and is poor. Then, we look at higher levels to see which of Cases (2) and (3) is executed. But, it may happen that we encounter neither a rich level nor a bottom of a tank, namely there is no tank in upper levels and all the upper levels are poor. We define this case as Case (7). However, we can prove the following lemma. Figure 5: An execution of Case (3). **Lemma 1**. : _If the semi-compactness is preserved and Case (7) occurs, then there is no configuration that assigns all the current codes._  
Proof. : We define the _bandwidth of a code_\(c\) as \(2^{\ell(c)}\) and the _bandwidth of the OVSF code tree_ of hight \(h\) as \(2^{h}\). Suppose that the semi-compactness is preserved and Case (7) occurs when an insertion \(i_{c}\) arrives. We show that \(2^{\ell(c)}\), the bandwidth required by this request, exceeds the bandwidth of the tree not used by the currently assigned codes. First, we transform the semi-compact assignment to a compact assignment. We remove tanks from the semi-compact assignment. Consider tank[\(b,t\)]. Release the code \(\bar{c}\) of level \(b\) from tank[\(b,t\)] temporarily. Then, assign \(\bar{c}\) to the vertex \(v\) immediately right of the rightmost dead vertex at \(b\). Because of conditions (ii) and (v) of semi-compactness, \(b\) is poor and the path from \(v\) to the root includes exactly one assigned vertex \(v^{\prime}\) at some level \(\ell\)\((\ell\leq t)\). Release code \(\bar{c}^{\prime}\) assigned to \(v^{\prime}\) and assign \(\bar{c}^{\prime}\) to the vertex \(v^{\prime\prime}\) immediately right of the rightmost dead vertex at \(\ell\). By repeating the above operations, a code \(\bar{c}^{\prime\prime}\) assigned to a vertex at level \(t\) is released. (\(\bar{c}^{\prime\prime}\) exists because of condition (iv) of semi-compactness.) We assign \(\bar{c}^{\prime\prime}\) to the vertex which was tank[\(b,t\)]. We show that conditions of semi-compactness remain satisfied after the above operation. Conditions (iii), (iv), and (v) remain satisfied for the levels which did not belong to tank[\(b,t\)] because no code was released from nor assigned to these levels. Also, conditions (iii), (iv), and (v) remain satisfied for levels which belonged to tank[\(b,t\)] because these conditions state on levels that belong to tanks but these levels do not belong to a tank any more since tank[\(b,t\)] was removed. (This argument is used several times in the later proofs.) Condition (i) remains satisfied because once two codes overlap, the one, say \(c\), at the higher level is moved immediately. Suppose that \(c\) is moved from \(v_{1}\) to \(v_{2}\) in this step. Then, \(v_{1}\) becomes unassigned but is still dead because one of its descendants is assigned. Also, \(v_{2}\) was the leftmost non-dead vertex at level \(\ell(c)\). Hence, Condition (ii) remains satisfied. If we do the above operation for each tank independently, the initial semi-compact assignment is transformed to a semi-compact assignment with no tanks. By definition, a semi-compact assignment with no tanks is a compact assignment. For example, the semi-compact assignment in Figure 3 is transformed to the compact assignment in Figure 6.  
Figure 6: Transformation from a semi-compact assignment to a compact assignment.