一、树堆（Treap）和红黑树（RB-Tree）的优劣

Treap

优点: 插入删除简单直观，速度也不错，很好地平衡了编码复杂度和时间效率。

缺点:由于优先级(优先级是个堆)是随机生成的，所以只能保证它的插入和删除操作时间复杂度大概是log(n)，你不能保证它的一个操作一定能在很准确的时限内完成。

所以Treap常用于算法竞赛需要手动写BST的时候，尤其是扩展而来的Rank Tree (名次树，查询第k人的元素，set做不了)。

RB-Tree

优点: 保证平衡并且有平衡限制条件，操作有准确时限，插入删除操作比AVL Tree快.

缺点: 太复杂，插入有5种情况，删除有6种情况，代码量大，编写容易出错。

所以RB-Tree用于大部分语言的set的实现，实时系统等。

延伸阅读：

二、树堆实现平衡树的特点

普通的BST具有很强的不确定性，如果数据特殊，建树的时候可能直接变成一条链。不仅如此，插入删除的时候也很麻烦。因为如果插入或者删除，整个树原来的结构就会被打乱，这会为遍历和查找带来灾难性的后果。

所以我们推出了平衡树。就是通过将树旋转来动态维护这个树形态是平衡的，这样查找的复杂度就是O(log)级别的，是一种稳定的复杂度。

树堆是一种平衡树，它通过为键值（也就是我们需要维护成BST的）赋予优先级，使之也满足堆结构来进行旋转，成为一棵平衡树。

但是我们需要注意一点：树堆的优先级是随机赋予的。也就是说，这个数据结构其实是一个随机化的数据结构。这不是树堆的缺点，因为只有随机化赋予优先级，才有可能保证树堆的复杂度是O(log)的级别。那么，上述性质也说明了，树堆并不是一个规则形态的二叉树，更不是堆需要满足的完全二叉树。甚至它也不符合平衡树的定义：每个节点左右子树高度相差≤1，所以我们说树堆是近似实现平衡。但是通过形态定义二叉树的方式并不绝对。我们换一种方式来对平衡树进行定义：能够保证时间复杂度的BST，就是平衡树。

上一篇

系统开发项目实施怎么写?

下一篇

C无锁(lockfree)数据结构与有锁数据结构相比，速度，性能等有何区别?