skiplist(跳表)算法實現
跳表是平衡樹的一種替代的數據結構，但是和紅黑樹不相同的是，跳表對于樹的平衡的實現是基于一種隨機化的算法的，這樣也就是說跳表的插入和刪除的工作是比較簡單的。
下面來研究一下跳表的核心思想：
先從鏈表開始，如果是一個簡單的鏈表，那么我們知道在鏈表中查找一個元素I的話，需要將整個鏈表遍歷一次。
如果是說鏈表是排序的，并且節點中還存儲了指向前面第二個節點的指針的話，那么在查找一個節點時，僅僅需要遍歷N/2個節點即可。
這基本上就是跳表的核心思想，其實也是一種通過“空間來換取時間”的一個算法，通過在每個節點中增加了向前的指針，從而提升查找的效率。
跳表的數據存儲模型
我們定義：
如果一個基點存在k個向前的指針的話，那么陳該節點是k層的節點。
一個跳表的層MaxLevel義為跳表中所有節點中最大的層數。
下面給出一個完整的跳表的圖示：
那么我們該如何將該數據結構使用二進制存儲呢？通過上面的跳表的很容易設計這樣的數據結構：
定義每個節點類型：
//定義每個節點類型：
type nodeStructure struct {
key int // key值
value int // value值
forward []*nodeStructure
}
上面的每個結構體對應著圖中的每個節點，如果一個節點是一層的節點的話（如7，12等節點），那么對應的forward將指向一個只含一個元素的數組，以此類推。
定義跳表數據類型：
// 定義跳表數據類型
type listStructure struct {
level int /* Maximum level of the list (1 more than the number of levels in the list) */
header *nodeStructure /* pointer to header */
}
跳表數據類型中包含了維護跳表的必要信息，level表明跳表的層數，header如下所示：
初始化的過程很簡單，僅僅是生成下圖中紅線區域內的部分，也就是跳表的基礎結構：
//跳表初始化
func newList() *listStructure {
var l *listStructure
var i int
// 申請list類型大小的內存
l = &listStructure{}
// 設置跳表的層level，初始的層為0層（數組從0開始）
l.level = 0
// 生成header部分
l.header = newNodeOfLevel(MaxNumberOfLevels)
// 將header的forward數組清空
for i = 0; i < MaxNumberOfLevels; i++ {
l.header.forward[i] = nil
}
return l
}
插入操作
由于跳表數據結構整體上是有序的，所以在插入時，需要首先查找到合適的位置，然后就是修改指針（和鏈表中操作類似），然后更新跳表的level變量。
func insert(l *listStructure, key int, value int) bool {
var k int
// 使用了update數組
var update [MaxNumberOfLevels]*nodeStructure
var p, q *nodeStructure
p = l.header
k = l.level
fmt.Printf("list level: %v\n", k)
for ; k >= 0; k-- {
// 查找插入位置
q = p.forward[k]
for q != nil && q.key < key {
p = q
q = p.forward[k]
}
// 設置update數組
update[k] = p
} // 對于每一層進行遍歷 一直到最低層
// 這里已經查找到了合適的位置，并且update數組已經
// 填充好了元素 貌似不插入重復元素
if q != nil && q.key == key {
q.value = value
return false
}
// 隨機生成一個層數
k = randomLevel()
fmt.Printf("random Level: %v\n", k)
if k > l.level {
// 如果新生成的層數比跳表的層數大的話
// 增加整個跳表的層數
l.level++
k = l.level
// 在update數組中將新添加的層指向l->header
update[k] = l.header
}
// 生成層數個節點數目
q = newNodeOfLevel(k + 1)
q.key = key
q.value = value
// 每層插入節點
for ; k >= 0; k-- {
p = update[k]
q.forward[k] = p.forward[k]
p.forward[k] = q
}
// 如果程序運行到這里，程序已經插入了該節點
return true
}
刪除某個節點
和插入是相同的，首先查找需要刪除的節點，如果找到了該節點的話，那么只需要更新指針域，如果跳表的level需要更新的話，進行更新。
func delete(l *listStructure, key int) bool {
var k, m int
// 生成一個輔助數組update
var update [MaxNumberOfLevels]*nodeStructure
var p, q *nodeStructure
p = l.header
k = l.level
m = l.level
//指向該節點對應層的前驅節點 一直到最低層
for ; k >= 0; k-- {
q = p.forward[k]
for q != nil && q.key < key {
p = q
q = p.forward[k]
}
update[k] = p
}
// 如果找到了該節點，才進行刪除的動作
if q != nil && q.key == key {
// 指針運算
for k = 0; k <= m && update[k].forward[k] == q; k++ {
// 這里可能修改l.header.forward數組的值的
p = update[k]
p.forward[k] = q.forward[k]
}
// 如果刪除的是最大層的節點，那么需要重新維護跳表的
// 層數level
for l.header.forward[m] == nil && m > 0 {
m--
}
l.level = m
return true
} else {
return false
}
}
skiplist完整代碼：
package main
import (
"fmt"
"math/rand"
"time"
)
//定義每個節點類型：
type nodeStructure struct {
key int // key值
value int // value值
forward []*nodeStructure
}
// 定義跳表數據類型
type listStructure struct {
level int /* Maximum level of the list (1 more than the number of levels in the list) */
header *nodeStructure /* pointer to header */
}
const (
MaxNumberOfLevels = 11
MaxLevel = 10
)
// newNodeOfLevel生成一個nodeStructure結構體，同時生成l個*nodeStructure數組指針
//#define newNodeOfLevel(l) (*nodeStructure)malloc(sizeof(struct nodeStructure)+(l)*sizeof(nodeStructure *))
func newNodeOfLevel(level int) *nodeStructure {
nodearr := make([]*nodeStructure, level) //new([level]*node)
return &nodeStructure{forward: nodearr}
}
//跳表初始化
func newList() *listStructure {
var l *listStructure
var i int
// 申請list類型大小的內存
l = &listStructure{}
// 設置跳表的層level，初始的層為0層（數組從0開始）
l.level = 0
// 生成header部分
l.header = newNodeOfLevel(MaxNumberOfLevels)
// 將header的forward數組清空
for i = 0; i < MaxNumberOfLevels; i++ {
l.header.forward[i] = nil
}
return l
}
func randomLevel() int {
r := rand.New(rand.NewSource(time.Now().UnixNano()))
return r.Intn(MaxLevel)
}
func insert(l *listStructure, key int, value int) bool {
var k int
// 使用了update數組
var update [MaxNumberOfLevels]*nodeStructure
var p, q *nodeStructure
p = l.header
k = l.level
for ; k >= 0; k-- {
// 查找插入位置
q = p.forward[k]
for q != nil && q.key < key {
p = q
q = p.forward[k]
}
// 設置update數組
update[k] = p
} // 對于每一層進行遍歷 一直到最低層
// 這里已經查找到了合適的位置，并且update數組已經
// 填充好了元素 貌似不插入重復元素
if q != nil && q.key == key {
q.value = value
return false
}
// 隨機生成一個層數
k = randomLevel()
if k > l.level {
// 如果新生成的層數比跳表的層數大的話
// 增加整個跳表的層數
l.level++
k = l.level
// 在update數組中將新添加的層指向l->header
update[k] = l.header
}
// 生成層數個節點數目
q = newNodeOfLevel(k + 1)
q.key = key
q.value = value
// 每層插入節點
for ; k >= 0; k-- {
p = update[k]
q.forward[k] = p.forward[k]
p.forward[k] = q
}
// 如果程序運行到這里，程序已經插入了該節點
return true
}
func delete(l *listStructure, key int) bool {
var k, m int
// 生成一個輔助數組update
var update [MaxNumberOfLevels]*nodeStructure
var p, q *nodeStructure
p = l.header
k = l.level
m = l.level
//指向該節點對應層的前驅節點 一直到最低層
for ; k >= 0; k-- {
q = p.forward[k]
for q != nil && q.key < key {
p = q
q = p.forward[k]
}
update[k] = p
}
// 如果找到了該節點，才進行刪除的動作
if q != nil && q.key == key {
// 指針運算
for k = 0; k <= m && update[k].forward[k] == q; k++ {
// 這里可能修改l.header.forward數組的值的
p = update[k]
p.forward[k] = q.forward[k]
}
// 如果刪除的是最大層的節點，那么需要重新維護跳表的
// 層數level
for l.header.forward[m] == nil && m > 0 {
m--
}
l.level = m
return true
} else {
return false
}
}
func search(l *listStructure, key int) int {
var k int
var p, q *nodeStructure
p = l.header
k = l.level
//指向該節點對應層的前驅節點 一直到最低層
for ; k >= 0; k-- {
q = p.forward[k]
for q != nil && q.key < key {
q = q.forward[k]
}
if q != nil && q.key == key {
return q.value
}
}
if q != nil && q.key == key {
return q.value
} else {
return -1
}
}
func main() {
l := newList()
insert(l, 3, 30)
insert(l, 6, 60)
insert(l, 7, 70)
insert(l, 9, 90)
delete(l, 9)
insert(l, 12, 120)
insert(l, 17, 170)
insert(l, 19, 190)
fmt.Printf("skiplist:%v\n", search(l, 12))
fmt.Printf("skiplist:%v\n", search(l, 9))
}
程序輸出結果:
skiplist:120 skiplist:-1
本文由用戶 jope3014 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。
轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。
本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！