skiplist-我真的需要一個解釋，它是如何插入和刪除

我真的不理解這個列表的概率事情。除了聲明「我們必須檢查不超過n/2 + 1個節點（其中n是列表的長度）。給每個第四個節點提前四個指針（圖1c）要求不超過n/4 + 2個節點進行檢查「。這條語句我在以下鏈接中閱讀：ftp：//ftp.cs.umd.edu/pub/skipLists/skiplists.pdfskiplist-我真的需要一個解釋，它是如何插入和刪除

來源

2010-12-12 ms.twenty four

我猜這是與家庭作業有關的問題。你能否讓你的問題更清楚？ – 2010-12-12 17:23:47

其實它不是一個家庭作業，我只是錯過了lec和即時通訊試圖瞭解跳過列表的好處，特別是它如何插入和刪除 – 2010-12-12 17:26:20

我在跳過列表的文章中閱讀該聲明。 – 2010-12-12 17:26:59

跳過列表在他們的Wikipedia article中解釋得很好。如果你有關於數據結構的具體問題，可以自由地問問他們。來自麻省理工學院

來源

2010-12-12 17:36:23

感謝你的幫助。我有插入和刪除功能的問題，我試圖瞭解它們，特別是獲得隨機等級的部分 – 2010-12-12 18:00:26

講座大約跳錶：http://video.google.com/videoplay?docid=-6710586843601387849#

來源

2010-12-12 17:57:55

一種較爲容易理解的解釋可以在這裏找到：http://igoro.com/archive/skip-lists-are-fascinating/

來源

2014-10-27 09:07:58

什麼你不理解的是，每節點有1級的鏈接也就是說，在最底層，數據結構本質上是一個鏈表。使用這個搜索節點當然是O（n）操作。

跳躍列表中的每個節點都有至少一個環節：一個在1 水平平均，節點的一半也有在2級鏈路如果這是最高水平在哪個鏈接存在，那麼你可以在O（n/2）中找到任意節點。基本上，您可以按照第二級節點進行操作，直到您找到要查找的項目，或者直到找到其值大於要查找的節點的節點。此時，您下降到1級節點並從前一個節點向前搜索（即比您要查找的節點更少）。

同樣，平均有1/4的節點在第3級有鏈接。使用這些，你可以在O（n/4）中找到任意節點。您首先搜索級別3節點，直到您找到該節點或超過該節點，然後從該點下降到第2級節點，如果沒有找到第2級節點，則下降到第1級節點。

如果您按照數學計算，可以看到如果最大級別爲m，那麼只要跳過列表中的節點少於2^m，您的平均搜索時間將爲O（log2（n）），其中n是列表中的項目數量。

因此，一個跳躍列表節點的結構是這樣的：

SkiplistNode 
{ 
    int level; 
    SomeType data; // the data held in the node 
    SkiplistNode* forwards[]; // an array of 'level' forward references 
}

如果節點具有爲1的level值，然後將有所述forwards陣列中只有一個項目。如果它是在第4級，那麼將有四個條目：一個用於每個級別4，3，2，以及1

事實證明，在平均大小的forwards陣列的是2。即如下進展1 + 1/2 + 1/4 + 1/8 + 1/16, + 1/32, ...那就是：

Every node has a link at level 1 
1/2 of the nodes have a link at level 2 
1/4 of the nodes have a link at level 3 
1/8 of the nodes have a link at level 4 
etc.

現在更清楚了嗎？

來源

2014-10-28 14:15:12

skiplist-我真的需要一個解釋，它是如何插入和刪除

回答

相關問題