甲結構來表示的有序集合不相交的段

Question

我有一組有序的不相交分段

S = {[a1 b1] [a2 b2] ... [an bn]} 

b1 + 1 < a2, b2 + 1 < a3用等所有數字都是整數。

我正在尋找一個數據結構來表示該操作的集合insert。我知道插入段與S的段之間沒有交集，但是如果b + 1 = ak或bk + 1 = a對於某些k可能需要合併。

Answer 1

如何處理每個節點上的值是一對整數的鏈接列表。 我們需要稍微修改insert操作，我們將其稱爲insertAndMerge。

def insertAndMerge(segment, head) { 
    curr = head; 
    // find element to insert after 
    while (segment.a < curr.b) { 
     curr = curr.next; 
    } 

    // if bk + 1 = a case occurs, merge with existing element, otherwise insert the new one 
    if (curr.b + 1 = segment.a) { 
     curr.b = segment.b; 
    } else { 
     segment.next = curr.next; 
     curr.next = segment; 
     curr = curr.next; 
    } 

    // the insertion or merge above could trigger the b + 1 = ak case, necessitating a merge with the element after it 
    if (curr.b + 1 = curr.next.a) { 
     toRemove = curr.next; 
     curr.next = toRemove.next; 
     curr.b = toRemove.b; 
     delete toRemove; 
    } 
}