姓名：谭旭东
学号：19011210016
嵌牛导读：经典数据结构——跳表
嵌牛鼻子：Java
嵌牛提问：内存排除算法
转载链接：http://182.92.190.128/archives/tiao-biao（我的博客）
- 参考文章：[跳表(SkipList)设计与实现(Java)](https://www.cnblogs.com/bigsai/p/14193225.html)
# 一、跳表的产生
## 1. 问题提出
- 有序链表中，虽然插入和删除节点十分方便，但是节点的查找往往需要遍历链表，是一种效率很低的操作
- 这时，出现一种思路：
- ① 在理想的情况下，一个完整的链表，如果在上面**加N层索引，每一层的节点数量都是下面一层的1/2**
- ② 索引链表的值与其对应的下层链表值相同，在索引链表中一次next可能跨越下层链表中的多个节点，相当于跳跃过去
- ③ 我们查找节点时，从**最上层的最左节点开始寻找，因为节点是有序的，通过节点值与查找值的比较，可以判断往下走/往右走**
- ④ 这样进行查找，在索引中的一次next可能跨越最底层有序链表中的多个节点，相当于跳过中间节点了，所以叫跳表
## 2. <font color=red>概念</font>
- <font color=red>跳表</font>是一个随机化的数据结构，实质就是一种**可以进行二分查找的有序链表**
- 跳表在原有的有序链表上面，增加了多级索引，通过索引二分来快速查找节点，**不但提升了搜索性能，还提升了删除和插入节点的性能**
- 最终跳表将遍历的次数减少到可接受范围内，**其查找效率最终接近二分查找**
- 主要涉及到的算法、思路：
- 有序链表：最底层链表（索引也是有序链表）
- 索引：一种结构，通过二分的方式，只对下一层一半的节点建立索引
- 二分查找：索引设计就是为了模拟二分查找
- 随机化：掷硬币算法，在插入节点时，判断是否生成上层索引
# 二、主要思路分析
围绕着对整个表的**增删改查**，设整个跳表中，**最上层索引的最左节点为head**
## 1. 查找/修改
需要先设置一个临时节点进行节点的移动操作（不能直接移走头节点），team=head
主要步骤如下：
- (1) 从team节点出发，**如果当前节点的key与查询的key相等，那么返回当前节点(如果是修改操作那么一直向下进行修改值即可)**
- (2) 如果key不相等，且**右侧为null**，那么证明只能向下(结果可能出现在下右方向)，此时team=team.down
- (3) 如果key不相等，且右侧不为null，且**右侧节点key小于待查询的key**。那么说明同级还可向右，此时team=team.right
- (4)（否则的情况）如果key不相等，且右侧不为null，且**右侧节点key大于待查询的key**。那么说明如果有结果的话就在这个索引和下个索引之间，此时team=team.down。
模拟一个查询12的情况：
## 2. 删除
删除操作需要对表结构进行改动，所以需要处理好节点之间的关系
其实就是先查找到节点（的前驱节点），然后再进行一层一层往下删除的工作：
- ① 删除节点，还会影响这个节点的前后节点
- ② 删除节点，要<font color=red>继续往下去删除这个节点下方的节点</font>
- ③ 删除节点，我们**要找的是被删除节点的前驱节点**，即team.right == key（单向链表找前驱节点，方便删除；否则需要重新遍历）
主要步骤如下：
- (1) 如果team右侧为null，那么team=team.down(之所以敢直接这么判断是因为左侧有头结点在左侧，不用担心特殊情况)
- (2) 如果team右侧不为null，并且**右侧的key等于待删除的key，那么先删除节点，再team向下team=team.down为了删除下层节点**。
- (3) 如果team右侧不为null，并且右侧key小于待删除的key，那么team向右team=team.right。
- (4) 如果team右侧不为null，并且右侧key大于待删除的key，那么team向下team=team.down，在下层继续查找删除节点
假设我们需要删除节点10：
## 3. <font color=red>插入</font>
插入操作是最麻烦的，因为在插入的过程中不但**涉及到了如何查找插入位置**，还要顺带**把表和索引构建出来**
- 在构建索引时，我们没办法按照理想的情况（n/2）建立索引，只能够通过随机化（掷硬币）的方式，在插入一个节点时确认这个节点是否需要建立上层索引
- 事实上，随机化概率为0.5时，这种方法建立出来的索引出现极端情况的概率很小（极端情况指都建立索引/都不建立索引）
主要步骤如下：
- (1)首先通过上面查找的方式，**找到待插入的左节点。找到左节点之后，直接遍历到最底层去，因为底层是一定要插入节点的，上面的索引层通过掷硬币的方式判断是否插入**
- (2)插入完这一层，需要**考虑上一层是否插入**，首先判断当前索引层级，如果大于最大值那么就停止(比如已经到最高索引层了)。否则设置一个随机数1/2的概率向上插入一层索引(因为理想状态下的就是每2个向上建一个索引节点)。
- 在判断过程中，需要记录下当前节点（也就是上一层节点.down指向的节点），方便直接赋值
- (3)继续(2)的操作，直到概率退出或者索引层数大于最大索引层。
假如我们要插入节点9：
<font color=red></font>
# 三、跳表代码（JAVA版本）
```java
import java.util.Random;
import java.util.Stack;
public class SkipList<T> {
SkipNode headNode; // 头节点：入口
int highLevel; // 最高层数
Random random; // 随机数，掷硬币
final int MAX_LEVEL = 32; // 最大层数
public SkipList() {
random = new Random();
headNode = new SkipNode<Integer>(Integer.MIN_VALUE, null);
highLevel = 0;
}
// 寻找节点功能
public SkipNode search(int key) {
SkipNode team = headNode;
while (team != null) {
if (team.key == key) // 直接返回
return team;
else if (team.right == null) // 右侧为空，往下走
team = team.down;
else if (team.right.key > key) // 右侧更大，往下走
team = team.down;
else // 右侧更小，往右走
team = team.right;
}
return null;
}
// 删除
public void delete(int key) {
SkipNode team = headNode;
while (team != null) {
if (team.right == null)
team = team.down;
else if (team.right.key == key) { // 找到节点了
team.right = team.right.right; // 删除
team = team.down; // 往下走，继续去删除
} else if (team.right.key > key)
team = team.down;
else
team = team.right;
}
}
public void add(SkipNode node) {
int key = node.key;
SkipNode findNode = search(key);
if (findNode != null) {
while (findNode != null) { // 一直往下修改，把全部该节点的值都修改
findNode.value = node.value;
findNode = findNode.down;
}
return;
}
Stack<SkipNode> stack = new Stack<>(); // 记录往下走的所有左节点，掷硬币确定是否需要插入值
SkipNode team = headNode;
while (team != null) {
if (team.right == null) {
stack.push(team);
team = team.down;
} else if (team.right.key > key) { // 已经找到该插入值的位置(在某一层的位置)
stack.push(team);
team = team.down;
} else
team = team.right;
}
int level = 1; // 当前层数，从第一次开始添加
SkipNode downNode = null; // 前驱节点，往上走后，需要记录下层节点是什么，方便插入
while (!stack.isEmpty()) {
team = stack.pop();
SkipNode nodeTeam = new SkipNode(node.key, node.value); // 节点需要新建：每层都是不同对象
nodeTeam.down = downNode; // down属性赋值
downNode = nodeTeam; // 更新前驱节点
if (team.right == null) { // 尾部插入
team.right = nodeTeam;
} else {
nodeTeam.right = team.right;
team.right = nodeTeam;
}
// 考虑是否向上
if (level > MAX_LEVEL)
break;
// 掷硬币，考虑是否向上层添加节点
double coin = random.nextDouble();
if (coin > 0.5)
break;
// 如果到这一步，表示已经决定向上添加
level++;
if (level > highLevel) { // 往上加，突破了当前表的最高层数，需要更新头节点
highLevel = level;
SkipNode highHeadNode = new SkipNode(Integer.MIN_VALUE, null);
highHeadNode.down = headNode; // 新头节点，下面是旧的头节点
headNode = highHeadNode;
stack.push(headNode); // 下次抛出head，作为插入节点的前继左节点
}
}
}
public void printList() {
SkipNode teamNode = headNode;
int index = 1;
SkipNode last = teamNode;
while (last.down != null) {
last = last.down;
}
while (teamNode != null) {
SkipNode enumNode = teamNode.right;
SkipNode enumLast = last.right;
System.out.printf("%-8s", "head->");
while (enumLast != null && enumNode != null) {
if (enumLast.key == enumNode.key) {
System.out.printf("%-5s", enumLast.key + "->");
enumLast = enumLast.right;
enumNode = enumNode.right;
} else {
enumLast = enumLast.right;
System.out.printf("%-5s", "");
}
}
teamNode = teamNode.down;
index++;
System.out.println();
}
}
public static void main(String[] args) {
SkipList<Integer> list = new SkipList<Integer>();
for (int i = 1; i < 20; i++) {
list.add(new SkipNode(i, 666));
}
System.out.println("================删除前====================");
list.printList();
list.delete(4);
list.delete(8);
System.out.println("================删除后====================");
list.printList();
}
}
class SkipNode<T> {
int key;
T value;
SkipNode right; // 左指针
SkipNode down; // 下指针
public SkipNode(int key, T value) {
this.key = key;
this.value = value;
}
}
```
