算法与理论计算机2018arxiv.org
Zip Trees
Zip Trees
进阶 · 约 35 分钟读完前置知识：二叉搜索树、堆序与优先队列、随机化分析
导读
论文提出 Zip Trees：一种用随机 rank（按几何分布抽取）维持堆序的二叉搜索树，用于实现有序字典。插入和删除可完全自顶向下完成，通过 zip/unzip 路径调整结构，期望重构代价为 O(1)，搜索/插入/删除整体期望 O(log n)。作者强调它比红黑树、弱 AVL 树等确定性平衡树的更新算法更简单。
HN 关注点：这种随机化 BST 能否以更简单的方式达到平衡树效率；讨论焦点是它与已知 treap/笛卡尔树的高度相似性及新颖性。
HN 评论精选
这几条评论里：支持 1 质疑 2 补充 1
质疑质疑其新颖性：认为它只是标准 split/merge treap 换了优先级分布。
如果我理解错了请纠正：这不就是标准的带 split/merge 的 treap（论文第 8 页脚注也多少承认了），只是换了优先级分布吗？结果当然很 impressive，但看起来只是对已知结构的小改动。[1] 这里有一个该结构的旧参考：http://e-maxx.ru/algo/treap ，Google 翻译效果不错，而且代码不翻译也能读。
rafael859查看英文原文
Correct me if I'm wrong, but isn't this the "standard" [1] treap with split/merge (which is somewhat acknowledged in the footnote of page 8), simply with a different distribution of priorities? The result is certainly impressive, but it seems like a small modification to an otherwise known structure. [1]: See here http://e-maxx.ru/algo/treap for an old reference of this structure. Google translate does a decent job with it, and the code is readable without translation.
质疑指出竞赛编程中的 treap 已有 zip/merge 操作，差别仅在 rank 分布。
带 zip/merge 修改操作的笛卡尔树（treap）是竞赛编程中众所周知的数据结构。与论文的唯一区别大概是 rank 选择算法——用均匀分布而非几何分布。不清楚作者是否知道这一点。
kilotaras查看英文原文
A Cartesian tree (treap) with zip/merge change routine is a well known datastructure in competitive programming. The only difference from the paper would be rank selection algorithm - uniform instead of geometric. Unclear if authors were aware of it.
支持赞赏其自顶向下、O(1) 期望重构和相对简单的更新。
论文指出插入和删除可以完全自顶向下完成，期望重构时间为 O(1)，昂贵重构的出现频率呈指数级下降。某些确定性平衡搜索树，特别是弱 AVL 树和红黑树，在摊还意义上达到这些界，但更新算法相当复杂。这是一个简洁新颖的数据结构，典型插入/删除时间为 O(1)。很酷！
mabbo查看英文原文
> insertion and deletion can be done purely top-down, with O(1) expected restructuring time and exponentially infrequent occurrences of expensive restructuring. Certain kinds of deterministic balanced search trees, in particular weak AVL trees and red-black trees achieve these bounds in the amortized sense [3], but at the cost of somewhat complicated update algorithms. It's a neat, novel data structure with O(1) typical insert and delete times. Very cool!
补充补充手机可读的论文 HTML 版本链接。
如果你在用手机，这里是论文的 HTML 版：https://www.arxiv-vanity.com/papers/1806.06726/
bfirsh查看英文原文
If you’re on a phone, here’s an HTML version of the paper https://www.arxiv-vanity.com/papers/1806.06726/
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
历次讨论
- 2018Hacker News 讨论帖301 分 · 36 评
同领域还值得读
哲学家为何应关注计算复杂性
Why Philosophers Should Care About Computational Complexity (2011)
Scott Aaronson 的这篇长文论证计算复杂性理论（如 P vs NP、停机问题的复杂度视角）对哲学问题（如知识的本质、中文房间、水槽论证等）具有实质意义，而不仅是技术细…
算法与理论计算机2015 · 552 分 · 120 评进阶 · 约 90 分钟编辑精选通信的数学理论
A Mathematical Theory of Communication
是香农1948年的《通信的数学理论》，为通信建立数学框架：把信息量定义为不确定性或自由度（信息熵），并讨论信源编码、信道容量与可靠传输。
算法与理论计算机2020 · 495 分 · 91 评进阶 · 约 120 分钟编辑精选物理、拓扑、逻辑与计算：罗塞塔石碑
Physics, Topology, Logic and Computation: A Rosetta Stone (2009)
用范畴论充当“罗塞塔石碑”，试图在量子物理、拓扑、逻辑与计算四个领域之间建立统一的结构性类比：物理中的量子过程、拓扑中的配边、逻辑中的证明和计算中的程序，都可被视为某类范畴中的态…
算法与理论计算机2009 · 390 分 · 55 评 · 引用 13专业 · 约 180 分钟编辑精选一种快速、极小内存的一致性哈希算法
A Fast, Minimal Memory, Consistent Hash Algorithm
论文给出一种快速、省内存的一致哈希方案，目标是在桶数量变化时保持较小的键迁移成本，同时降低计算和内存开销。
算法与理论计算机2014 · 327 分 · 57 评 · 引用 4进阶 · 约 25 分钟编辑精选第五个 Busy Beaver 值的确定
Determination of the fifth Busy Beaver value
宣布确定了第五个 Busy Beaver 值 BB(5)：即 5 状态图灵机中停机前运行步数最多的机器（Champion）在 47,176,870 步后停机。
算法与理论计算机2025 · 288 分 · 116 评 · 引用 1专业 · 约 75 分钟编辑精选