在插入鍵值對後增加搜索樹中的值

Question

我正在解決一個編程問題，並且遇到了障礙。我試圖想出一個數據結構來將任意整數映射到另一個整數。你可能傾向於說「哈希表！」或「搜索樹！」，我實際上已經想到了這些（甚至嘗試了一個骯髒的實現）。但是有一個問題！每當我從映射中插入或刪除一個值時，我想也增加/減少（通過一個或一些任意偏移量）所有大於或等於插入/刪除值的值。

下面是一個例子。

說我有，我會在這個地圖中使用了我的鑰匙和值的整數兩個列表：

Keys: (1, 6, 18, 21, 24) 
Vals: (2, 1, 3, 0, 4) 

現在，如果我添加一個鍵值對（7,1），我想增加大於或等於1導致這個所有值：

Keys: (1, 6, 7, 18, 21, 24) 
Vals: (3, 2, 1, 4, 0, 5) 

並且隨後，如果我刪除鍵 - 值對（21，0），這是結果：

Keys: (1, 6, 7, 18, 24) 
Vals: (2, 1, 0, 3, 4) 

在每次插入/刪除（即遍歷值並逐個更改它們）之後，這對於一對列表/數組以及一些處理來說是相當簡單的。

但是，我正在尋找一種更有效的方法，可能無需通過整個值列表並遞增/遞減它們。也許通過延遲遞增​​/遞減直到已經請求了一個值（應該已經遞增/遞減）。

有什麼想法？

Answer 1

我認爲，如果您需要通過某個鍵進行快速查找，並根據實際值修改結果，則需要兩個數據結構：一個用於鍵，一個用於值。

密鑰的數據結構將只是一個關聯數組（將它實現爲散列表，自平衡樹或跳過列表，它無關緊要）從您的密鑰到樹中的節點值。

值爲樹將成爲一個自平衡二叉搜索樹（或跳過列表，請參閱下面的編輯）。樹中的節點與它們相關的增量及其值。增量適用於大於或等於特定節點的所有節點，即適用於其自身和其右子樹中的所有節點。

當您插入一個值時，您將增加所有節點的增量大於或等於您要插入的值。這會增加所有節點的實際值，其值大於或等於您在整個樹中插入的值。刪除是相似的，你只需用遞減替換增量。

當您想要讀取值時，可以使用基於鍵的結構在基於值的樹中查找節點。然後你爬到根節點（你必須保留指向樹中父節點的指針），並從節點累積增量，其值大於或等於你開始節點的值。

由於您必須重新計算某些節點的增量，因此您在選擇自平衡算法時必須小心進行重新平衡，但這不會影響時間複雜度。

編輯：對跳轉列表，管理三角洲是很容易的：當你正在尋找插入的地方，增量三角洲鏈表的每一個節點你比較大於或等於該你插入的價值（這也意味着你要下降一級）。刪除是類似的，除了你必須將被刪除的項目的任何增量移動到右邊。

當您想要計算某個節點的實際值時，請儘可能地在當前項目中進行爬升，然後在其中應用增量（一個項目可以在不同級別上多次插入或刪除一個增量，您總是必須使用最高級別的值），然後將鏈接列表中的一個節點放到左側，並重復該過程，直到到達最左側的項目。

您訪問節點的方式也意味着鏈接列表必須雙向鏈接。