golang数据结构篇之跳表

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