Golang 程序实现跳跃表
跳跃表是一种动态数据结构，可提供高效的插入、搜索和删除操作。在本文中，我们将演示该函数并探索在 Go 编程语言中实现跳跃表的算法概念。我们将为此演示编写两个不同示例。在第一个示例中，我们将使用随机化方法，在第二个示例中，我们将直接从随机塔结构构建跳跃表，以便更快地遍历。
解释
跳跃表作为一种数据结构，维护元素的排序列表，以便快速搜索，而无需平衡树的复杂性。这是通过创建具有不同跳跃距离的多个链接列表层来实现的，有助于更快地遍历到所需的元素。
语法
func newNode(vlue, lvl int) *node
该语法表示一种称为 `newNode()` 的方法，该方法定义为接受一个值和一个整数来指定塔的高度，并返回一个节点及其值集以及指向不同级别的后续节点的指针数组，用于 Skip List 实现。
func (sl *skipList) randomLvl() int
该语法表示一种称为 `randomLvl()` 的方法，该方法定义为使用概率参数和最大级别为 Skip List 中的新节点生成随机高度，以确定塔的高度高度。
算法
首先用一个基数和一个最大层数初始化跳跃表。
为具有随机层的元素创建节点，最终形成类似塔的结构。
在层内水平连接节点，在层间垂直连接节点。
从左上角开始搜索，然后向右或向下移动。
对于插入，更新节点链接，同时考虑塔的高度。
示例 1
在此示例中，我们将使用随机化在 Go 中实现跳跃表。结构节点保存值和链接指针。函数 insert 通过遍历层添加元素，函数 search 定义为使用多级搜索方法查找元素。randomLvl() 方法生成塔的高度。我们利用每个节点中的下一个指针数组来创建塔结构，该结构直接存储每个节点塔的级别及其与下一个数组的连接。最后在主函数中，使用值初始化跳跃列表。最后，执行元素搜索。
package main
import (
"fmt"
"math/rand"
)
const (
maxLvl = 16
p = 0.5
)
type node struct {
vlue int
nxt []*node
}
type skipList struct{ head *node }
func newNode(vlue, lvl int) *node {
return &node{vlue: vlue, nxt: make([]*node, lvl)}
}
func (sl *skipList) insert(vlue int) {
lvl := sl.randomLvl()
newNode := newNode(vlue, lvl)
crrent := sl.head
for i := lvl - 1; i >= 0; i-- {
for crrent.nxt[i] != nil && crrent.nxt[i].vlue < vlue { crrent = crrent.nxt[i] }
newNode.nxt[i], crrent.nxt[i] = crrent.nxt[i], newNode
}
}
func (sl *skipList) search(vlue int) bool {
crrent := sl.head
for i := len(crrent.nxt) - 1; i >= 0; i-- {
for crrent.nxt[i] != nil && crrent.nxt[i].vlue < vlue { crrent = crrent.nxt[i] }
}
return crrent.nxt[0] != nil && crrent.nxt[0].vlue == vlue
}
func (sl *skipList) randomLvl() int {
lvl := 1
for rand.Float64() < p && lvl < maxLvl { lvl++ }
return lvl
}
func main() {
sl := &skipList{head: newNode(0, maxLvl)}
vlues := []int{3, 6, 9, 2, 5, 8, 1, 4, 7}
for _, v := range vlues { sl.insert(v) }
fmt.Print("Skip List: ")
crrent := sl.head.nxt[0]
for crrent != nil { fmt.Printf("%d -> ", crrent.vlue); crrent = crrent.nxt[0] }
fmt.Println("nil")
fmt.Println("Search 5:", sl.search(5))
fmt.Println("Search 10:", sl.search(10))
}
输出
Skip List: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> nil Search 5: true Search 10: false
示例 2
在本示例中，我们将直接从随机塔结构中实现 Go 中的 Skip List，以便更快地进行遍历。通过创建类似塔的连接来插入元素，并通过多级比较进行类似的搜索。生成随机级别以保持平衡分布。每个级别由一个单独的链表表示，并通过链表节点管理连接。在主函数中，启动 Skip List，最后在其上执行元素搜索。
package main
import (
"fmt"
"math/rand"
)
const (
maxLvl = 16
p = 0.5
)
type node struct {
vlue int
nxt []*node
}
type skipList struct{ head *node }
func newNode(vlue, lvl int) *node {
return &node{vlue: vlue, nxt: make([]*node, lvl)}
}
func (sl *skipList) insert(vlue int) {
lvl, crrent := sl.randomLvl(), sl.head
for i := lvl - 1; i >= 0; i-- {
for crrent.nxt[i] != nil && crrent.nxt[i].vlue < vlue {
crrent = crrent.nxt[i]
}
newNode := newNode(vlue, i+1)
newNode.nxt[i], crrent.nxt[i] = crrent.nxt[i], newNode
}
}
func (sl *skipList) search(vlue int) bool {
crrent := sl.head
for i := len(crrent.nxt) - 1; i >= 0; i-- {
for crrent.nxt[i] != nil && crrent.nxt[i].vlue < vlue {
crrent = crrent.nxt[i]
}
}
return crrent.nxt[0] != nil && crrent.nxt[0].vlue == vlue
}
func (sl *skipList) randomLvl() int {
lvl := 1
for rand.Float64() < p && lvl < maxLvl {
lvl++
}
return lvl
}
func main() {
sl := &skipList{head: newNode(0, maxLvl)}
vlues := []int{3, 6, 9, 2, 5, 8, 1, 4, 7}
for _, v := range vlues {
sl.insert(v)
}
fmt.Println("Skip List:")
for crrent := sl.head.nxt[0]; crrent != nil; crrent = crrent.nxt[0] {
fmt.Printf("%d -> ", crrent.vlue)
}
fmt.Println("nil")
fmt.Println("Search 5:", sl.search(5))
fmt.Println("Search 10:", sl.search(10))
}
输出
Skip List: 1 -> 2 -> 3 -> 5 -> 7 -> 8 -> 9 -> nil Search 5: false Search 10: false
实际实施
游戏开发:在有排行榜或最高分的游戏场景中，跳过列表是保留玩家分数排序的绝佳方式。这使得更新和获取最高分更加容易。
地理空间索引:跳过列表被发现是构建地理索引的一种潜在方式，有助于高效存储和检索地理数据。使用这些索引可以高效检索附近的地点或地区，这对于以位置为中心的应用程序(如地图服务)非常重要。
结论
跳过列表是一种多功能数据结构，兼具简单性和效率，非常适合通过快速搜索、插入和删除操作来维护有序数据。在本文中，我们通过两种不同的方法探讨了实现跳跃列表的概念:与链表实现相比，第一种方法更节省内存，因为它避免了每个节点单独指针的开销。与数组方法相比，下一种方法提供了更好的灵活性和动态调整大小的功能，但从更负面的角度来看，由于单个链表节点的开销，它会消耗更多内存。
