## 3 Algorithm Extended-Lazy
### Executions of Extended-Lazy for insertions  
As summarized in Figure 4, the behavior of Extended-Lazy for an insertion \(i_{c}\) is divided into six cases based on the status of the level \(\ell(c)\). **Case (1):** The case that \(\ell(c)\) does not belong to a tank and is rich. Execute AppendRich(\(\ell(c),c\)). The execution of this case costs 1 and the number of locally rich levels increases by at most one because only \(\ell(c)\) changes its status. **Case (2):** The case that \(\ell(c)\) does not belong to a tank and is poor. Furthermore, if we look at the higher levels than \(\ell(c)\) in the order of \(\ell(c)+1,\ell(c)+2,\ldots,h\) until we encounter a level that is rich or a bottom of a tank, we encounter a rich level (say, the level \(t\)) before a bottom of a tank. In this case, execute AppendRich(\(t,c\)). Note that the new tank[\(\ell(c),t\)] is created. This case costs 1 and the number of locally rich levels increases by at most one since only level \(t\) changes its status. **Case (3):** The same as Case (2), but when looking at higher levels, we encounter a bottom \(b\) of tank[\(b,t\)] before we encounter a rich level. Since this case is a little bit complicated, we give an example in Figure 5, in which \(\ell(c)=0\), \(b=1\), and \(t=2\). First, execute FreeTail(\(t\)) and receive the code \(c^{\prime}\) of level \(b\) (because a level-\(b\) code was assigned to level \(t\) by exploiting a tank), and then execute AppendPoor(\(b,c^{\prime}\)) (note that \(b\) is poor by the condition (v) of semi-compactness)(Figure 5). Next, receive another code \(c^{\prime\prime}\) of level \(s\). Note that there is an assigned vertex at \(t\) because of the condition (iv), and hence \(b<s\leq t\)  
Figure 4: Execution of Extended-Lazy for an insertion \(i_{c}\). Then, using AppendRich(\(t,c^{\prime\prime}\)), assign \(c^{\prime\prime}\) to the vertex which was tank[\(b,t\)], which creates the new tank[\(s,t\)] if \(s\
eq t\) (Figure 52). Now, recall that the level \(b\) was poor, and hence \(c^{\prime}\) was assigned to a left child. So, the level \(b\) is currently locally rich. We execute AppendRich(\(b,c\)) (Figure 53). Note that tank[\(\ell(c),b\)] is newly created. In this case, the cost incurred is 3, and the number of locally rich levels does not change. **Case (4):** The case that \(\ell(c)\) is the top of a tank and is rich. First, execute FreeTail(\(\ell(c)\)) and receive the code \(c^{\prime}\) from the bottom of the tank. Then, execute AppendRich(\(\ell(c),c\)) and AppendRich(\(\ell(c),c^{\prime}\)) in this order. Intuitively speaking, we shift the top of the tank to the right, and assign \(c\) to the vertex which was the tank. In this case, it costs 2 and similarly as Case (1), the number of locally rich levels increases by at most one. **Case (5):** The case that \(\ell(c)\) is the top of a tank, say tank[\(b,\ell(c)\)], and is poor. Execute FreeTail(\(\ell(c)\)) and receive the code \(c^{\prime}\) of level \(b\) from tank[\(b,\ell(c)\)], and execute AppendRich(\(\ell(c),c\)) to process \(c\). Note that \(\ell(c^{\prime})\ (=b)\) is poor because \(\ell(c^{\prime})\) was the bottom of tank[\(b,\ell(c)\)]. Also, note that \(b\) currently does not belong to a tank. Hence our current task is to process \(c^{\prime}\) of level \(b\) where \(b\) does not belong to a tank and is poor. So, according to the statuses of levels higher than \(b\), we execute one of Cases (2) or (3). Before going to Cases (2) or (3), the cost incurred is 1 and there is no change in the number of locally rich levels. Hence, the total cost of the whole execution of this case can be obtained by adding one to the cost incurred by the subsequently executed case (Cases (2) or (3)), and the change in the locally rich levels is the same as that of the subsequently executed case. **Case (6):** The case that \(\ell(c)\) belongs to tank[\(b,t\)] and is not the top of tank[\(b,t\)]. Execute FreeTail(\(t\)) and receive the code \(c^{\prime}\) of level \(b\) from tank[\(b,t\)].