Treap――堆和二叉树的完美结合，性价比极值的搜索树

基本上到这里整个Treap的原理就介绍完了，当然除了我们刚才介绍的基本操作之外，Treap还有一些其他的操作。比如可以split成两个Treap，也可以由两个Treap合并成一个。还可以查找第K大的元素，等等。这些额外的操作，我用得也不多，就不多介绍了，大家感兴趣可以去了解一下。

Treap这个数据结构在实际当中几乎没有用到过，一般还是以竞赛场景为主，我们学习它主要就是为了提升和锻炼我们的数据结构能力以及代码实现能力。Treap它的最大优点就是实现简单，没有太多复杂的操作，但是我们前面也说了，它是通过随机的priority来控制树的平衡的，那么它显然无法做到完美平衡，只能做到不落入最坏的情况，但是无法保证可以进入最好的情况。不过对于二叉树来说，树深的一点差距相差并不大。所以Treap的性能倒也没有那么差劲，属于一个性价比非常高的数据结构。

最后，还是老规矩，我把完整的代码放在了paste当中，大家感兴趣可以点击阅读原文查看，代码里都有详细的注释，大家应该都能看明白。

本文转载自微信公众号「 TechFlow」  

（编辑：核心网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!