数据结构示意图 #

代码实现 #

package main

import "math/rand"

const (
	MaxLevel    = 16  // 跳表的最大层数
	Probability = 0.5 // 随机提升层数的概率
)

type SkipList struct {
	head  *Node
	level int
}

type Node struct {
	key   int
	value string
	next  []*Node
}

func randomLevel() int {
	level := 1
	for rand.Float64() < Probability && level < MaxLevel {
		level++
	}
	return level
}

func NewSkipList() *SkipList {
	return &SkipList{
		head:  NewNode(0, "", MaxLevel),
		level: 1,
	}
}

func NewNode(key int, value string, level int) *Node {
	return &Node{
		key:   key,
		value: value,
		next:  make([]*Node, level),
	}
}

// 插入元素
func (sl *SkipList) Insert(key int, value string) {
	update := make([]*Node, MaxLevel)
	node := sl.head

	// 找到每一层最后一个<key的节点放入update中
	for i := sl.level - 1; i >= 0; i-- {
		for node.next[i] != nil && node.next[i].key < key {
			node = node.next[i]
		}
		update[i] = node
	}

	// 随机层数
	level := randomLevel()
	// 将>sl.level的层，sl.head加入update中
	if level > sl.level {
		for i := sl.level; i < level; i++ {
			update[i] = sl.head
		}
		sl.level = level
	}

	// 将新节点加入跳表
	newNode := NewNode(key, value, level)
	for i := 0; i < level; i++ {
		newNode.next[i] = update[i].next[i]
		update[i].next[i] = newNode
	}
}

// 查找元素
func (sl *SkipList) Search(key int) (string, bool) {
	// 从最高层开始往下，找到最后一个比key小的节点
	node := sl.head
	for i := sl.level - 1; i >= 0; i-- {
		for node.next[i] != nil && node.next[i].key < key {
			node = node.next[i]
		}
	}

	node = node.next[0]
	if node != nil && node.key == key {
		return node.value, true
	}

	return "", false
}

// 删除元素
func (sl *SkipList) Delete(key int) bool {
	update := make([]*Node, MaxLevel)

	// 从最高层开始往下，找到最后一个比key小的节点
	node := sl.head
	for i := sl.level; i >= 0; i-- {
		for node.next[i] != nil && node.next[i].key < key {
			node = node.next[i]
		}
		update[i] = node
	}

	// 判断元素是否存在
	node = node.next[0]
	if node == nil || node.key != key {
		return false
	}

	// 从第1层开始往上，剔除目标节点
	for i := 0; i < sl.level; i++ {
		if update[i].next[i] != node {
			break
		}
		update[i].next[i] = node.next[i]
	}

	// 如果高层除了头节点没有多余节点，则降层
	for sl.level > 1 && sl.head.next[sl.level-1] == nil {
		sl.level--
	}

	return true
}

func main() {
	sl := skiplist.NewSkipList()
	sl.Insert(1, "Hello")
	sl.Insert(2, "World")
	sl.Insert(3, "SkipList")

	if value, found := sl.Search(2); found {
		fmt.Println("Found key 2 with value:", value)
	} else {
		fmt.Println("Key 2 not found")
	}

	sl.Delete(2)
	if value, found := sl.Search(2); found {
		fmt.Println("Found key 2 with value:", value)
	} else {
		fmt.Println("Key 2 not found")
	}

}