按年被提到
20182018 · 1 次2026
算法与数据结构›经典算法与数据结构·arXiv:1806.06726 · cs.DS

Zip Trees

Zip 树
Robert E. Tarjan, Caleb C. Levy, Stephen Timmel · 2018

与跳表同构的随机二叉搜索树,用拆分与合并代替旋转

开始阅读 ↗PDFalphaXiv 讨论
被推荐 · 4 人首次 2018-10-24 · 最近 2026-04-20
4不同的人
6活跃月份
6讨论串
9被引(OpenAlex)

提出 zip tree:每个节点带数值秩,树按秩满足最大堆序,秩相同时偏向较小的键。它本质上是 treap,但秩取自几何分布并允许相同,因此每个节点所需的随机比特更少;插入和删除通过拆分与合并路径(unzip/zip)完成而不用旋转。理论上,最大秩只需 O(log log n) 比特,且 zip tree 与跳表天然同构,简化了跳表与二叉搜索树之间的映射。

HN 为什么提它

在谈跳表、treap 和函数式不可变数据结构时,HN 评论者把它当作值得一看的相关结构来推荐,并引用它说明跳表与 treap 几乎是同一种东西。

方法难度 3 / 5约 45 分钟经得起时间
读之前最好知道
1二叉搜索树与堆
2treap 与跳表(skip list)
3随机化算法与期望分析
4渐近复杂度

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
推荐anfelor · 2023-05

“I would also recommend Koen Claessen's simplified finger trees ([LINK]) and Zip trees for purely functional skip lists.”

推荐 Zip 树,作为纯函数式跳表的替代
Purely Functional Data Structure by Chris Okasaki [pdf]原评论 ↗
推荐anfelor · 2024-03

“Another interesting data structure related to skiplists but not mentioned here are zip trees: Zip Trees”

推荐 Zip 树,一种适合不可变数据的跳表树形变体
What Cannot be Skipped About the Skiplist原评论 ↗
引用Labo333 · 2019-09

“and probably with Zip trees as well.”

提到 Zip 树可能也适用,是简单的随机平衡搜索树
Show HN: Array with Constant Time Access and Fast Insertion and Deletion原评论 ↗
引用anfelor · 2022-08

“There is also a nice new datastructure called Zip Trees [1]”

介绍 Zip 树是一种与跳表同构的随机化搜索树
Let's Talk SkipList原评论 ↗
引用mananaysiempre · 2026-04

“Maestro Tarjan tells us skiplists and treaps are very nearly the same thing: Zip Trees.”

引 Tarjan 的论文,说明跳表和 treap 几乎是同一种东西
What Are Skiplists Good For?原评论 ↗
被提交为 story · 1 次