Treap：二叉搜索树与堆的奇妙融合

Treap (Cartesian Tree)

Treap（Cartesian Tree）是一种将二叉搜索树与二叉堆特性完美结合的数据结构。它通过为每个节点分配随机优先级，确保树在平均情况下保持平衡，从而将插入、查找和删除等操作的时间复杂度稳定在 O(log n)。文章详细介绍了Treap的核心优势，包括如何通过Split和Merge两个基础操作高效实现插入、删除、合并及交集等复杂功能。此外，还展示了如何维护子树大小以支持查找第K大元素等高级操作，并提供了清晰的C++实现代码。对于算法竞赛和数据结构爱好者而言，Treap不仅是一个强大的工具，更是理解随机化算法思想的绝佳案例。