点击蓝字关注我们
来源:程序员小灰(chengxuyuanxiaohui)
————— 第二天 —————
如何进行二分查找呢?
首先根据数组下标,定位到数组的中间元素:
由于要查找的元素20,大于中间元素12,再次定位到数组右半部分的中间元素:
这一次定位到的元素正好是20,查找成功。
如果数组的长度是n,二分查找的时间复杂度是O(logn),比起从左到右逐个遍历元素进行查找的方式,大大提升了查找性能。
如上图所示,想要定位到链表的中间结点9,是无法直接定位的,需要从头结点开始,顺着next指针,逐个访问下一个结点。
因此,链表这种数据结构并不适用于二分查找。
————————————
常见的图书目录,就像下面这样:
第5章对应的页码是170,因此我们直接翻到书的第170页,就是第5章的内容。
如图所示,在原始链表的基础上,我们增加了一个索引链表。原始链表的每两个结点,有一个结点也在索引链表当中。
这样做有什么好处呢?当我们想要定位到结点20,我们不需要在原始链表中一个一个结点访问,而是首先访问索引链表:
在索引链表找到结点20之后,我们顺着索引链表的结点向下,找到原始链表的结点20:
这个过程,就像是先查阅了图书的目录,再翻到章节所对应的页码。
由于索引链表的结点个数是原始链表的一半,查找结点所需的访问次数也相应减少了一半。
多层次的图书目录,就像下面这样:
如图所示,我们基于原始链表的第1层索引,抽出了第2层更为稀疏的索引,结点数量是第1层索引的一半。
这样的多层索引可以进一步提升查询效率,假如仍然要查找结点20,让我们来演示一下过程:
首先,我们从最上层的索引开始查找,找到该层中仅小于结点20的前置索引结点12:
接下来,我们顺着结点12访问下一层索引,在该层中找到结点20:
最后,我们顺着第1层索引的结点20向下,找到原始链表的结点20:
在这个例子中,由于原始链表的结点数量较少,仅仅需要2层索引。如果链表的结点数量非常多,我们就可以抽出更多的索引层级,每一层索引的结点数量都是低层索引的一半。
假设原始链表有n个结点,那么索引的层级就是log(n)-1,在每一层的访问次数是常量,因此查找结点的平均时间复杂度是O(logn)。这比起常规的查找方式,也就是线性依次访问链表节点的方式,效率要高得多。
但相应的,这种基于链表的优化增加了额外的空间开销。假设原始链表有n个结点,那么各层索引的结点总数是n/2+n/4+n/8+n/16+......2,约等于n。
也就是说,优化之后的数据结构所占空间,是原来的2倍。这是典型的以空间换时间的做法。
假设我们要插入的结点是10,首先我们按照跳表查找结点的方法,找到待插入结点的前置结点(仅小于待插入结点):
接下来,按照一般链表的插入方式,把结点10插入到结点9的下一个位置:
这样是不是插入工作就完成了呢?并不是。随着原始链表的新结点越来越多,索引会渐渐变得不够用了,因此索引结点也需要相应作出调整。
如何调整索引呢?我们让新插入的结点随机“晋升”,也就是成为索引结点。新结点晋升成功的几率是50%。
假设第一次随机的结果是晋升成功,那么我们把结点10作为索引结点,插入到第1层索引的对应位置,并且向下指向原始链表的结点10:
新结点在成功晋升之后,仍然有机会继续向上一层索引晋升。我们再进行一次随机,假设随机的结果是晋升失败,那么插入操作就告一段落了。
小灰说的是什么意思呢?让我们看看下图,新结点10已经晋升到第2层索引,下一次随机的结果仍然是晋升成功,这时候该怎么办呢?
假设我们要从跳表中删除结点10,首先我们按照跳表查找结点的方法,找到待删除的结点:
接下来,按照一般链表的删除方式,把结点10从原始链表当中删除:
这样是不是删除工作就完成了呢?并不是。我们需要顺藤摸瓜,把索引当中的对应结点也一一删除:
刚才的例子当中,第3层索引的结点已经没有了,因此我们把整个第3层删去:
最终的删除结果如下:
1. 程序中跳表采用的是双向链表,无论前后结点还是上下结点,都各有两个指针相互指向彼此。
2. 程序中跳表的每一层首位各有一个空结点,左侧的空节点是负无穷大,右侧的空节点是正无穷大。
之所以这样设计,是为了方便代码实现。代码中的跳表就像下图这样:
public class SkipList{ //结点“晋升”的概率 private static final double PROMOTE_RATE = 0.5; private Node head,tail; private int maxLevel; public SkipList() { head = new Node(Integer.MIN_VALUE); tail = new Node(Integer.MAX_VALUE); head.right = tail; tail.left = head; } //查找结点 public Node search(int data){ Node p= findNode(data); if(p.data == data){ System.out.println("找到结点:" + data); return p; } System.out.println("未找到结点:" + data); return null; } //找到值对应的前置结点 private Node findNode(int data){ Node node = head; while(true){ while (node.right.data!=Integer.MAX_VALUE && node.right.data<=data) { node = node.right; } if (node.down == null) { break; } node = node.down; } return node; } //插入结点 public void insert(int data){ Node preNode= findNode(data); //如果data相同,直接返回 if (preNode.data == data) { return; } Node node=new Node(data); appendNode(preNode, node); int currentLevel=0; //随机决定结点是否“晋升” Random random = new Random(); while (random.nextDouble() < PROMOTE_RATE) { //如果当前层已经是最高层,需要增加一层 if (currentLevel == maxLevel) { addLevel(); } //找到上一层的前置节点 while (preNode.up==null) { preNode=preNode.left; } preNode=preNode.up; //把“晋升”的新结点插入到上一层 Node upperNode = new Node(data); appendNode(preNode, upperNode); upperNode.down = node; node.up = upperNode; node = upperNode; currentLevel++; } } //在前置结点后面添加新结点 private void appendNode(Node preNode, Node newNode){ newNode.left=preNode; newNode.right=preNode.right; preNode.right.left=newNode; preNode.right=newNode; } //增加一层 private void addLevel(){ maxLevel++; Node p1=new Node(Integer.MIN_VALUE); Node p2=new Node(Integer.MAX_VALUE); p1.right=p2; p2.left=p1; p1.down=head; head.up=p1; p2.down=tail; tail.up=p2; head=p1; tail=p2; } //删除结点 public boolean remove(int data){ Node removedNode = search(data); if(removedNode == null){ return false; } int currentLevel=0; while (removedNode != null){ removedNode.right.left = removedNode.left; removedNode.left.right = removedNode.right; //如果不是最底层,且只有无穷小和无穷大结点,删除该层 if(currentLevel != 0 && removedNode.left.data == Integer.MIN_VALUE && removedNode.right.data == Integer.MAX_VALUE){ removeLevel(removedNode.left); }else { currentLevel ++; } removedNode = removedNode.up; } return true; } //删除一层 private void removeLevel(Node leftNode){ Node rightNode = leftNode.right; //如果删除层是最高层 if(leftNode.up == null){ leftNode.down.up = null; rightNode.down.up = null; }else { leftNode.up.down = leftNode.down; leftNode.down.up = leftNode.up; rightNode.up.down = rightNode.down; rightNode.down.up = rightNode.up; } maxLevel --; } //输出底层链表 public void printList() { Node node=head; while (node.down != null) { node = node.down; } while (node.right.data != Integer.MAX_VALUE) { System.out.print(node.right.data + " "); node = node.right; } System.out.println(); } //链表结点类 public class Node { public int data; //跳表结点的前后和上下都有指针 public Node up, down, left, right; public Node(int data) { this.data = data; } } public static void main(String[] args) { SkipList list=new SkipList(); list.insert(50); list.insert(15); list.insert(13); list.insert(20); list.insert(100); list.insert(75); list.insert(99); list.insert(76); list.insert(83); list.insert(65); list.printList(); list.search(50); list.remove(50); list.search(50); } }给我点个“在看”呗