做网站的网页用什么软件好,网站建设主流编程软件,对外贸营销型网站建设的几点建议,wordpress wp terms想慢慢的给大家自然的引入跳表。 想想#xff0c;我们
1#xff09;在有序数列里搜索一个数
2#xff09;或者把一个数插入到正确的位置
都怎么做#xff1f;
很简单吧
对于第一个操作#xff0c;我们可以一个一个比较#xff0c;在数组中我们可以二分#xff0c;这…想慢慢的给大家自然的引入跳表。 想想我们
1在有序数列里搜索一个数
2或者把一个数插入到正确的位置
都怎么做
很简单吧
对于第一个操作我们可以一个一个比较在数组中我们可以二分这样比链表快
对于第二个操作二分也没什么用因为找到位置还要在数组中一个一个挪位置时间复杂度依旧是o(n)。
那我们怎么发明一个查找插入都比较快的结构呢 可以打一些标记 这样我们把标记连起来搜索一个数时先从标记开始搜起下一个标记比本身大的话就往下走因为再往前就肯定不符合要求了。
比如我们要搜索18 因为一次可以跨越好多数呀自然快了一些。
既然可以打标记我们可以改进一下选出一些数来再打一层标记 这样我们搜索20是这样的 最终我们可以打好多层标记我们从最高层开始搜索一次可以跳过大量的数依旧是右边大了就往下走。 比如搜索26 最好的情况就是每一层的标记都减少一半这样到了顶层往下搜索其实和二分就没什么两样我们最底层用链表串起来插入一个元素也不需要移动元素所谓跳表就完成了一大半了。 现在的问题是我们对于一个新数到底应该给它打几层标记呢
刚开始一个数都没有所以解决了这个问题我们一直用这个策略更新即可
答案是。。。。。投硬币全看脸。
我其实有点惊讶我以为会有某些很强的和数学相关的算法可以保证一个很好的搜索效率是我想多了。
我们对于一个新数字有一半概率可以打一层标记有一半概率不可以打。
对于打了一层标记的数我们依旧是这个方法它有一半概率再向上打一层标记依次循环。
所以每一层能到达的概率都少一半。
各层的节点数量竟然就可以比较好的维护在很好的效率上最完美的就是达到了二分的效果 再分析一下其实对于同一个数字
等等。。
其实没必要全都用指针因为我们知道通过指针找到一个数可比下标慢多了。
所以同一个数字的所有标记没必要再用指针效率低还不好维护用一个list保存即可。
这样我们就设计出来一个数字的所有标记组成的结构 public static class SkipListNode {public Integer value;//本身的值public ArrayListSkipListNode nextNodes;
//指向下一个元素的结点组成的数组长度全看脸。public SkipListNode(Integer value) {this.value value;nextNodes new ArrayListSkipListNode();}}
将integer比较的操作封装一下 private boolean lessThan(Integer a, Integer b) {return a.compareTo(b) 0;}private boolean equalTo(Integer a, Integer b) {return a.compareTo(b) 0;}
找到在本层应该往下拐的结点 // Returns the node at a given level with highest value less than eprivate SkipListNode findNext(Integer e, SkipListNode current, int level) {SkipListNode next current.nextNodes.get(level);while (next ! null) {Integer value next.value;if (lessThan(e, value)) { // e valuebreak;}current next;next current.nextNodes.get(level);}return current;}
这样我们就写一个一层层往下找的方法并且封装成find(Integer e)的形式 // Returns the skiplist node with greatest value eprivate SkipListNode find(Integer e) {return find(e, head, maxLevel);}// Returns the skiplist node with greatest value e// Starts at node start and levelprivate SkipListNode find(Integer e, SkipListNode current, int level) {do {current findNext(e, current, level);} while (level-- 0);return current;}
刚才的方法是找到最大的小于等于目标的值如果找到的值等于目标跳表中就存在这个目标。否则不存在。 public boolean contains(Integer value) {SkipListNode node find(value);return node ! null node.value ! null equalTo(node.value, value);}
我们现在可以实现加入一个新点了要注意把每层的标记打好 public void add(Integer newValue) {if (!contains(newValue)) {size;int level 0;while (Math.random() PROBABILITY) {level;//能有几层全看脸}while (level maxLevel) {//大于当前最大层数head.nextNodes.add(null);//直接连系统最大maxLevel;}SkipListNode newNode new SkipListNode(newValue);SkipListNode current head;//前一个结点也就是说目标应插current之后do {//每一层往下走之前就可以设置这一层的标记了就是链表插入一个新节点current findNext(newValue, current, level);newNode.nextNodes.add(0, current.nextNodes.get(level));current.nextNodes.set(level, newNode);} while (level-- 0);}}
删除也是一样的 public void delete(Integer deleteValue) {if (contains(deleteValue)) {SkipListNode deleteNode find(deleteValue);size--;int level maxLevel;SkipListNode current head;do {//就是一个链表删除节点的操作current findNext(deleteNode.value, current, level);if (deleteNode.nextNodes.size() level) {current.nextNodes.set(level, deleteNode.nextNodes.get(level));}} while (level-- 0);}}
作为一个容器Iterator那是必须有的吧里面肯定有hasNext和next吧 public static class SkipListIterator implements IteratorInteger {SkipList list;SkipListNode current;public SkipListIterator(SkipList list) {this.list list;this.current list.getHead();}public boolean hasNext() {return current.nextNodes.get(0) ! null;}public Integer next() {current current.nextNodes.get(0);return current.value;}}
这个跳表我们就实现完了。
现实工作中呢我们一般不会让它到无限多层万一有一个数它人气爆炸随机数冲到了一万层呢
所以包括redis在内的一些跳表实现都是规定了一个最大层数的。
别的好像也没什么了。
最后贴出所有代码。
import java.util.ArrayList;
import java.util.Iterator;public SkipListDemo {public static class SkipListNode {public Integer value;public ArrayListSkipListNode nextNodes;public SkipListNode(Integer value) {this.value value;nextNodes new ArrayListSkipListNode();}}public static class SkipListIterator implements IteratorInteger {SkipList list;SkipListNode current;public SkipListIterator(SkipList list) {this.list list;this.current list.getHead();}public boolean hasNext() {return current.nextNodes.get(0) ! null;}public Integer next() {current current.nextNodes.get(0);return current.value;}}public static class SkipList {private SkipListNode head;private int maxLevel;private int size;private static final double PROBABILITY 0.5;public SkipList() {size 0;maxLevel 0;head new SkipListNode(null);head.nextNodes.add(null);}public SkipListNode getHead() {return head;}public void add(Integer newValue) {if (!contains(newValue)) {size;int level 0;while (Math.random() PROBABILITY) {level;}while (level maxLevel) {head.nextNodes.add(null);maxLevel;}SkipListNode newNode new SkipListNode(newValue);SkipListNode current head;do {current findNext(newValue, current, level);newNode.nextNodes.add(0, current.nextNodes.get(level));current.nextNodes.set(level, newNode);} while (level-- 0);}}public void delete(Integer deleteValue) {if (contains(deleteValue)) {SkipListNode deleteNode find(deleteValue);size--;int level maxLevel;SkipListNode current head;do {current findNext(deleteNode.value, current, level);if (deleteNode.nextNodes.size() level) {current.nextNodes.set(level, deleteNode.nextNodes.get(level));}} while (level-- 0);}}// Returns the skiplist node with greatest value eprivate SkipListNode find(Integer e) {return find(e, head, maxLevel);}// Returns the skiplist node with greatest value e// Starts at node start and levelprivate SkipListNode find(Integer e, SkipListNode current, int level) {do {current findNext(e, current, level);} while (level-- 0);return current;}// Returns the node at a given level with highest value less than eprivate SkipListNode findNext(Integer e, SkipListNode current, int level) {SkipListNode next current.nextNodes.get(level);while (next ! null) {Integer value next.value;if (lessThan(e, value)) { // e valuebreak;}current next;next current.nextNodes.get(level);}return current;}public int size() {return size;}public boolean contains(Integer value) {SkipListNode node find(value);return node ! null node.value ! null equalTo(node.value, value);}public IteratorInteger iterator() {return new SkipListIterator(this);}/******************************************************************************* Utility Functions *******************************************************************************/private boolean lessThan(Integer a, Integer b) {return a.compareTo(b) 0;}private boolean equalTo(Integer a, Integer b) {return a.compareTo(b) 0;}}public static void main(String[] args) {}}