设计跳表(动态设置节点高度)

最近学习redis的zset时候，又看到跳表的思想，突然对跳表的设置有了新的思考
这是19年设计的跳表，在leetcode的执行时间是200+ms
现在我对跳表有了新的想法
1、跳表的设计，类似二分查找，但是不是二分查找，比较像之前遇到的一个面试题，使用有限个数鸡蛋，确定鸡蛋易损程度
2、跳表无法在设计的时候，就达到完美状态，而是在操作过程中一直维护较完美状态(动态平衡)
基于以上想法，我开始重新进行跳表的设计，在leetCode执行时间为14ms
设计思路如下：
0、设计节点，节点有next和pre两个指针，且因为多层结构，所以是数组表达
1、设计多层数据结构，多层均为有序链表，其中第0层包含所有数值
2、初始时，只有一层结构，先设计为10层结构
3、新增数据时，如果发现步数(即执行next次数)过长(大于3倍层高)，就进行抬升节点高度行为，即节点high值增加

2023-03-04有补充，看最下方

最初代码如下：
Node类

		class Node {Node[] next = new Node[10];Node[] pre = new Node[10];//节点高度int high = 0;//节点值int value;//最近一次走到这个节点的步数int step = 0;//这个仅是为了后续show方法使用int k = 0;}

基础参数及构造器

		//头节点Node head;int maxHigh = 0;//步数int step = 0;public Skiplist() {}

查询操作，不直接查是否有，而是查floor值后，与tagert进行比较，查floor作用是，复用

public boolean search(int target) {if (head == null) {return false;}if (head.value > target) {return false;}//查询Floorreturn searchFloor(head, maxHigh, target).value == target;
}private Node searchFloor(Node node, int high, int target) {//查到了if (node.value == target) {return node;}//已经最下层了if (high == -1) {return node;}//如果next值小于tagert,就进行next操作while (node.next[high] != null &&node.next[high].value <= target) {//步数增加step++;node = node.next[high];node.step = step;}//向下找return searchFloor(node, high - 1, target);
}

新增节点

public void add(int num) {if (head == null) {head = new Node();head.value = num;//没有head，好处理return;}if (num < head.value) {Node newHead = new Node();newHead.value = num;//比head还小，加上之后，充当新headsetNewHead(newHead, head);return;}step = 0;Node newNode = new Node();newNode.value = num;//找到floor，就加在floor后面Node node = searchFloor(head, maxHigh, num);setNext(node, newNode);if (step > 3 * maxHigh) {//需要抬高高度了，这个方法很重要，类似hashmap的扩容resize(newNode);}
}

先把几个简单的方法展示出来

		private void setNext(Node pre, Node node) {int high = node.high;if (pre.next[high] == null) {pre.next[high] = node;node.pre[high] = pre;} else {Node next = pre.next[high];pre.next[high] = node;node.pre[high] = pre;node.next[high] = next;next.pre[high] = node;}}private void setNewHead(Node newHead, Node head) {newHead.high = head.high;for (int i = 0; i <= newHead.high; i++) {newHead.next[i] = head;head.pre[i] = newHead;}this.head = newHead;}

重点在resize

		private void resize(Node node) {if (node.high == maxHigh) {//如果当前高度已经是最高高度了，将maxHigh增高maxHigh++;if (maxHigh == 10) {show();}node.high = maxHigh;head.high = maxHigh;head.next[maxHigh] = node;node.pre[maxHigh] = head;return;}//找前者Node pre = getMoreHighPre(node);//抬高高度node.high++;//加入节点(比如，开始加在0层，这时就记在1层)setNext(pre, node);//更新步数值node.step = pre.step + 1;//步数还大，继续增高if (node.step > 3 * (maxHigh + 1)) {resize(node);}}private Node getMoreHighPre(Node node) {int high = node.high;Node pre = node.pre[high];//找到高一层级的上一个节点while (pre.high == high) {pre = pre.pre[high];}return pre;}

删除操作

		public boolean erase(int num) {if (head == null) {return false;}if (head.value == num) {if (head.next[0] != null && head.next[0].value == num) {//能不删head尽量不删headremoveNode(head.next[0]);} else {//只能删除headremoveHead();}return true;}//一样，找到对应节点Node node = searchFloor(head, maxHigh, num);if (node.value == num) {//移除removeNode(node);return true;}return false;}private void removeNode(Node node) {for (int i = 0; i <= node.high; i++) {//每一层，都要删除Node pre = node.pre[i];Node next = node.next[i];if (next == null) {//注意可能没有nextpre.next[i] = null;} else {pre.next[i] = next;next.pre[i] = pre;}}}private void removeHead() {//删除头节点，就是把老二当老大用if (head.next[0] == null) {head = null;}Node node = head.next[0];node.high = head.high;for (int i = 1; i <= maxHigh; i++) {if (head.next[i] != null && head.next[i] != node) {node.next[i] = head.next[i];head.next[i].pre[i] = node;}}head = node;}

以上代码执行后，leetCode执行时长为19ms，已经远快于19年的代码
但是，我发现了问题所在
因为数组高度有限，设置的高度为10，如果高度不够，就会出现数组越界，我尝试进行测试，写了show方法

		private void show() {System.out.println("总数"+i+"为出现越界");System.out.println("0级，并设置k");head.k = 0;int k = 0;Node node = head;while (node != null) {node.k = k++;node = node.next[0];}for (int i = 1; i < 10; i++) {System.out.println(i + "级间隔：");node = head;Node next = node.next[i];while (next != null) {System.out.print(next.k - node.k + ",");node = next;next = node.next[i];}System.out.println();}}

结果如下

居然一万多数值之后就越界了，思考原因所在
应该是，抬高的node，不应该是插入的那个node，应该是node所在层次的中间node，调整接口如下

通过middleNode，找到需要抬高的node

private void resize(Node node) {if (node.high == maxHigh) {//最高层，这个可以接受maxHigh++;if (maxHigh == max) {show();}node.high = maxHigh;head.high = maxHigh;head.next[maxHigh] = node;node.pre[maxHigh] = head;return;}//找前人Node pre = getMoreHighPre(node);//不应该直接用node升级，应该用node区间的中间值node = middleNode(pre, node);node.high++;//加入节点setNext(pre, node);node.step = pre.step + 1;if (node.step > 3 * (maxHigh + 1)) {resize(node);}
}

寻找middleNode的代码如下

private Node middleNode(Node pre, Node node) {int high = node.high;if (pre.next[high + 1] == null) {return getLast(node);}Node next = pre.next[high + 1];int left = getLen(pre, node, node.high);int right = getLen(node, next, node.high);if (left == right) {return node;}if (left > right) {return left(node, (left - right) / 2);} else {return right(node, (right - left) / 2);}
}private int getLen(Node left, Node right, int high) {int step = 0;while (left != right) {left = left.next[high];step++;}return step;
}private Node left(Node node, int step) {if (step == 0) {return node;}return left(node.pre[node.high], step - 1);
}private Node right(Node node, int step) {if (step == 0) {return node;}return right(node.next[node.high], step - 1);
}private Node getLast(Node node) {int high = node.high;while (node.next[high] != null) {node = node.next[high];}return node;
}

同时发现，最左侧有一些数字极低值，优化setNewHead方法

		private void setNewHead(Node newHead, Node head) {newHead.high = head.high;newHead.next[0] = head;head.pre[0] = newHead;head.high = 0;for (int i = 1; i <= newHead.high; i++) {Node next = head.next[i];if(next==null){break;}newHead.next[i] = next;next.pre[i] = newHead;}this.head = newHead;}

执行leetCode，14ms

使用show方法
结果如下：

数据超过我的想象，百万级了
当然，这不是完美的跳表，比如我只在新增时，判断是否需要抬高(resize),查询时没有，可能出现某些节点运气不好，查询就是很慢

完整代码包括test在下方

public class TiaoBIaoNewTest {static int i =0;public static void main(String[] args) {Skiplist skiplist = new Skiplist();Random random = new Random();for (i = 0; i < 1000000000; i++) {skiplist.add(random.nextInt());}System.out.println();}static class Skiplist {static int max = 10;class Node {Node[] next = new Node[max];Node[] pre = new Node[max];int high = 0;int value;//最近一次走到这个节点的步数int step = 0;int k = 0;}Node head;int maxHigh = 0;//1)先分割0级public Skiplist() {}public boolean search(int target) {if (head == null) {return false;}if (head.value > target) {return false;}Node node = searchFloor(head, maxHigh, target);return node.value == target;}int step = 0;private Node searchFloor(Node node, int high, int target) {if (node.value == target) {return node;}if (high == -1) {return node;}while (node.next[high] != null &&node.next[high].value <= target) {step++;node = node.next[high];node.step = step;}return searchFloor(node, high - 1, target);}public void add(int num) {if (head == null) {head = new Node();head.value = num;return;}if (num < head.value) {Node newHead = new Node();newHead.value = num;setNewHead(newHead, head);return;}step = 0;Node newNode = new Node();newNode.value = num;Node node = searchFloor(head, maxHigh, num);setNext(node, newNode);if (step > 3 * maxHigh) {resize(newNode);}}private void setNewHead(Node newHead, Node head) {newHead.high = head.high;newHead.next[0] = head;head.pre[0] = newHead;head.high = 0;for (int i = 1; i <= newHead.high; i++) {Node next = head.next[i];if(next==null){break;}newHead.next[i] = next;next.pre[i] = newHead;}this.head = newHead;}public boolean erase(int num) {if (head == null) {return false;}if (head.value == num) {if (head.next[0] != null && head.next[0].value == num) {removeNode(head.next[0]);} else {removeHead();}return true;}Node node = searchFloor(head, maxHigh, num);if (node.value == num) {removeNode(node);return true;}return false;}private void removeNode(Node node) {for (int i = 0; i <= node.high; i++) {Node pre = node.pre[i];Node next = node.next[i];if (next == null) {pre.next[i] = null;} else {pre.next[i] = next;next.pre[i] = pre;}}}private void removeHead() {if (head.next[0] == null) {head = null;}Node node = head.next[0];node.high = head.high;for (int i = 1; i <= maxHigh; i++) {if (head.next[i] != null && head.next[i] != node) {node.next[i] = head.next[i];head.next[i].pre[i] = node;}}head = node;}private void resize(Node node) {if (node.high == maxHigh) {//最高层，这个可以接受maxHigh++;if (maxHigh == max) {show();}node.high = maxHigh;head.high = maxHigh;head.next[maxHigh] = node;node.pre[maxHigh] = head;return;}//找前人Node pre = getMoreHighPre(node);//不应该直接用node升级，应该用node区间的中间值node = middleNode(pre, node);node.high++;//加入节点setNext(pre, node);node.step = pre.step + 1;if (node.step > 3 * (maxHigh + 1)) {resize(node);}}private Node middleNode(Node pre, Node node) {int high = node.high;if (pre.next[high + 1] == null) {return getLast(node);}Node next = pre.next[high + 1];int left = getLen(pre, node, node.high);int right = getLen(node, next, node.high);if (left == right) {return node;}if (left > right) {return left(node, (left - right) / 2);} else {return right(node, (right - left) / 2);}}private int getLen(Node left, Node right, int high) {int step = 0;while (left != right) {left = left.next[high];step++;}return step;}private Node left(Node node, int step) {if (step == 0) {return node;}return left(node.pre[node.high], step - 1);}private Node right(Node node, int step) {if (step == 0) {return node;}return right(node.next[node.high], step - 1);}private Node getLast(Node node) {int high = node.high;while (node.next[high] != null) {node = node.next[high];}return node;}private Node getMoreHighPre(Node node) {int high = node.high;Node pre = node.pre[high];while (pre.high == high) {pre = pre.pre[high];}return pre;}private void setNext(Node pre, Node node) {int high = node.high;if (pre.next[high] == null) {pre.next[high] = node;node.pre[high] = pre;} else {Node next = pre.next[high];pre.next[high] = node;node.pre[high] = pre;node.next[high] = next;next.pre[high] = node;}}private void show() {System.out.println("总数"+i+"为出现越界");System.out.println("0级，并设置k");head.k = 0;int k = 0;Node node = head;while (node != null) {node.k = k++;node = node.next[0];}for (int i = 3; i < max; i++) {System.out.println(i + "级间隔：");node = head;Node next = node.next[i];while (next != null) {System.out.print(next.k - node.k + ",");node = next;next = node.next[i];}System.out.println();}}@Overridepublic String toString() {String s = "";Node node = head;while (node != null) {s += node.value + ",";node = node.next[0];}return s;}}
}

2023-03-04补充
今日验证每个节点的搜索路径，验证结果如下：

总数5445676为出现越界
0级，并设置k
9级最大step：33
8级最大step：35
7级最大step：35
6级最大step：35
5级最大step：35
4级最大step：36
3级最大step：38
2级最大step：39
1级最大step：44
0级最大step：58
平均step24.20			总数6749752为出现越界
0级，并设置k
9级最大step：31
8级最大step：32
7级最大step：34
6级最大step：34
5级最大step：36
4级最大step：37
3级最大step：39
2级最大step：45
1级最大step：47
0级最大step：59
平均step24.38总数5829201为出现越界
0级，并设置k
9级最大step：32
8级最大step：33
7级最大step：35
6级最大step：35
5级最大step：37
4级最大step：38
3级最大step：41
2级最大step：46
1级最大step：49
0级最大step：62
平均step24.40

最大step也只是60左右，之所以不是30，之前也说了，是因为没有对查询操作进行提高判断操作(加了判断，有可能反而导致查询减慢)，个人也觉得没必要，平均的查询步骤是24

进行局部修改，当出现待提高node的左相邻节点，本身高度就够情况下，提高左节点(防止较低层级节点密集)
如下

		private void resize(Node node) {if (node.high == maxHigh) {//最高层，这个可以接受maxHigh++;if (maxHigh == max) {show();}node.high = maxHigh;head.high = maxHigh;head.next[maxHigh] = node;node.pre[maxHigh] = head;return;}//找前人Node pre = getMoreHighPre(node);//不应该直接用node升级，应该用node区间的中间值node = middleNode(pre, node);if(pre.next[node.high]==node){//升自己不如升preresize(pre);return;}node.high++;//加入节点setNext(pre, node);node.step = pre.step + 1;if (node.step > 3 * (maxHigh + 1)) {resize(node);}}

验证结果如下：

总数11386207为出现越界
0级，并设置k
9级最大step：32
8级最大step：32
7级最大step：36
6级最大step：37
5级最大step：38
4级最大step：39
3级最大step：41
2级最大step：42
1级最大step：52
0级最大step：62
平均step24.78总数13122318为出现越界
0级，并设置k
9级最大step：30
8级最大step：32
7级最大step：37
6级最大step：38
5级最大step：39
4级最大step：41
3级最大step：42
2级最大step：43
1级最大step：49
0级最大step：63
平均step25.30			总数11352711为出现越界
0级，并设置k
9级最大step：28
8级最大step：30
7级最大step：31
6级最大step：32
5级最大step：35
4级最大step：37
3级最大step：39
2级最大step：42
1级最大step：46
0级最大step：59
平均step25.09

最大步骤没有明显增加，平均步骤从24+增加至25+，查询会些许减慢，但是可容纳数据量，从600w左右，提升至1000w以上，提升明显
以上只是个人实现的跳表，肯定会有问题，欢迎大家一起讨论