推荐anfelor · 2023-05
“I would also recommend Koen Claessen's simplified finger trees ([LINK]) and Zip trees for purely functional skip lists.”
推荐 Zip 树,作为纯函数式跳表的替代
与跳表同构的随机二叉搜索树,用拆分与合并代替旋转
提出 zip tree:每个节点带数值秩,树按秩满足最大堆序,秩相同时偏向较小的键。它本质上是 treap,但秩取自几何分布并允许相同,因此每个节点所需的随机比特更少;插入和删除通过拆分与合并路径(unzip/zip)完成而不用旋转。理论上,最大秩只需 O(log log n) 比特,且 zip tree 与跳表天然同构,简化了跳表与二叉搜索树之间的映射。
在谈跳表、treap 和函数式不可变数据结构时,HN 评论者把它当作值得一看的相关结构来推荐,并引用它说明跳表与 treap 几乎是同一种东西。
“I would also recommend Koen Claessen's simplified finger trees ([LINK]) and Zip trees for purely functional skip lists.”
“Another interesting data structure related to skiplists but not mentioned here are zip trees: Zip Trees”
“and probably with Zip trees as well.”
“There is also a nice new datastructure called Zip Trees [1]”
“Maestro Tarjan tells us skiplists and treaps are very nearly the same thing: Zip Trees.”