## 3 Algorithm Extended-Lazy
### Executions of Extended-Lazy for deletions  
Next, we describe executions of Extended-Lazy for deletions. Similarly as Sec. 3.1., for a deletion \(d_{c}\), there are eight cases depending on the status of level \(\ell(c)\) as summarized in Figure 7, each of whichwill be explained in the following. **Case (I):** The case that \(\ell(c)\) does not belong to a tank and is locally rich. Remove \(c\). If \(c\) is the rightmost dead vertex at \(\ell(c)\), do nothing. Otherwise, use FreeTail(\(\ell(c)\)) and receive a code \(c^{\prime}\) of level \(\ell(c)\). Then, using AppendLeft(\(\ell(c),c^{\prime}\)), assign \(c^{\prime}\) to the vertex to which \(c\) was assigned. Note that the vertex \(v\) which was the rightmost dead vertex of level \(\ell(c)\) becomes non-dead after the above operations, which may turn some dead vertices in the path from \(v\) to the root non-dead. As a result, an assignment may become non-semi-compact. If the semi-compactness is broken, we use the operation Repair, which will be explained later, to retrieve the semi-compactness. The cost of this case is either 1 or 0, and the number of locally rich levels decreases by one without considering the effect of Repair. (We later estimate these quantities considering the effect of Repair.) **Case (II):** The case that \(\ell(c)\) does not belong to a tank and is not locally rich. Extended-Lazy behaves in exactly the same way as Case (I). Note that vertex \(v\) which was the rightmost dead vertex at level \(\ell(c)\) becomes non-dead after the above operations, but \(v\) is a right child because \(\ell(c)\) was not locally rich. Since the semi-compactness was satisfied before the execution, the vertex immediately left of \(v\) was (and is) dead, which implies that the parent and hence all ancestors of \(v\) are still dead. Thus, we do not need Repair in this case. It costs either 1 or 0, and the number of locally rich levels increases by one or remains unchanged because \(\ell(c)\) may become locally rich. **Case (III):** The case that \(\ell(c)\) belongs to tank[\(b,t\)], \(\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 vertex immediately left of tank[\(b,t\)] at \(t\), do nothing. Otherwise, using FreeTail(\(t\)), receive a code \(c^{\prime\prime}\) of level \(t\), and using AppendLeft(\(t,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 code \(c^{\prime}\). Starting from level \(t\), 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 \(t\) 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 stays unchanged or decreases by one, and if it costs 2, the number of locally rich levels decreases by one. **Case (IV):** The case that \(\ell(c)\) belongs to tank[\(b,t\)], \(\ell(c)=t\), and \(t\) is not locally rich. Extended-Lazy behaves in exactly the same way as Case (III). In this case, we do not need Repair by a similar observation as Case (II). It costs either 1 or 2, and the number of locally rich levels increases by one. Figure 7: Execution of Extended-Lazy for a deletion \(d_{c}\). **Case (V):** The case that \(\ell(c)\) belongs to tank[\(b,t\)], \(\ell(c)=b\), and \(t\) is locally rich. First, remove \(c\). If \(c\) was the code assigned to tank[\(b,t\)], stop here; otherwise, do the following: Execute FreeTail(\(t\)) and receive the code \(c^{\prime}\) of level \(b\) from tank[\(b,t\)]. Then, using AppendLeft(\(b,c^{\prime}\)), assign \(c^{\prime}\) to the vertex to which \(c\) was assigned. In this case, we may need Repair because tank[\(b\), \(t\)] becomes unassigned.