插入跳過列表

Question

A 跳過列表是一種數據結構，其中元素按排序順序存儲，並且列表中的每個節點可以包含多於1個指針，並用於減少搜索所需的時間從單一鏈接列表中的O(n)到平均情況的O(lg n)的操作。它看起來像這樣：

參考：由沃伊切赫·穆拉 「跳錶」 - 自己的工作。通過維基共享資源，根據公有領域授權 - http://commons.wikimedia.org/wiki/File:Skip_list.svg#mediaviewer/File:Skip_list.svg

它可以被看作是一個類比標尺：

在跳躍列表，搜索一個元素，刪除一個是好的，但是當它來插入，它變得困難，因爲根據Data Structures and Algorithms in C++: 2nd edition by Adam Drozdek：

要插入一個新元素，只是插入必須被重組節點以下的所有節點;指針的數量和指針的值必須改變。

---

我可以從這個詮釋，雖然選擇基於節點的可能性指針的隨機數一個節點插入一個新的元素，不創建一個完美的跳躍列表，它變得非常接近它在考慮大量元素時（例如〜900萬）。

我的問題是：爲什麼我們不能在新節點中插入新元素，根據前一個節點確定它的指針數量，將它附加到列表末尾，然後使用高效的排序算法僅對存在於節點中的數據進行排序，從而保持跳過列表的完美結構並且還實現了插入複雜性？

編輯：我還沒有嘗試過任何代碼，我只是提出了一個觀點。僅僅因爲實施跳過列表有點困難。抱歉。

Answer 1

您在這一點上有問題and then use efficient sorting algorithms to sort just the data present in the nodes。對數據進行排序將具有複雜性O(n*lg(n))，因此會增加插入的複雜性。從理論上講，您可以爲插入的每個節點選擇「完美」數量的鏈接，但即使這樣做，當您執行刪除操作時，完美性也會「破碎」。使用隨機化的方法足夠接近完美的結構來表現良好。

Answer 2

您需要有搜索位置的功能/方法。

它需要做以下幾點：

1. 如果插入的唯一密鑰，它需要找到節點。那麼你保留一切，只需更改數據（行李）。例如node-> data = data。

2. 如果您允許重複，或者如果找不到密鑰，那麼此函數/方法需要爲每個高度（通道）提供前一個節點。然後確定新節點的高度並將其插入找到的節點之後。

這裏是我的C++實現： https://github.com/nmmmnu/HM2/blob/master/hm_skiplist.c

您需要檢查以下功能：

static const hm_skiplist_node_t *_hm_skiplist_locate(const hm_skiplist_t *l, const char *key, int complete_evaluation); 

它存儲hm_skiplist_t結構中的位置。

complete_evaluation用於節省時間以防萬一您需要數據並且您不打算插入/刪除。

Answer 3

插入節點時不需要修改任何後續節點。詳情請參閱原稿Skip Lists: A Probabilistic Alternative to Balanced Trees。

我已經實現了該引用的跳過列表，並且我可以向您保證我的插入和刪除例程不會修改插入點前面的任何節點。

我還沒有讀過你指的那本書，但是出於上下文的考慮，你突出顯示的這段文字是錯誤的。