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
;
}