跳表(Skip List)

发布时间 2023-04-03 18:08:27作者: 我见青山应如是

跳表(Skip List)

发明者:William Pugh

有序表的一种实现。CRUD操作时间复杂度O(logN)。

把用户输入的不规则转换为一种概率事件来规避。

核心:升层

大致逻辑:
使用头节点head记录所有的层级,头节点不存放数据。
每新增一个数据时,先掷骰子确定层数,从层顶到底层进行添加。

Java代码实现:
// 待添加

public class SkipListMap<K extends Com>