Skip List跳躍表原理及實現
Skip lists are a data structure that can be used in place of balanced trees。 Skip lists use probabilistic balancing rather than strictly enforced balancing and as a result the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees。
–William Pugh
轉載整理至：
Skip List（跳躍表）原理詳解與實現
skiplist 跳躍表詳解及其程式設計實現
跳錶SkipList
跳錶是由William Pugh發明的，上面的引言就是他給出的解釋。跳錶是一種隨機化的資料結構，目前開源軟體 Redis 和 LevelDB 都有用到它，它的效率和紅黑樹以及 AVL 樹不相上下，但跳錶的原理相當簡單，只要你能熟練操作連結串列，就能輕鬆實現一個 SkipList。
跳躍表結構體
typedef
struct
node
//每個節點的資料結構
{
keyType
key
；
// key值
valueType
value
；
// value值
struct
node
*
next
［
1
］；
// 後繼指標陣列，柔性陣列 可實現結構體的變長
}
Node
；
typedef
struct
skip_list
//跳錶結構
{
int
level
；
// 最大層數
Node
*
head
；
//指向頭結點
}
skip_list
；
柔性陣列
*sizeof（Node*）））柔性陣列既陣列大小待定的陣列， C語言中結構體的最後一個元素可以是大小未知的陣列，也就是所謂的0長度，所以我們可以用結構體來建立柔性陣列。柔性陣列既陣列大小待定的陣列， C語言中結構體的最後一個元素可以是大小未知的陣列，也就是所謂的0長度，所以我們可以用結構體來建立柔性陣列。
#define new_node（n） （（Node*）malloc（sizeof（Node）+n
跳躍表的插入
跳錶的插入總結起來需要三步：
查詢到待插入位置， 每層跟新update陣列；
需要隨機產生一個層數；
從高層至下插入，與普通連結串列的插入完全相同；
//插入元素的時候元素所佔有的層數完全是隨機演算法
int
randomLevel
（）
{
int
level
=
1
；
while
（
rand
（）
%
2
）
level
++
；
level
=
（
MAX_L
>
level
）
？
level
：
MAX_L
；
return
level
；
}
/*
step1：查詢到在每層待插入位置，跟新update陣列
step2：需要隨機產生一個層數
step3：從高層至下插入，與普通連結串列的插入完全相同。
*/
bool
insert
（
skip_list
*
sl
，
keyType
key
，
valueType
val
）
{
Node
*
update
［
MAX_L
］；
Node
*
q
=
NULL
，
*
p
=
sl
->
head
；
//q，p初始化
int
i
=
sl
->
level
-
1
；
/******************step1*******************/
//從最高層往下查詢需要插入的位置，並更新update
//即把降層節點指標儲存到update陣列
for
（
；
i
>=
0
；
——
i
）
{
while
（（
q
=
p
->
next
［
i
］）
&&
q
->
key
<
key
）
p
=
q
；
update
［
i
］
=
p
；
}
if
（
q
&&
q
->
key
==
key
）
//key已經存在的情況下
{
q
->
value
=
val
；
return
true
；
}
/******************step2*******************/
//產生一個隨機層數level
int
level
=
randomLevel
（）；
//如果新生成的層數比跳錶的層數大
if
（
level
>
sl
->
level
）
{
//在update陣列中將新新增的層指向header
for
（
i
=
sl
->
level
；
i
<
level
；
++
i
）
{
update
［
i
］
=
sl
->
head
；
}
sl
->
level
=
level
；
}
//printf（“%d\n”， sizeof（Node）+level*sizeof（Node*））；
/******************step3*******************/
//新建一個待插入節點，一層一層插入
q
=
create_node
（
level
，
key
，
val
）；
if
（
！
q
）
return
false
；
//逐層更新節點的指標，和普通連結串列插入一樣
for
（
i
=
level
-
1
；
i
>=
0
；
——
i
）
{
q
->
next
［
i
］
=
update
［
i
］
->
next
［
i
］；
update
［
i
］
->
next
［
i
］
=
q
；
}
return
true
；
}
刪除結點
bool
erase
（
skip_list
*
sl
，
keyType
key
）
{
Node
*
update
［
MAX_L
］；
Node
*
q
=
NULL
，
*
p
=
sl
->
head
；
int
i
=
sl
->
level
-
1
；
for
（；
i
>=
0
；
——
i
）
{
while
（（
q
=
p
->
next
［
i
］）
&&
q
->
key
<
key
）
{
p
=
q
；
}
update
［
i
］
=
p
；
}
//判斷是否為待刪除的key
if
（
！
q
||
（
q
&&
q
->
key
！=
key
））
return
false
；
//逐層刪除與普通連結串列刪除一樣
for
（
i
=
sl
->
level
-
1
；
i
>=
0
；
——
i
）
{
if
（
update
［
i
］
->
next
［
i
］
==
q
）
//刪除節點
{
update
［
i
］
->
next
［
i
］
=
q
->
next
［
i
］；
//如果刪除的是最高層的節點，則level——
if
（
sl
->
head
->
next
［
i
］
==
NULL
）
sl
->
level
——
；
}
}
free
（
q
）；
q
=
NULL
；
return
true
；
}
查詢操作
valueType
*
search
（
skip_list
*
sl
，
keyType
key
）
{
Node
*
q
，
*
p
=
sl
->
head
；
q
=
NULL
；
int
i
=
sl
->
level
-
1
；
for
（；
i
>=
0
；
——
i
）
{
while
（（
q
=
p
->
next
［
i
］）
&&
q
->
key
<
key
）
{
p
=
q
；
}
if
（
q
&&
key
==
q
->
key
）
return
&
（
q
->
value
）；
}
return
NULL
；
}