E1=c1+2-Φ1 mum+(2. mum-capacity )-(2.nmum--capacity-) =nm1+(2,mm1-2.(nm-1)-(2(mm2-1)-(nm-1) 带有删除操作的动态表 当a<1/2时插入 (T)=num[/ sieTI d(T)= j2-mumIT1-sizelT] if a(T)21/2, =1+(sie1/2-nm2)-(sie Size[T]/2-num[T] ifa(T)<1/2 =1+(sie1/2-nm1)-(size/2-(mm-1) 当a1<1/2但a1≥12,则 删除操作:α<1/2 C1=c1+d-Φ- =1+(2(mm-1+1)-se1)-(sie12-mm-) 1+(sie2/2-nm)-(sie212-(mm+1)7 清华大学 宋斌恒 37 1 ˆi = i + Φi − Φi− c c (2 capacity ) (2 capacity ) −1 − −1 = + ⋅ − − ⋅ i i i i i num num num = + (2 ⋅ − 2 ⋅( −1)) − (2( −1) − ( −1)) i i i i i num num num num num = + 2 − ( −1) numi numi = 3. 清华大学 宋斌恒 38 0 4 8 12 16 20 24 28 32 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 势能 数量 容量 清华大学 宋斌恒 39 带有删除操作的动态表 ⎩ ⎨ ⎧ − < ⋅ − ≥ Φ = = [ ]/ 2 [ ] ( ) 1/ 2. 2 [ ] [ ] ( ) 1/ 2, ( ) ( ) [ ]/ [ ] size T num T if T num T size T if T T T num T size T α α α 清华大学 宋斌恒 40 当αi <1/2时插入 1 ˆi = i + Φi − Φi− c c 1 ( / 2 ) ( / 2 ) = + i − i − i−1 − numi−1 size num size = 1+ ( / 2 − ) − ( / 2 − ( −1)) i i i numi size num size = 0 清华大学 宋斌恒 41 当 αi-1<1/2 但 αi ≥1/2, 则 1 ˆi = i + Φi − Φi− c c 1 (2 ) ( / 2 ) − − −1 − −1 = + ⋅ i i i i num size size num 1 (2( 1) ) ( / 2 ) = + i−1 + − i−1 − i−1 − i−1 num size size num 3 2 3 3 = ⋅ numi−1 − sizei−1 + 3 2 3 = 3αi−1sizei−1 − sizei−1 + 3 2 3 2 1 1 3 < sizei− − sizei− + = 3. 清华大学 宋斌恒 42 删除操作： αi <1/2 1 ˆi = i + Φi − Φi− c c 1 ( / 2 ) ( / 2 ) = + i − i − i−1 − numi−1 size num size = 1+ ( / 2 − ) − ( / 2 − ( +1)) i i i i size num size num = 2