10.3. Amortized Insert and Delete

10.3.1. Amortized Insert: Binary Structure

We want to implement the operation W. INSERT(d) efficiently . First, we have to compute W . Therefore we distribute the n data objects of the static structure V among several structures V _i . If a new element has to be inserted, we hope that only a single structure V _i may be concerned . Let

Then a _l a _l _ˆ1 a ₁ a is the binary representation of n . For every a _i = 1, we build a structure V _i that has 2 ⁱ elements. The collection of these structures is a representation of W that is called the binary decomposition (see Figure 10.4). To build up the binary decomposition W , we proceed as follows . In Algorithm 10.1 we use array entries V [ i ] to represent V _i .

The following is the BUILD(D) sketch.

Compute the binary representation of n = D.
Decompose D into sets D _i with D _i = 2 ⁱ w.r.t. the representation of n .
Compute V _i := D _i . Build for every D _i .
Return a pointer to an array of pointers to V _i .

Note that in Algorithm 10.1, the set Bin represents the binary decomposition of n by a sorted set of indices and provides access to the O (log n ) filled components of the array V []. For example, for n = 1010011, we will have Bin = {0, 1, 4, 6}. In this case, we have Bin. Last = 6. Additionally, as mentioned earlier we make use of self-explanatory list and array manipulation. For example, L. First( n ) collects the first n elements of list L , whereas L. Delete First( n ) deletes the first n elements.

Algorithm 10.1: Computing the binary decomposition of a set of objects D.

W D . BinDecomp (D is a set of objects)

  n  :=  D  Bin  :=  n.  BinRep  V  := new array(  Bin .  Last)  BinCopy  :=  Bin . BinCopy   while   BinCopy        do   i  :=  BinCopy .  First  BinCopy .  DeleteFirst  Sub set  := D  .  First(2 ⁱ )  V  [  i  ] :=  Subset .  Build          D := D  .  DeleteFirst(  Subset  )  end while   return W  = (  V  []  , Bin  )

In principle, the binary decomposition W can be constructed as quick as the corresponding structure V .

Lemma 10.1.

Proof: Computing the binary representation of n and the decomposition into D _i can be done in linear time O ( n ).

The operation D _i . Build needs b _V (2 ⁱ ) time. We have i ‰ l = log n , and therefore we conclude:

We used the fact that increases monotonically.

Altogether, we have

since b _V ( n ) is at least linear.

Algorithm 10.2: Collecting all elements of W.

A W . COLLECT( W ) ( W = ( V [] , Bin ) represents the binary decomposition)

  V  [] :=  W.  DataArray  Bin  :=  W.  BinRep  A  := new list  while   Bin        do   i  :=  Bin .  First  A.  ListAdd(  V  [  i  ]  .  Collect)  Bin .  DeleteFirst  end while   return   A

Algorithm 10.3: Computing the query for the binary decomposition W.

A W . QUERY( q ) ( W = ( V [] , Bin ) represents the binary decomposition, q is a query)

  V  [] :=  W.  DataArray  Bin  :=  W.  BinRep  A  := new list  while   Bin        do   i  :=  Bin .  First  A.  ListAdd(  V  [  i  ]  .  Query(  q  ))  Bin .  DeleteFirst  end while   return   A

Algorithm 10.4: Destroying the structure W.

W. DESTROY ( W = ( V [] , Bin ) represents the binary decomposition)

  V  [] :=  W.  DataArray  Bin  :=  W.  BinRep  while   Bin        do   i  :=  Bin .  First  V  [  i  ]  .  Destroy  Bin .  DeleteFirst  end while   V  []  .  Deallocate  Bin .  Deallocate  W.  Deallocate

Similar results hold for some other operations. The operations are designed in a straightforward manner, and we omit the sketches here; Algorithm 10.2, Algorithm 10.3, and Algorithm 10.4 are self-explanatory. The insert operation and its analysis will be explained in more detail now.

First, we can prove

simply by applying V _i . Collect for at most log n structures V _i ; see Algorithm 10.2.

By the same argument, we have

Additionally,

holds if we assume that the query is decomposable; see Algorithm 10.3.

It is easy to see that

which means that we do not need more space. Finally, we have to analyze the insert operation I _W ( n ) in the amortized cost model.

As we have seen from Figure 10.4, sometimes the whole structure of W _n is destroyed when W _n ₊ ₁ has to be built up. In the situation of Figure 10.4, we would like to perform the following construction steps:

