服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - 编程技术 - 什么?跳表都不知道的你还敢去面 BAT!

什么?跳表都不知道的你还敢去面 BAT!

2021-11-12 22:21后端技术小牛说 编程技术

跳表这一数据结构,已经成为了Redis面试的高频考点。前两年没这么卷的时候,可能大家从开始学习,到拿到大厂offer这一过程,都可能没听说过跳表这一数据结构。

什么?跳表都不知道的你还敢去面 BAT!

跳表这一数据结构,已经成为了Redis面试的高频考点。前两年没这么卷的时候,可能大家从开始学习,到拿到大厂offer这一过程,都可能没听说过跳表这一数据结构。

那什么是跳表呢?它是用来干啥的?AVL树红黑树知道吧,对,跳表跟他干的事情差不多。我举个例子大家就明白了。假设目前有一个有序数列:

  1. [2, 11,22, 33, 44, 52, 63]

我们想基于单链表的思想,设计一个数据结构,实现查找时间复杂度为O(logn)。单链表的话,它的结构长这个样子。

什么?跳表都不知道的你还敢去面 BAT!

跳表1

当然这个结构,查找时间复杂度妥妥的O(n),那咋改呢?

那换个问法:一般做算法题,手撕代码面试的时候,当咱写了个时间复杂度为O(n)的解法,面试官摇摇头,问你有没有更好的方法,你会怎么做?

常见复杂度O(nlogn) O(n) O(logn) O(1),要优化,一步步来的话,只能上O(logn)了,那复杂度logn最常见的算法是哪个?当然是二分!

思路对了,那对着链表,咋把二分思想融合进去呢?

要不单链表指针这边动动刀子?让指针除了指向后面元素,还能越过几个节点,指向更后面元素?类似二叉查找树?先来看看这个数组对应的二叉查找树长什么样。

什么?跳表都不知道的你还敢去面 BAT!

跳表2

当然,由于我们的结构是单链表,所以只能有由小值,指向大值,这个二叉树得改改。

什么?跳表都不知道的你还敢去面 BAT!

跳表2

好像有点意思在里面了,再把原先单链表的性质加上。

什么?跳表都不知道的你还敢去面 BAT!

跳表2

走线有点凌乱,按单链表的布局显示方式改改:(值得注意的是,我们需要新建一个数组项,每个数组项存储一个指针,指向刚刚二叉搜索树每一层最左侧的节点)

什么?跳表都不知道的你还敢去面 BAT!

(咋感觉越看越像B+树了(雾))

来看个查找逻辑吧:

当查找到的结点保存的数,比要查找的数小时,跳表就会继续访问该层上的下一个结点。

当不满足时,跳表就会用到当前查找到的结点的指针数组的下一层指针,然后沿着下一层指针继续查找。

对于这种数据结构,我们需要从上往下依次查询三个链表,比如我们想查大于35的数字。

首先按左侧数组第一个找,发现中间节点是33,比较一下比35小。

什么?跳表都不知道的你还敢去面 BAT!

发现33比35小,跳下一个节点。

什么?跳表都不知道的你还敢去面 BAT!

发现该节点是Null,跳33的下一层节点。

什么?跳表都不知道的你还敢去面 BAT!

发现52比35大,再跳下一层节点。

什么?跳表都不知道的你还敢去面 BAT!

发现44比35大,跳下一层节点,但由于这是最后一层节点,即44是第一个比33大的数,满足最终条件,就找到了第一个比35大的数字。

我们知道,二叉平衡树,如果设计插入操作,会特别特别麻烦。对于由二叉平衡树思想改的跳表也是如此,对于我们这边的情况,每增加,或者减少一个新节点,每个节点的高度都需要变化。。那有没有高人改进呢?

既然把二叉平衡树改成这四不像了,为啥再不改改,能不能让他不平衡的同时,还能保证查找效率?

说实话,还真可以,来看看这种跳表。

什么?跳表都不知道的你还敢去面 BAT!

跳表1

虽然这个跳表跟咱刚刚讲的跳表比起来,奇形怪状的,但按刚刚的查找思路,还是能做比较好的查询工作的。

而且既然表都长这么奇形怪状了,那添加或者删新元素,其他节点高度不变问题也不大了。

而且惊人的是,如果我们对新插入节点的高度进行随机产生(每次随机大于p,接着往上加高度,小于p停下来),然后别的节点高度保持不变,查找效率还是为O(logn),不会出现像二叉查找树那种直接退化成O(logn)的情况。

有兴趣想看推导的同学点个赞,点赞破100,咱写波推导。(目前面试还没卷到要证明跳表时间复杂度的程度,所以不知道咋推没问题)

原文链接:https://mp.weixin.qq.com/s/uaEOIKEmiBcmo6gGAIXtyg

延伸 · 阅读

精彩推荐