1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
package main

import "math/rand/v2"

const (
	maxLevel = 32
	p        = 0.25
)

type SkiplistNode struct {
	val int
	nxt []*SkiplistNode
}

type Skiplist struct {
	head  *SkiplistNode
	level int
}

func Constructor() Skiplist {
	return Skiplist{
		head: &SkiplistNode{
			val: -1,
			nxt: make([]*SkiplistNode, maxLevel),
		},
		level: 0,
	}
}

func (s *Skiplist) Search(target int) bool {
	cur := s.head
	for i := maxLevel - 1; i >= 0; i-- {
		for cur.nxt[i] != nil && cur.nxt[i].val < target {
			cur = cur.nxt[i]
		}
	}
	cur = cur.nxt[0]
	return cur != nil && cur.val == target
}

func (s *Skiplist) Add(num int) {
	upd := make([]*SkiplistNode, maxLevel)
	for i := range upd {
		upd[i] = s.head
	}

	cur := s.head
	for i := maxLevel - 1; i >= 0; i-- {
		for cur.nxt[i] != nil && cur.nxt[i].val < num {
			cur = cur.nxt[i]
		}
		upd[i] = cur
	}

	level := s.randomLevel()
	s.level = max(s.level, level)

	newNode := &SkiplistNode{
		val: num,
		nxt: make([]*SkiplistNode, level),
	}
	for i, node := range upd[:level] {
		newNode.nxt[i] = node.nxt[i]
		node.nxt[i] = newNode
	}
}

func (s *Skiplist) Erase(num int) bool {
	upd := make([]*SkiplistNode, maxLevel)

	cur := s.head
	for i := maxLevel - 1; i >= 0; i-- {
		for cur.nxt[i] != nil && cur.nxt[i].val < num {
			cur = cur.nxt[i]
		}
		upd[i] = cur
	}
	cur = cur.nxt[0]
	if cur == nil || cur.val != num {
		return false
	}

	for i := 0; i < s.level && upd[i].nxt[i] == cur; i++ {
		upd[i].nxt[i] = cur.nxt[i]
	}
	for s.level > 1 && s.head.nxt[s.level-1] == nil {
		s.level--
	}
	return true
}

func (s *Skiplist) randomLevel() int {
	level := 1
	for level < maxLevel && rand.Float64() < p {
		level++
	}
	return level
}