In general, we have to build up V _j and extract and erase V _j _ˆ ₁ , V _j _ˆ ₂ , , V only if a _i = 1 holds for i = 0 , 1 , j ˆ 1 and a _j = 0 holds (for the binary representation of the current n ). Algorithm 10.5 also has to update the index set Bin adequately. For example, for n = 1010011, we have Bin {0, 1, 4, 6}. Inserting a new element gives Bin = {2, 4, 6}.

In this special situation, we can prove

where K is a constant. The effort K j stands for combining the collected elements. The rest stems from the properties of the cost functions; see the third function property listed in Section 10.2.

For a long sequence of insertions, many of the insert operations are performed without extreme reconstructions. The effort for all W . INSERT(d) is amortized over time. For the W . INSERT(d) operation, we can prove

The result stems from summing up the reconstruction cost for all V _i structures. V is reconstructed after every insertion, V ₁ is reconstructed after every second insertion, and generally V _i is reconstructed after every 2 ⁱ insertions. For a sequence of n insertions, the total insertion cost is

The average over n gives the result above. Note that apart from insertions, there are only queries in t . Queries do not change the size of the data set, and so we can replace t by the number of insertions n here.

Altogether, the results are presented in the following theorem.

Theorem 10.2. A static abstract data type Static as presented in Figure 10.10 can be dynamized by means of the binary decomposition in a dynamic abstract data type DYNAMIC so that the operation W . INSERT(d) is performed in amortized time

where t denotes the length of the operation sequence.

Let n be the size of the data set. For the remaining operations BUILD , QUERY , DESTROY , and COLLECT and the needed storage, we will achieve

Algorithm 10.5: Inserting an element into the binary decomposition.

W . INSERT( d ) ( W = ( V [] , Bin ) represents the binary decomposition, d is an element)

  W  [] :=  W.  DataArray  Bin  :=  W.  BinRep  j  := 0 D = new list  while   Bin       and  j  = First(  Bin  )  do  D  .  ListAdd(  V  [  j  ]  .  Collect)  V  [  j  ] := Nil  Bin .  DeleteFirst  j  :=  j  + 1  end while  D  .  ListAdd({  d  })  V  [  j  ] := D  .  Build  Bin .  AddFirst(  j  )

10.3.2. Amortized Delete: Half-Size Rule

Assume that we have not implemented the INSERT operation yet. If we have to delete an object, we cannot predict its location in V in advance. Additionally, deletion may cause fundamental reconstruction and is much more difficult than a simple insertion.

For many data structures, it is easier to mark an object as deleted. Physically, the object remains in the structure but no longer belongs to the data set D . Such weakly deleted objects may have some influence on the running time of all operations. Therefore, from time to time, we would like to reconstruct the data structure for the actual data set D .

First, for Static we introduce an additional operation V . WeakDelete(d) with cost function wd _V ( n ). We want to construct a strong delete function DELETE with an acceptable amortized time bound for DYNAMIC. The WeakDelete operation strongly depends on the corresponding data structure.

We will use V . WeakDelete( d ) until D has only the half-size of V . Then weh erase V and build a new structure V out of D . Practically, we can make use of two counters, ActElements and WeakDeleteElements. After every WeakDelete operation, we decrease ActElements and increase WeakDeleteElements. If the counters have the same size, we collect all real elements and rebuild the data structure from scratch. Since the algorithm is trivial, we do not present it in pseudocode. Furthermore, we integrate the DELETE operation into Algorithm 10.6 in the next section.

The cost of the half-size rule is amortized over the preceding WeakDelete operations as follows. We can spread the cost for the reconstruction of V by 1/2 V WeakDelete operations. Additionally, we have to account for the WeakDelete operation itself. This means that the amortized cost of the DELETE operation is given by at most for a sequence of t operations. Since the number of all data objects is at most two times the number of real data, we can apply the third function property listed in Section 10.2: f (2 n ) ˆˆ O ( f ( n )). Consequently, all other operations are not affected, and the running time can be considered for the actual data set. This gives the following general result.

Theorem 10.3. A static abstract data type as presented in Section 10.2 with an additional operation V. WeakDelete( d ) and with additional cost function WD _V ( n ) can be dynamized by means of occasional reconstruction in a dynamic abstract data type TDyn, so that

holds. The size of the actual data set is denoted with r and t denotes the length of the operation sequence.

10.3.3. Amortized Insert and Amortized Delete

