数据结构 - 跳跃链表

雨点打透心脏的1/2处 2023-05-31 12:15 63阅读 0赞

### 文章目录 ###

*  数据结构 - 跳跃链表
 *   *  一，为什么会有跳表？
     *  二，跳表结构
     *  三，跳表元素查询
     *  四，跳表元素插入
     *  五，跳表元素删除
     *  六，完整代码

# 数据结构 - 跳跃链表 #

> 作者今年大三，正在准备明年的春招，文章中有写得不对的，希望大家及时指出文章中的错误的地方，大家一起努力!

## 一，为什么会有跳表？ ##

> 以下图片均来自：[https://blog.csdn.net/xushiyu1996818/article/details/89841112\#%E4%B8%BA%E4%BB%80%E4%B9%88%E8%A6%81%E6%9C%89%E8%B7%B3%E8%A1%A8][https_blog.csdn.net_xushiyu1996818_article_details_89841112_E4_B8_BA_E4_BB_80_E4_B9_88_E8_A6_81_E6_9C_89_E8_B7_B3_E8_A1_A8]

对于一个普通的单链表，如图：

![img][]

如果我们想要查找55号节点，那么我们需要从头结点依次遍历到尾节点，那么对于单链表的节点查询来说，如果链表节点数量很大的情况下，那么需要遍历的节点数量也会越多，时间复杂度是O(N)

> 这样我们就会想，有什么方法会让我们访问链表某一节点的速度加快？

如果我们尝试另一条访问路径，比如

![img][img 1]

这样我们访问55号节点就会相比之前访问的节点数减少了，头结点 ->2 -> 21 -> 37 -> 55

> 如果我们还想更快呢？

根据上图的思路，我们也许还可以开辟一条路出来

![img][img 2]

此时访问55号节点就只要经过头结点，21号节点，55号节点，访问速度大大加快

可以想象，当链表节点达到很多的时候，比如：

![img][img 3]

使用跳表的查询方式比普通链表的遍历要快的多

> 这种思想其实和二分查找法的思想很相似

所以，这种查询的时间复杂度可以达到O(logN)

> 对比平衡树？

AVL平衡树的插入和删除，查询操作都可以在O(logN)的复杂度完成，但是AVL平衡树的插入和删除需要通过左旋或者右旋去调整树的节点，相对跳表来说是要复杂的。跳表也是支持动态插入和删除的一种动态的数据结构，其查找，插入和删除的时间复杂度也能做到和AVL平衡树媲美的O(logN)，是一种以空间换时间的做法。跳表在redis中是sort set的底层实现

## 二，跳表结构 ##

> 跳表的最底层可以是双向链表也可以单链表，看情况而定，但是索引层一般是单链表

节点类

class ListNode:
    
        def __init__(self, data: Optional[int] = None):
            self._data = data     # 数值域
            self._forwards = []   # 向前指针

跳表：

class SkipList:
    
        # 最大层数
        _MAX_LEVEL = 16
    
        def __init__(self):
            self._level_count = 1
            self._head = ListNode()
            self._head._forwards = [None] * type(self)._MAX_LEVEL

## 三，跳表元素查询 ##

> 其实上面已经对跳表元素查询做了一个简单的介绍了，接下来讲具体讲讲
> 
> 接下来用到的图片来自：https://blog.csdn.net/pcwl1206/article/details/83512600\#commentBox

如果我需要查询13号节点

![img][img 4]

此时，我们只需要在level2（第二级索引层）遍历1,7,13便找到了13号节点

> 又如果我想要查找11号节点

我会先遍历level2（第二级索引层）发现13号节点比我要查找的11号节点大，那么我会退回7号节点，从7号节点往下一层，到达level1（第一级索引层）从7号节点往前遍历，遍历9，又发现13号节点比我要查找的11号节点大，此时从9号节点往下一层，到达level0（最底层）从9开始往前遍历，遍历10，发先10前边是13，没有我们所需要的节点11

代码实现：

# 查询跳表节点
        def find(self, value: int) -> Optional[ListNode]:
            p = self._head  # 从头结点开始查找
            for i in range(self._level_count - 1, -1, -1):   # 从最高层开始，一层一层查找
                while p._forwards[i] and p._forwards[i]._data < value: # 每一层中向前查找
                    p = p._forwards[i]  
            # 现在找到的是最接近这个value的节点，可以这么说：node.data <= value
            return p._forwards[0] if p._forwards[0] and p._forwards[0]._data == value else None

## 四，跳表元素插入 ##

对于纯粹的单链表，需要遍历每个结点，来找到插入的位置。但是对于跳表来说，查找的时间复杂度为O(logn)，所以这里查找某个数据应该插入的位置的时间复杂度也是O(logn)，如下图所示：

![img][img 5]

节点插入不单单是最后底层的链表插入节点而已，还需要调整层级level

# 插入节点
        def insert(self, value: int):
            # 生成随机level
            level = self._random_level()
            # 如果原level小于生成的随机level则更新level为刚生成的level
            if self._level_count < level: self._level_count = level
            # 构造新增节点
            new_node = ListNode(value)
            new_node._forwards = [None] * level # forwards指向每层第一个节点
            update = [self._head] * level # update数组保存每层插入节点的前驱节点     
    
            p = self._head
            # 寻找插入位置
            for i in range(level - 1, -1, -1):
                while p._forwards[i] and p._forwards[i]._data < value:
                    p = p._forwards[i]
                
                update[i] = p     # update数组保存每层插入节点的前驱节点     
    
            # 插入节点，调整节点间指向关系
            for i in range(level):
                # 相当于 newNode.next = pre.next
                new_node._forwards[i] = update[i]._forwards[i]  
                # 相当于 pre.next = newNode
                update[i]._forwards[i] = new_node

随机函数：

最理想的情况就是，一级索引中元素个数应该占原始数据的 50%，二级索引中元素个数占 25%，三级索引12.5% ，一直到最顶层。因为这里每一层的晋升概率是 50%。对于每一个新插入的节点，都需要调用 randomLevel 生成一个合理的层数。该 randomLevel 方法会随机生成 1~MAX\_LEVEL 之间的数，且 ：50%的概率返回 1， 25%的概率返回 2，12.5%的概率返回 3 …

# 随机函数，在redis中，概率是取到1/4
        def _random_level(self, p: float = 0.5) -> int:
            level = 1
            while random.random() < p and level < type(self)._MAX_LEVEL:
                level += 1
            return level

## 五，跳表元素删除 ##

在跳表中删除某个结点时，如果这个结点在索引中也出现了，我们除了要删除原始链表中的结点，还要删除索引中的。因为单链表中的删除操作需要拿到删除结点的前驱结点，然后再通过指针操作完成删除。所以在查找要删除的结点的时候，一定要获取前驱结点（双向链表除外）。因此跳表的删除操作时间复杂度即为O(logn)。

# 删除跳表节点    
        def delete(self, value):
            update = [None] * self._level_count
            p = self._head
            for i in range(self._level_count - 1, -1, -1):
                while p._forwards[i] and p._forwards[i]._data < value:
                    p = p._forwards[i]
                update[i] = p   # 要删除节点的前驱节点
    
            # 判断是否符合删除条件
            if p._forwards[0] and p._forwards[0]._data == value:
                for i in range(self._level_count - 1, -1, -1):
                    if update[i]._forwards[i] and update[i]._forwards[i]._data == value:
                        update[i]._forwards[i] = update[i]._forwards[i]._forwards[i]   # 相当于pre.next = pre.next.next

## 六，完整代码 ##

from typing import Optional
    import random
    
    class ListNode:
    
        def __init__(self, data: Optional[int] = None):
            self._data = data     # 数值域
            self._forwards = []   # 向前指针
    
    class SkipList:
    
        # 最大层数
        _MAX_LEVEL = 16
    
        def __init__(self):
            self._level_count = 1
            self._head = ListNode()
            self._head._forwards = [None] * type(self)._MAX_LEVEL
    
        # 查询跳表节点
        def find(self, value: int) -> Optional[ListNode]:
            p = self._head  # 从头结点开始查找
            for i in range(self._level_count - 1, -1, -1):   # 从最高层开始，一层一层查找
                while p._forwards[i] and p._forwards[i]._data < value: # 每一层中向前查找
                    p = p._forwards[i]   
            # 现在找到的是最接近这个value的节点，可以这么说：node.data <= value
            return p._forwards[0] if p._forwards[0] and p._forwards[0]._data == value else None
    
        # 插入跳表节点
        def insert(self, value: int):
            # 生成随机level
            level = self._random_level()
            # 如果原level小于生成的随机level则更新level为刚生成的level
            if self._level_count < level: self._level_count = level
            # 构造新增节点
            new_node = ListNode(value)
            new_node._forwards = [None] * level # forwards指向每层第一个节点
            update = [self._head] * level # update数组保存每层插入节点的前驱节点     
    
            p = self._head
            # 寻找插入位置
            for i in range(level - 1, -1, -1):
                while p._forwards[i] and p._forwards[i]._data < value:
                    p = p._forwards[i]
                
                update[i] = p     # update[i]是要插入位置的前驱节点     
    
            # 插入节点，调整节点间指向关系
            for i in range(level):
                # 相当于 newNode.next = pre.next
                new_node._forwards[i] = update[i]._forwards[i]  
                # 相当于 pre.next = newNode
                update[i]._forwards[i] = new_node     
    
        # 删除跳表节点    
        def delete(self, value):
            update = [None] * self._level_count
            p = self._head
            for i in range(self._level_count - 1, -1, -1):
                while p._forwards[i] and p._forwards[i]._data < value:
                    p = p._forwards[i]
                update[i] = p   # 要删除节点的前驱节点
    
            # 判断是否符合删除条件
            if p._forwards[0] and p._forwards[0]._data == value:
                for i in range(self._level_count - 1, -1, -1):
                    if update[i]._forwards[i] and update[i]._forwards[i]._data == value:
                        update[i]._forwards[i] = update[i]._forwards[i]._forwards[i]   # 相当于pre.next = pre.next.next
    
        '''
        最理想的情况就是，一级索引中元素个数应该占原始数据的 50%，二级索引中元素个数占 25%，三级索引12.5% ，一直到最顶层。
        因为这里每一层的晋升概率是 50%。对于每一个新插入的节点，都需要调用 randomLevel 生成一个合理的层数。
        该 randomLevel 方法会随机生成 1~MAX_LEVEL 之间的数，且 ：
            50%的概率返回 1
            25%的概率返回 2
            12.5%的概率返回 3 ...
        '''
        # 随机函数，在redis中，概率是取到1/4
        def _random_level(self, p: float = 0.5) -> int:
            level = 1
            while random.random() < p and level < type(self)._MAX_LEVEL:
                level += 1
            return level
    
        def __repr__(self) -> str:
            values = []
            p = self._head
            while p._forwards[0]:
                values.append(str(p._forwards[0]._data))
                p = p._forwards[0]
            return "->".join(values)
    
    
    if __name__ == "__main__":
        l = SkipList()
        for i in range(10):
            l.insert(i)
        print(l)
        p = l.find(7)
        print(p._data)
        l.delete(3)
        print(l)

[https_blog.csdn.net_xushiyu1996818_article_details_89841112_E4_B8_BA_E4_BB_80_E4_B9_88_E8_A6_81_E6_9C_89_E8_B7_B3_E8_A1_A8]: https://blog.csdn.net/xushiyu1996818/article/details/89841112#%E4%B8%BA%E4%BB%80%E4%B9%88%E8%A6%81%E6%9C%89%E8%B7%B3%E8%A1%A8
[img]: /images/20230531/210c23ce41c9466db07f5437e2bd8953.png
[img 1]: /images/20230531/97ced63209c44b728042c448615a49f5.png
[img 2]: /images/20230531/87050f880afa4729a3a9c90621e6d3e9.png
[img 3]: /images/20230531/e2f41c84d10a425cbdac79cc546b7c19.png
[img 4]: /images/20230531/d4d33b5a5c114922a0ce59089683fe42.png
[img 5]: /images/20230531/a58811b2dfbd40cbb728595df82309b9.png