golang数据结构篇之跳表

跳表 复杂度介绍代码insert 打印跳表

复杂度

时间复杂度：O(logN)
空间复杂度：O(N)

介绍

跳表是在一个有序的链表上面建立索引，实现快速查找、插入、删除，redis中的zset的数据结构就是跳表

代码 insert

package main

import (
	"fmt"
	"math/rand"
	"time"
)

const (
	maxLevel = 16
)

// Element 对外的元素抽象
type Element struct {
	Member string
	Score  float64
}

// Level 节点Node中每一层的抽象
type Level struct {
	forward *Node
	span    int64
}

// Node 节点Node
type Node struct {
	Element
	backward *Node
	level    []*Level
}

//跳表
type skipList struct {
	header *Node
	tail   *Node
	length int64
	level  int16
}

//在跳表中插入节点
func (skiplist *skipList) insert(member string, score float64) *Node {
	//既然要插入一个节点，那么就要找到新节点插入位置的前驱节点，这个前驱节点的forward会指向新节点
	//因为插入一个新节点会影响很多层，所以每层都会有一个对应的前驱节点
	updatePre := make([]*Node, maxLevel)
	//保存各层前驱节点的排名(前驱节点是第几个)，用于计算span，span是与下一个节点的距离
	rankPre := make([]int64, maxLevel)
	//刚开始从header节点开始查找
	node := skiplist.header
	for i := skiplist.level - 1; i >= 0; i-- {
		if i != skiplist.level-1 {
			//下一层的rank肯定从上一层的rank开始记录的
			rankPre[i] = rankPre[i+1]
		}
		if node.level[i] != nil {
			//遍历搜素,找到第i层的前驱节点，然后记录第i层的rank
			for (node.level[i].forward != nil && node.level[i].forward.Score < score) ||
				(node.level[i].forward != nil && node.level[i].forward.Score == score && node.level[i].forward.Member < member) {
				rankPre[i] += node.level[i].span
				node = node.level[i].forward
			}
		}
		//记录第i层的前驱节点是哪个Node
		updatePre[i] = node
	}
	// 随机决定新节点的层数
	level := randLevel()
	//可能新层数超过了最高层，那么此时要创建新的层
	if level > skiplist.level {
		for i := skiplist.level; i < level; i++ {
			updatePre[i] = skiplist.header
			updatePre[i].level[i].span = skiplist.length
		}
		//更新最高层
		skiplist.level = level
	}
	//创建新节点
	node = makeNode(level, score, member)

	//前驱节点找到了，排名也统计了，该插入到跳表中了
	for i := int16(0); i < level; i++ {
		//新节点的forward指向前驱节点的forward
		node.level[i].forward = updatePre[i].level[i].forward
		//前驱节点的forward指向新的节点
		updatePre[i].level[i].forward = node
		//至此，当前层（level--> i）插入成功
		//接下来更新前驱节点的span和新节点的span
		node.level[i].span = updatePre[i].level[i].span - (rankPre[0] - rankPre[i])
		updatePre[i].level[i].span = rankPre[0] - rankPre[i] + 1
	}
	//因为新的节点可能不会包含所有的层，所以对于没有的层
	//上面的前驱节点的span要加1，因为新插入了一个节点
	for i := level; i < skiplist.level; i++ {
		updatePre[i].level[i].span++
	}
	//更新前向指针
	if updatePre[0] == skiplist.header {
		node.backward = nil //这种情况发生于插入的位置就在header的后面
	} else {
		node.backward = updatePre[0] //最近的前驱节点Node
	}
	if node.level[0].forward != nil {
		node.level[0].forward.backward = node //后一个的前向指针指自己，这种情况发生于插入位置在中间
	} else {
		skiplist.tail = node //这种情况插入位置在最后
	}
	skiplist.length++
	return node
}
func randLevel() int16 {
	//level := int16(1)
	//for float32(rand.Int31()&0xFFFF) < (0.25 * 0xFFFF) {
	//	level++
	//}
	//if level < maxLevel {
	//	return level
	//}
	//return maxLevel

	level := int16(1)
	for rand.Intn(2) != 1 {
		level++
	}
	if level < maxLevel {
		return level
	}
	return maxLevel

}
func makeNode(level int16, score float64, member string) *Node {
	n := &Node{
		Element: Element{
			Score:  score,
			Member: member,
		},
		level: make([]*Level, level),
	}
	for i := range n.level {
		n.level[i] = new(Level)
	}
	return n
}
func (skiplist *skipList) PrintShipList() {
	fmt.Println("start")
	for i := int(skiplist.level) - 1; i >= 0; i-- {
		node := skiplist.header
		if node.level[i].forward == nil {
			continue
		}
		for j := 0; j <= int(skiplist.length); j++ {
			if node == skiplist.header {
				fmt.Printf("level:%d-head---",i+1)
			} else {
				fmt.Printf("[%d]", int(node.Score))
			}
			cnt := int(node.level[i].span - 1)
			for x := 1; x <= cnt; x++ {
				fmt.Printf("----")
			}
			j += cnt
			if node.level[i].forward == nil {
				break
			} else {
				node = node.level[i].forward
			}
		}
		fmt.Printf("\n")
	}
	fmt.Println("end")

}

func makeSkipList() *skipList {
	return &skipList{
		level:  1,
		header: makeNode(maxLevel, 0, ""),
	}
}

func main() {
	sl := makeSkipList()
	rand.Seed(time.Now().UnixNano())
	mp := make(map[int]int)
	for i := 0; i < 50; i++ {
		cnt := 0
		for !(cnt >= 10 && cnt <= 99) {
			cnt = (rand.Intn(10000) + 100) % 100
			mp[cnt]++
			if mp[cnt] > 1 {
				cnt = 0
			}
		}
		sl.insert("", float64(cnt))
	}
	sl.PrintShipList()
}

打印跳表

start
level:6-head-----------------------------------------------------------------------------------------------------------[58]----------------------------------------------------------------------------------------
level:5-head-----------------------[19]--------[28]----------------------------------------------------[50]------------[58]----------------------------------------------------------------------------------------
level:4-head-------[14]------------[19]--------[28]--------------------------------[44][45]------------[50]------------[58]----------------------------------------------------------------------------------------
level:3-head-------[14]------------[19]--------[28]----[30]------------------------[44][45]----[48]----[50][52]--------[58]----------------------------------------------------------------------------[96]--------
level:2-head-------[14]----[16]----[19]--------[28][29][30][33][35][37]------------[44][45]----[48][49][50][52]----[57][58][59][60]--------[68][72]--------[78]----[83]----[85][87]--------------------[96]--------
level:1-head---[12][14][15][16][17][19][23][25][28][29][30][33][35][37][39][40][41][44][45][47][48][49][50][52][56][57][58][59][60][64][65][68][72][76][77][78][79][83][84][85][87][90][92][93][94][95][96][97][98][99]
end