跳躍表是一種隨機(jī)化的數(shù)據(jù)結(jié)構(gòu)，目前開源軟件 Redis 和 LevelDB 都有用到它述雾，它的效率和紅黑樹以及 AVL 樹不相上下驳庭，但原理相當(dāng)簡單，只要你能熟練操作鏈表柔纵，就能輕松實(shí)現(xiàn)一個(gè)跳躍表缔杉。
skip_list
從圖中可以看到， 跳躍表主要由以下部分構(gòu)成：
- 表頭（head）：負(fù)責(zé)維護(hù)跳躍表的節(jié)點(diǎn)指針搁料。
- 跳躍表節(jié)點(diǎn)：保存著元素值或详，以及多個(gè)層。
- 層：保存著指向其他元素的指針郭计。高層的指針越過的元素?cái)?shù)量大于等于低層的指針霸琴，為了提高查找的效率，程序總是從高層先開始訪問昭伸，然后隨著元素值范圍的縮小梧乘，慢慢降低層次。
- 表尾：全部由
NULL組成庐杨，表示跳躍表的末尾选调。
跳躍表有如下特點(diǎn)：
- 每個(gè)跳躍表由很多層結(jié)構(gòu)組成。
- 每一層都是一個(gè)有序鏈表灵份，且第一個(gè)節(jié)點(diǎn)是頭節(jié)點(diǎn)仁堪。
- 最底層的有序鏈表包含所有節(jié)點(diǎn)。
- 每個(gè)節(jié)點(diǎn)可能有多個(gè)指針填渠，這與節(jié)點(diǎn)所包含的層數(shù)有關(guān)弦聂。
- 跳躍表的查找、插入氛什、刪除的時(shí)間復(fù)雜度均為O(log N)莺葫。
代碼實(shí)現(xiàn)：
import random
MAX_DEPTH = 5
class SkipNode:
def __init__(self, height = 0, elem = None):
self.elem = elem
self.next = [None]*height
def __repr__(self):
return str(self.elem)
class SkipList:
def __init__(self):
self.head = SkipNode()
def updateList(self, elem):
update = [None] * len(self.head.next)
x = self.head
for i in reversed(range(len(self.head.next))):
while x.next[i] != None and \
x.next[i].elem < elem:
x = x.next[i]
update[i] = x
return update
def find(self, elem, update=None):
if update == None:
update = self.updateList(elem)
if len(update) > 0:
candidate = update[0].next[0]
if candidate != None and candidate.elem == elem:
return candidate
return None
def insert(self, elem):
node = SkipNode(self.randomHeight(), elem)
while len(self.head.next) < len(node.next):
self.head.next.append(None)
update = self.updateList(elem)
if self.find(elem, update) == None:
for i in range(len(node.next)):
node.next[i] = update[i].next[i]
update[i].next[i] = node
def randomHeight(self):
k = 1
while random.randint(0, 1):
k = k + 1
if k == MAX_DEPTH:
break
return k
def remove(self, elem):
update = self.updateList(elem)
x = self.find(elem, update)
if x != None:
for i in range(len(x.next)):
update[i].next[i] = x.next[i]
if self.head.next[i] == None:
self.head.next = self.head.next[:i]
return
def traversal(self):
for i in reversed(range(len(self.head.next))):
x = self.head
line = []
while x.next[i] != None:
line.append(str(x.next[i].elem))
x = x.next[i]
print('line{}: '.format(i+1) + '->'.join(line))
主要方法updateList的作用是，從跳躍表的最頂層開始依次向下查找枪眉，找到該層級中比給定元素elem小的最大一個(gè)元素捺檬，將該元素保存起來，重復(fù)以上步驟知道到達(dá)最底層瑰谜。它返回一個(gè)列表update欺冀，update[0]表示第一層最后一個(gè)比elem小的元素，以此類推萨脑。該方法可以使得插入刪除操作變得更加簡單隐轩。
在向跳躍表中插入新的結(jié)點(diǎn)時(shí)候，我們需要生成該結(jié)點(diǎn)的層數(shù)渤早。使用拋硬幣的思想隨機(jī)生成層數(shù)职车，如果是正面（random.randint(0, 1) == 1）則層數(shù)加一，直到拋出反面為止鹊杖。其中的 MAX_DEPTH 是防止如果運(yùn)氣太好悴灵，層數(shù)就會(huì)太高，而太高的層數(shù)往往并不會(huì)提供額外的性能骂蓖。
