algorithm/skiplist.go at master · xttty/algorithm · GitHub

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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
package algorithm

import (
	"math/rand"
	"time"
)

const maxLevel = 7

// SkipNode  跳跃表节点
type SkipNode struct {
	Val   int
	level uint8
	ptrs  []*SkipNode
}

// NewSkipList 初始化
func NewSkipList(value int) *SkipNode {
	level := randomLevel()
	node := &SkipNode{
		Val:   value,
		level: level,
		ptrs:  make([]*SkipNode, level),
	}
	return node
}

// Search 跳跃表搜索
func (head *SkipNode) Search(value int) *SkipNode {
	node := head.search(value)
	if node.Val != value {
		return nil
	}
	return node
}

func (head *SkipNode) search(value int) *SkipNode {
	node := head
	level := node.level
	for node.Val < value {
		for node.ptrs[level-1] == nil || node.ptrs[level-1].Val > value {
			level--
			if level <= 0 {
				break
			}
		}
		if level == 0 || node.ptrs[level-1] == nil {
			break
		}
		node = node.ptrs[level-1]
		level = node.level
	}
	return node
}

// Add 新增节点
func (head *SkipNode) Add(value int) *SkipNode {
	node := head.search(value)
	if node.Val == value {
		return head
	} else if node.Val > value {
		node.Val, value = value, node.Val
	}
	insertNode := &SkipNode{
		Val:   value,
		level: randomLevel(),
	}
	insertNode.ptrs = make([]*SkipNode, insertNode.level)
	node = head
	for node.ptrs[0] != insertNode {
		level := node.level
		for level > insertNode.level {
			level--
		}
		for level > 0 && (node.ptrs[level-1] == nil || node.ptrs[level-1].Val > value) {
			insertNode.ptrs[level-1] = node.ptrs[level-1]
			node.ptrs[level-1] = insertNode
			level--
		}
		if level > 0 {
			node = node.ptrs[level-1]
		}
	}
	return head
}

// Delete 删除节点
func (head *SkipNode) Delete(value int) *SkipNode {
	node := head.search(value)
	if node.Val != value {
		return head
	}
	tempNode := head
	level := uint8(maxLevel)
	for level > 0 && tempNode != nil {
		level = tempNode.level
		for level > node.level {
			level--
		}
		for level > 0 && tempNode.ptrs[level-1] == node {
			tempNode.ptrs[level-1] = node.ptrs[level-1]
			level--
		}
		if level > 0 {
			tempNode = tempNode.ptrs[level-1]
		}
	}
	return head
}

func randomLevel() uint8 {
	rand.Seed(time.Now().UnixNano())
	level := rand.Int()%maxLevel + 1
	return uint8(level)
}