[Skip List] 跨越串列

跨越串列，中國那邊稱之為跳表，是由 William Pugh 發明的一種利用隨機性質維護有序性的資料結構，也就是說他能做到普通 binary search tree 能做到的所有操作。

skip list 由多層 (levels) 的 linked-list 組成。每一個插入 skip list 的元素要隨機決定一個高度 (height)，這個高度是幾何分布，也就是高度是 $1$ 的機率是 $1/2$；高度是 $2$ 的機率是 $1/4$；高度是 $3$ 的機率是 $1/8 $；...；高度是 $k$ 的機率是 $1/2^{k}$ 以此類推。高度為 $h$ 的元素會再 $1\sim h$ 層中存在 linked-list 節點，並且每一層的 linked-list 都是排序好的。

這樣的設計可以讓插入、刪除和搜尋變成多層的 linked-list 操作，且平均時間複雜度是 $\ord{\log n}$。

經我個人實測它的效率並沒有比 STL 的紅黑樹還要來高，另一個缺點是若要支援重複元素也較難處理。但他的優勢在於能夠輕鬆改為 concurrent 的版本，這點對需要平衡的二元搜尋樹來說極為困難， TBB 中的 concurrent set 和 concurrent map 都是使用 skip list  實作的。

這裡附上程式碼：