In the preceding sections, we discussed INSERT and DELETE separately. Now, we want to show how to combine the two approaches.

A static abstract data type with a WeakDelete implementation is given. As in Section 10.3.1, we use the binary decomposition for the insertion. The WeakDelete operation is available only for the structures V _i , and we have to extend it to W to apply the result of Section 10.3.2. If W. DELETE(d) is applied, d should be marked as deleted in W , rather than physically deleted from storage. But we do not know in which of the structures V _i the element d lies. Therefore, in addition to the binary decomposition, we construct a balanced search tree T that stores this information. For every d ˆˆ W , there is a pointer to the structure V _i with d ˆˆ V _i an example is shown in Figure 10.9.

We can assume that W contains the array V [], the index set Bin , and the search tree T . The additional cost of the search tree T is covered as follows.

QUERY operations are not involved and work as indicated in Section 10.3.1.
Analogously, T has no influence on collecting all elements. Note that only actual elements are collected.
Algorithm 10.4 for the DESTROY operation must be extended for destroying T . Since T has a linear size, the running time of Y( W ) is not concerned.
For the BUILD operation, we need to build up the search tree also. This operation needs O ( r ) time, since the order of the elements in the search tree T is unimported. Fortunately, the cost O ( r ) is subsumed by O (b _V ( r )), because the number of data objects is a lower bound for b _V ( r ).

The corresponding algorithm for DESTROY, BUILD, QUERY, and COLLECT can be easily extended, and we omit the simple pseudocode extension here. We turn to the extended INSERT and DELETE operations.

For W . DELETE(d), there is an additional O (log n ) for searching the corresponding V _i and for marking d as deleted in V _i ; see Algorithm 10.6.

The INSERT operation needs additional O (log 2 r ) time for inserting the new element d into the tree T . Creating a link to its substructure V _j is done in constant time. The costs of these operations are subsumed by the amortized cost of the insertion. Furthermore, V , , V _j _ˆ ₁ has to be erased, and the corresponding objects should point to V _j afterwards. This can be efficiently realized by collecting the pointers of all elements in V , , V _j _ˆ ₁ , { d }. We assume that the pointers belong to the elements. That is, the information will be stored within the elements; see Algorithm 10.7. We collect the pointers and change them to V _j . This operation is already covered by time O (b _V (2 ^j )) for constructing V _j . Additionally, the INSERT operation has to update the counter W. ActElements. The extended INSERT operation is implemented in Algorithm 10.7.

Algorithm 10.6: The extended DELETE operation incorporates the half-size rule and the WeakDelete operation.

W . DELETE( d ) ( W = ( V [] , Bin, T ) represents the binary decomposition with search tree T , and d is an element)

  V  [] :=  W.  DataArray  Bin  :=  W.  BinRep  T  :=  W.  SearchTree  if   W.  ActElements   <  W.  WeakDeleteElements +1  then   D  :=  W.  COLLECT  W .  DESTROY  W  := BUILD(  D  )  else   W.  WeakDeleteElements :=  W.  WeakDeleteElements +1  V  [  i  ] :=  T.  SearchTreeQuery(  d  )  V  [  i  ]  .  WeakDelete(  d  )  end if

Algorithm 10.7: The extended INSERT operation.

W . INSERT( d ) ( W = ( V [] , Bin, T ) represents the binary decomposition with search tree T , and d is an element)

  V  [] :=  W.  DataArray  Bin  :=  W.  BinRep  T  :=  W.  SearchTree  j  := 0 D := new list  P  := new list  while   Bin       and  j  = First(  Bin  )  do  D  .  ListAdd(  V  [  j  ]  .  Collect)  V  [  j  ] := Nil  Bin .  DeleteFirst  j  :=  j  + 1  end while  D  .  Pointer(  V  [  j  ]) D  .  ListAdd({  d  })  V  [  j  ]:= D  .  Build  Bin .  AddFirst(  j  )  T.  Insert(  d  )  W.  ActElements :=  W.  ActElements +1

Altogether we conclude the following.

Theorem 10.4. A static abstract data type Static as presented in Figure 10.10 with an additional operation V . WeakDelete(d) and with additional cost function wd _V ( n ) can be dynamized by means of binary decomposition , search tree T, and the half-size rule in a dynamic abstract data type DYNAMIC so that the amortized time for insertion reads

and the amortized time for deletion reads

For the remaining operations and storage, we obtain the following time functions:

The size of the actual data set is denoted with r, whereas t denotes the length of the operation sequence.