带有删除操作的动态表 当<12时插入 当a<12但a;≥1/2,则 删除操作:<1/27 清华大学 宋斌恒 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