数据结构之treap
这篇从二叉搜索树在极端情况下可能退化成链表、失去效率优势的经典问题出发，引出了一个巧妙的设计：treap。它名字本身就是“树”与“堆”的合体，其核心思想是在每个节点上附加一个随机生成的优先级。通过维护“按关键值排序是一棵二叉搜索树，同时按优先级排列又是一个大顶堆”这两个性质，它用概率避免了树的不平衡问题。 文章解释了这种混合结构的妙处：当进行插入或删除操作时，treap会通过旋转来同时维护这两个性质，而随机的优先级使得树的结构在期望意义上保持平衡。相比严格的平衡树（如红黑树）实现更简单，相比普通BST又能保证较好的性能。对于需要频繁动态插入和删除，同时希望实现相对简洁、避免最坏情况的场景，treap是一个很有吸引力的折中方案。