## 3 Algorithm Extended-Lazy
### Executions of Extended-Lazy for deletions
The incurred cost is 1 or 0, and the number of locally rich levels decreases by one without considering the effect of Repair. **Case (VI):** The case that \(\ell(c)\) belongs to tank[\(b,t\)], \(\ell(c)=b\), and \(t\) is not locally rich. Extended-Lazy behaves in exactly the same way as Case (V). In this case, we do not need Repair for the same reason as Case (II). The cost is 1 or 0, and the number of locally rich levels increases by one. **Case (VII):** The case that \(\ell(c)\) belongs to tank[\(b,t\)], \(b<\ell(c)<t\), and \(t\) is locally rich. First, remove \(c\). Next, execute FreeTail(\(t\)) and receive the code \(c^{\prime}\) of level \(b\) from tank[\(b,t\)]. If \(c\) was assigned to the rightmost assigned vertex at \(\ell(c)\), do nothing. Otherwise, using FreeTail(\(\ell(c)\)), receive a code \(c^{\prime\prime}\) of level \(\ell(c)\), and using AppendLeft(\(\ell(c),c^{\prime\prime}\)), assign \(c^{\prime\prime}\) to the vertex to which \(c\) was assigned. We then find a level to which we assign the request \(c^{\prime}\) in the same way as Case (III). Starting from level \(\ell(c)\), we see if the level contains at least one code, until we reach level \(b+1\). Let \(\ell\) be the first such level. Then execute AppendRich(\(\ell,c^{\prime}\)), which creates tank[\(b,\ell\)]. If there is no such level \(\ell\) between \(\ell(c)\) and \(b+1\), execute AppendRich(\(b,c^{\prime}\)). In this case, we may need Repair. Without considering the effect of Repair, it costs either 1 or 2. If it costs 1, the number of locally rich levels is unchanged or decreases by one, and if it costs 2, the number of locally rich levels decreases by one. **Case (VIII):** The case that \(\ell(c)\) belongs to tank[\(b,t\)], \(b<\ell(c)<t\), and \(t\) is not locally rich. Extended-Lazy behaves in exactly the same way as Case (VII). In this case, we do not need Repair for the same reason as Case (IV). The cost is 1 or 2. The number of locally rich levels increases by one or two when the cost is 1, and by one when the cost is 2. Recall that after executing Cases (I), (III), (V), or (VII), the OVSF code tree may not satisfy semi-compactness. In such a case, however, there is only one level that breaks the conditions of semi-compactness, and furthermore, there is only one broken condition, namely, either (ii) or (v). If (ii) is broken at level \(\ell\), level \(\ell\) consists of, from left to right, a sequence of unassigned dead vertices up to some point, one non-dead vertex \(v\), a sequence of (at least one) assigned dead vertices, and a sequence of non-dead vertices. Note that, if \(\ell\) is a bottom of a tank tank[\(\ell\), \(t\)], the last non-dead vertices include a leftmost level-\(\ell\) descendant of tank[\(\ell\), \(t\)] (which is non-dead by definition). This non-dead vertex \(v\) was called a \"hole\" in [6]. We also use the same terminology here, and call level \(\ell\) a _hole-level_. If (v) is broken at level \(\ell\), \(\ell\) is a bottom of tank[\(\ell\), \(t\)] and is rich. Furthermore, level \(\ell\) consists of, from the leftmost vertex, a sequence of one or more unassigned dead vertices, a sequence of one or more non-dead vertices, and then the leftmost level-\(\ell\) descendant of tank[\(\ell\), \(t\)]. We call level \(\ell\) a _rich-bottom-level_. A level is called a _critical-level_ if it is a hole-level or a rich-bottom-level. The idea of Repair is to resolve a critical-level one by one. When we remove a critical-level \(\ell\) by Repair, it may create another critical-level. However, we can prove that there arises at most one new critical level, and its level is higher than \(\ell\). Hence we can obtain a semi-compact assignment by applying Repair at most \(h\) times. We explain the operation Repair. If \(\ell\) is a hole-level and \(\ell\) is not a bottom of a tank, then we execute FreeTail(\(\ell\)) so that we receive a code \(c\) and execute AppendLeft(\(\ell,c\)), i.e., we release the code \(c\) assignedto the rightmost assigned vertex at level \(\ell\), and reassign \(c\) to the hole to fill it.