Python數據結構與算法之跳表詳解
0. 學習目標
在諸如單鏈表、雙線鏈表等普通鏈表中，查找、插入和刪除操作由於必須從頭結點遍歷鏈表才能找到相關鏈表，因此時間復雜度均為O(n)。跳表是帶有附加指針的鏈表，使用這些附加指針可以跳過一些中間結點，用以快速完成查找、插入和刪除等操作。本節將介紹跳表的相關概念及其具體實現。
通過本節學習，應掌握以下內容：
- 跳表的基本概念及其與普通鏈表的區別
- 跳表及其操作的實現
1. 跳表的基本概念
跳表 (Skip List) 是一種可以快速進行查找、插入和刪除等操作的有序鏈表(鏈表中的數據項按照某種順序進行排列的鏈表稱為有序鏈表)。跳表的核心思想是以更大的跨度遍歷鏈表，以便可以跳過中間結點。
1.1 跳表介紹
首先，讓我們回想一下如何在以下單鏈表中查找數據元素，即使鏈表中的數據已經排好序，我們也需要從頭結點開始遍歷鏈表。
例如要在以上單鏈表中查找 15，查找過程為： 0–>3–>5 –>7–>10–>15。
為瞭提高查找的效率，我們可以抽取鏈表中的一部分結點建立一個起“索引”作用的鏈，稱為“索引層”或簡稱“索引”：
此時我們查找 15，首先在索引層中遍歷，當我們掃描到值為 10 的結點時，由於下一結點值為 27，因此我們知道 15 應當在這兩個結點之間，然後回到原鏈表中遍歷即可找到值為 15 的結點，遍歷過程如下圖綠色箭頭所示：
可以看到通過建立索引鏈，需要遍歷的結點數得以減少，為瞭進一步減少所需遍歷的結點數，可以通過對索引鏈添加索引，跳表是對鏈表疊加多級索引的數據結構。
1.2 跳表的性能
1.3 跳表與普通鏈表的異同
我們可以將跳表理解為排序後的鏈表，但與普通鏈表相比，有以下不同點：
- 普通鏈表中的結點隻有一個 next 指針，跳表中的結點有多個 next 指針；
- 給定結點的 next 指針的數量是隨機確定的。
跳表中結點的每個 next 指針稱為一層，結點中的層數稱為結點的大小，其決定瞭結點在鏈表中的層級；在普通的有序鏈表中，插入、刪除和查找操作需要對鏈表依次遍歷，因此每個操作的時間復雜度均為O(n)，跳表允許在遍歷時跳過一些中間節點，每個操作的時間復雜度為O(㏒n)。
2. 跳表的實現
跳表中的每個數據元素由一個結點表示，結點的層級在結點插入時隨機選擇，而不考慮數據結構中數據元素的數量。第i級結點有i個next 指針(在結點實現時使用大小為i的數組 next 存儲i個 next 指針)，因此我們不需要在結點中存儲結點的層級，使用最大層數 max_level 來限制層級上限。跳表的頭結點具有從 1 級到 max_level 級的 next 指針。
2.1 跳表結點類
跳表的結點示意圖如下所示，每個結點都有一組用於指向其它層級結點的指針域列表 next：
class Node:
def __init__(self, data, level=0):
self.data = data
self.next = [None] * level
def __str__(self):
return "Node({}, {})".format(self.data, len(self.next))
next 數組用於保存指向不同層級結點的指針，其中每個元素就是一個 next 指針，而 data 變量用於存儲數據，重載 __str__ 方法用於便於打印結點對象，len(self.next) 可以用於表示結點中的層數。
2.2 跳表的初始化
跳表的初始化是建立一個空的帶頭結點的跳表，其表長 length 初始化為 0，此時鏈表中沒有元素結點，隻有一個頭結點：
class SkipList:
def __init__(self, max_level=8):
self.max_level = max_level
node = Node(Node, max_level)
self.head = node
self.length = 0
創建跳表 SkipList 對象的時間復雜度為O(1)。
2.3 獲取跳表長度
求取跳表長度隻需要重載 __len__ 從對象返回 length 的值，因此時間復雜度為O(1)：
def __len__(self):
return self.length
2.4 讀取指定位置元素
由於跳表中的每個結點的層級是在結點插入時隨機選擇的，因此讀取指定位置的數據元素和單鏈表類似，需要順序遍歷第0層結點，操作的復雜度為O(n)，如果索引不在可接受的索引范圍內，將引發 IndexError 異常：：
def __getitem__(self, index):
if index > self.length - 1 or index < 0:
raise IndexError("UnrolledLinkedList assignment index out of range")
else:
count = 0
node = self.head.next[0]
while count < index:
node = node.next[0]
count += 1
return node.data
2.5 查找指定元素
跳表的查找操作從最上層開始，如果待查元素 value 小於當前層的後繼結點的 data，則平移至當前層的後繼結點；否則下移進入下一層，繼續比較，直至第一層。
def locate(self, value):
node = self.head
# 由於索引從0開始，因此第i層級的索引為i-1
level = self.max_level - 1
while level >= 0:
while node.next[level] != None and node.next[level].data < value:
# 平移到當前層的後繼結點
node = node.next[level]
# 下移進入下一層
level -= 1
if node.next[0].data == value:
return node.next[0]
else:
raise ValueError("{} is not in skip list".format(value))
2.6 在跳表中插入新元素
與普通鏈表不同，在跳表中插入新元素不能指定位置(需要保證有序性)，需要通過查找確定新數據元素的插入位置。
插入元素前，首先需要確定該元素所占據的層數 level k，這是通過算法隨機生成的，這樣可以減少算法實現的復雜度，同時也可以保證跳表性能。
def random_level(self, max_level):
num = random.randint(1, 2**max_level -1)
lognum = math.log(num, 2)
level = int(math.floor(lognum))
return max_level - level
然後需要在 level 1, level 2, …, level k 各層的鏈表都插入新元素，為瞭達到此目的，我們需要在查找插入位置時維護一個列表 update，update 中的每個元素 update[i] 指向 level i 中小於插入元素 data 的最右邊結點，即插入位置的左側，如下圖所示，插入元素 data = 9，隨機層數 k=3：
def update_list(self, data):
update = [None] * self.max_level
node = self.head
level = self.max_level - 1
while level >= 0:
while node.next[level] != None and node.next[level].data < data:
node = node.next[level]
update[level] = node
level -= 1
return update
可以看到維護 update 列表的過程與查找元素類似，根據 update 列表可以判斷跳表中是否已存在元素 data，如果不存在將其插入跳表中：
def insert_node(self, data):
# 產生隨機 level，並構造結點
level = self.random_level(self.max_level)
node = Node(data, level)
# 獲取 update 列表
update = self.update_list(data)
# 插入結點
if len(update) == 0 or update[0].next[0] == None or update[0].next[0].data != data:
self.length += 1
for i in range(level):
node.next[i] = update[i].next[i]
update[i].next[i] = node
2.7 刪除跳表中指定元素
刪除指定元素與插入操作類似：
def delete_node(self, data):
# 獲取 update 列表
update = self.update_list(data)
if len(update) > 0:
node = update[0].next[0]
# 刪除指定元素結點
if node != None and node.data == data:
self.length -= 1
for i in range(len(node.next)):
update[i].next[i] = node.next[i]
del node
2.8 其它一些有用的操作
1.跳表指定層元素輸出
將跳表指定層轉換為字符串以便進行打印，編寫 print_level 方法打印指定層中數據元素：
def get_level(self, level):
"""輔助函數，用於根據給定層構造結果字符串"""
node = self.head.next[level]
result = ''
while node:
result = result + str(node.data) + '-->'
node = node.next[level]
result += 'None'
return result
def print_level(self, level):
print('level {}'.format(level))
result = self.get_level(level)
print(result)
2.跳表各層元素輸出
可以借助上述輔助函數 get_level，使用 str 函數調用對象上的 __str__ 方法可以創建適合打印的字符串表示：
def __str__(self):
result = ''
for i in list(range(self.max_level))[self.max_level-1:0:-1]:
result = result + self.get_level(i) + '\n'
result += self.get_level(0)
return result
3. 跳表應用
接下來，我們將測試上述實現的鏈表，以驗證操作的有效性。
3.1 跳表應用示例
首先初始化一個跳表 sl，並在其中插入若幹元素：
sl = SkipList(4)
for i in range(0, 30, 3):
sl.insert_node(i)
我們可以直接打印跳表中的數據元素、鏈表長度等信息：
print('跳表 sl 各層元素為：')
print(sl)
print('跳表 sl 長度為：', len(sl))
print('跳表 sl 第 2 個元素為：', sl[2])
以上代碼輸出如下：
跳表 sl 各層元素為： 9-->None 0-->9-->18-->None 0-->9-->18-->27-->None 0-->3-->6-->9-->12-->15-->18-->21-->24-->27-->None 跳表 sl 長度為： 10 跳表 sl 第 2 個元素為： 6
接下來，我們將演示在添加/刪除元素、以及如何查找指定元素等：
# 插入元素
sl.insert_node(14)
print('在跳表 sl 中插入數據 14 後：')
print(sl)
# 刪除元素
sl.delete_node(14)
print('刪除跳表 sl 中數據 14 後：')
print(sl)
# 查找數據元素 15
print('查找跳表 sl 中數據元素 15：', sl.locate(15))
以上代碼輸出如下：
在跳表 sl 中插入數據 14 後： 9-->None 0-->9-->18-->None 0-->9-->14-->18-->27-->None 0-->3-->6-->9-->12-->14-->15-->18-->21-->24-->27-->None 刪除跳表 sl 中數據 14 後： 9-->None 0-->9-->18-->None 0-->9-->18-->27-->None 0-->3-->6-->9-->12-->15-->18-->21-->24-->27-->None 查找跳表 sl 中數據元素 15： Node(15, 1)
以上就是Python數據結構與算法之跳表詳解的詳細內容，更多關於Python跳表的資料請關註WalkonNet其它相關文章！