跳表 skip_list

 
package data_structure

import (
	"math"
	"math/rand/v2"
)

const MaxLv = 11

type Node struct {
	value int          // 节点值
	level int          // 节点拥有最高层数
	next  [MaxLv]*Node // 每一层的下一个节点
}

type Skiplist struct {
	head     *Node // 头节点
	curLevel int   // 当前跳表的最高层数
}

func Constructor() Skiplist {
	sl := Skiplist{
		head: &Node{
			value: math.MinInt64,
			level: 0,
			next:  [MaxLv]*Node{},
		},
	}

	sl.curLevel = 0
	return sl
}

func randomLevel() int {
	level := 0
	for rand.Float32() < 0.5 && level+1 < MaxLv {
		level++
	}
	return level
}

func (this *Skiplist) Search(target int) bool {
	curNode := this.head
	for i := this.curLevel; i >= 0; i-- {
		for curNode.next[i] != nil && curNode.next[i].value <= target {
			curNode = curNode.next[i]
		}
		if curNode.value == target {
			return true
		}
	}
	return false
}

func (this *Skiplist) Add(num int) {
	level := randomLevel()
	update := [MaxLv]*Node{}
	curNode := this.head
	for i := level; i >= 0; i-- {
		for curNode.next[i] != nil && curNode.next[i].value < num {
			curNode = curNode.next[i]
		}
		update[i] = curNode
	}

	newNode := &Node{
		value: num,
		level: level,
		next:  [MaxLv]*Node{nil},
	}

	for i := 0; i <= level; i++ {
		newNode.next[i] = update[i].next[i]
		update[i].next[i] = newNode
	}

	if level > this.curLevel {
		this.curLevel = level
	}
}

func (this *Skiplist) Erase(num int) bool {
	update := [MaxLv]*Node{}
	curNode := this.head
	for i := this.curLevel; i >= 0; i-- {
		for curNode.next[i] != nil && curNode.next[i].value < num {
			curNode = curNode.next[i]
		}
		update[i] = curNode
	}
	if update[0].next[0] == nil || update[0].next[0].value != num {
		return false
	}

	for i := 0; i <= this.curLevel; i++ {
		if update[i].next[i] != nil && update[i].next[i].value == num {
			update[i].next[i] = update[i].next[i].next[i]
		}
	}

	for this.curLevel > 0 && this.head.next[this.curLevel] == nil {
		this.curLevel--
	}
	return true
}

func (this *Skiplist) PrintSkiplist() {
	for i := MaxLv - 1; i >= 0; i-- {
		cur := this.head.next[i]
		if cur == nil {
			continue
		}
		for cur != nil {
			print(cur.value, "->")
			cur = cur.next[i]
		}
		println("nil")
	}
}