dreamapplehappy / blog

⚔️ 讲解关于正则表达式,前端,后端等相关的知识。也记录自己的一些学习内容
216 stars 22 forks source link

[2018-12-02] 使用JavaScript实现SkipList这种数据结构 #1

Closed dreamapplehappy closed 4 years ago

dreamapplehappy commented 5 years ago

关于这篇文章,大家有什么想法可以在这里提出来

kkdev163 commented 5 years ago

赞,实现的还是很简洁的。

kkdev163 commented 5 years ago

对于数据结构的示意图,还有P.ref[level-1]的理解,与您有些出入。。以下是我理解的示意图: image

mysteryven commented 4 years ago

个人认为 p.refer[i-1] 不是指向的下一层节点,而是和 p.refer[i] 在同一数组的,只比它 index 小一的节点,也就是你在图中表示的 p.refer[i-1] 的下一个节点。

假设我们执行插入操作的 update 数组碰巧都是一竖列那种,也就意味着 update 数组的每一项都是相同的:

newNode[0] = update[0].refer[0]
newNode[1] = update[1].refer[1]
newNode[2] = update[1].refer[2]
...

而此时 update[0] === update[1] === update[2]

所以也就意味着refer[i-1]不是题主图画的那样呢。