数据结构与算法： 树堆
之前我们讲到 二叉搜索树 ，从二叉搜索树到 2-3树 到 红黑树 到 B-树。
二叉搜索树的主要问题就是其结构与数据相关，树的深度可能会很大，Treap 树就是一种解决二叉搜索树可能深度过大的另一种数据结构。
Treap的定义
Treap=Tree+Heap 树堆（Treap）是二叉排序树（Binary Sort Tree）与堆（Heap）结合产生的一种拥有堆性质的二叉排序树。
Treap每个节点记录两个数据，一个是键值，一个是 随机 附加的优先级，Treap在以关键码构成二叉排序树的同时，又以结点优先级形成最大堆和最小堆。所以Treap必须满足这两个性质，一是二叉排序树的性质，二是堆的性质。Treap是由一个随机附加域满足堆的性质的二叉搜索树，其结构相当于以随机数据插入的二叉搜索树。相对于其他的平衡二叉搜索树，Treap的特点是实现简单，且能基本实现随机平衡的结构。Treap维护堆性质的方法只用到了旋转，只需要两种旋转，编程复杂度比Splay要小一些。
但是这里要注意两点:
- 二叉堆必须是完全二叉树，而Treap并不一定是；
- Treap并不严格满足平衡二叉排序树（AVL树）的要求，即树堆中每个节点的左右子树高度之差的绝对值可能会超过1，只是近似满足平衡二叉排序树的性质。
1
2
3
4
5
10(1)
/ \
8(10) 14(5)
/ / \
6(12) 12(7) 16(8)
Treap的操作
插入
给节点随机分配一个优先级，先和二叉排序树（又叫二叉搜索树）的插入一样，先把要插入的点插入到一个叶子上，然后再维护堆的性质。
以最小堆为例，如果当前节点的优先级比其根节点小就旋转。如果当前节点是根的左子节点就右旋。如果当前节点是根的右子节点就左旋。 即左旋能使根节点转移到左边，右旋能使根节点转移到右边。
如下为一颗树堆，同时满足二叉搜索树和堆的性质，其中括号中为节点的优先级
1
2
3
4
5
3(1)
/ \
2(10) 5(5)
/ / \
1(12) 4(7) 6(8)
新插入的节点4优先级为 1, 由于 4 是根的左子节点，此处右旋
1
2
3
4
5
5(5) 4(1)
/ \ 右旋 \
4(1) 6(8) ==> 5(5)
↑ \
6(8)
新插入节点 6 优先级为 1, 由于 其为 5 的右子节点，此处左旋
1
2
3
4
5
5(5) 6(1)
/ \ 左旋 /
4(7) 6(1) ==> 5(5)
↑ /
4(7)
由于旋转是O(1)的，最多进行h次(h是树的高度)，插入的复杂度是 O(h) 的，在期望情况下 h=O(log n)，所以它的期望复杂度是 O(log n)。
下面来看一个完整的插入过程,如下是一颗树堆，还是在括号中表示优先级
1
2
3
4
5
6
7
8
7(4)
/ \
2(7) 8(5)
/ \ \
1(10) 5(23) 11(65)
/
9(73)
插入 3 随机优先级假设为 25, 先按照二叉查找树插入作为 5的子节点，在根据堆的性质判断优先级是否满足小根堆的条件。满足则不做任何操作
1
2
3
4
5
6
7
8
7(4)
/ \
2(7) 8(5)
/ \ \
1(10) 5(23) 11(65)
/ /
3(25) 9(73)
插入 4 随机优先级假设为 9。
1
2
3
4
5
6
7
8
9
10
7(4) 7(4) 7(4)
/ \ / \ / \
2(7) 8(5) 2(7) 8(5) 2(7) 8(5)
/ \ \ / \ \ / \ \
1(10) 5(23) 11(65) ==> 左旋 1(10) 5(23) 11(65) 1(10) 4(9) 11(65)
/ / / / / \ /
3(25) 9(73) 4(9) 9(73) 3(25) 5(23) 9(73)
\ /
4(9) 3(25)
(a) (b) (c)
先按照二叉查找树插入作为 3的子节点（a）。再根据堆的性质判断优先级是否满足小根堆的条件。由于优先级 9 < 25，所以需要将节点左旋来满足小根堆条件变成 (b);旋转后，发现 4的优先级 9 依然小于其父节点 5 的优先级 23。此时右旋,变成 (c)。此时同时满足二叉查询树性质，且满足小根对条件
在插入 6 假设优先级为 2，使用相同方式得到如下结果, 从结果中可以看到，调整完成后，不是完全二叉树，也不是平衡二叉树。
1
2
3
4
5
6
7
8
9
6(2)
/ \
2(7) 7(4)
/ \ \
1(10) 4(9) 8(5)
/ \ \
3(25) 5(23) 11(65)
/
9(73)
删除
删除一个节点有两种方式，可以像删除二叉树节点那样删除一个节点，也可以像删除堆中节点那样删除。
用二叉搜索树的方式删除
先在二叉查找树中找到要删除的节点的位置,然后根据节点分以下情况:
-
情况一: 该节点是
叶节点(没有非空子节 点的节点),直接把节点删除即可。 -
情况二：该节点是
链节点(只有一个非空子节点的节点),为了删除这个节点而不影响它的子树,需要把它的子节点代替它的位置,然后把它删除。 -
情况三：该节点有
两个非空子节点。由于情况比较复杂,一般的策略是用它右子树的最小值来代替它,然后把它删除。
如下所示,删除节点 2 时,在它的右子树中找到最小的节点3, 该节点一定为待删除节点的后继。删除节点 3 (它可能是叶节点或者链节点),然后把节点2的值改为3。（当然，我们也可以使用结点的左子树的最大值来替代它，为了不使Treap向一边偏沉,我们可以随机地选取是用后继还是前驱代替它, 并保证两种选择的概率均等。）
1
2
3
4
5
6
7
8
9
6 6
/ \ / \
2 7 3 7
/ \ / \
1 5 1 5
/ /
3 4
\
4
注意:
- 删除节点
2, 并用节点3替换其值的时候，只是替换了值，节点2原来的优先级没有发生变化，所以删除后不需要重新根据堆属性进行调整 - 节点
2的后继节点为其右子树中的最小值(同时也是最左边的值)，因此其只可能是叶子节点或者只有一个右子节点的链节点。
用堆的方式删除
因为Treap满足堆性质，所以只需要把要删除的节点旋转到叶节点上，然后直接删除就可以了。具体的方法：
-
如果该节点的左子节点的优先级小于右子节点的优先级，右旋该节点。使该节点降为右子树的根节点，然后访问右子树的根节点,继续操作；
-
反之，左旋该节点,使该节点降为左子树的根节点，然后访问左子树的根节点，继续操作，直到变成可以直接删除的节点。（即：让小优先级的结点旋到上面，满足堆的性质）
如下所示，如果要删除节点 6:
1
2
3
4
5
6
7
8
9
10
2(10) 2(10) 2(10) 2(10)
/ \ / \ / \ / \
1(15) 6(12) <--- 1(15) 4(13) 1(15) 4(13) 1(15) 4(13)
/ \ / \ / \ / \
4(13) 7(15) 3(40) 6(12) 3(40) 7(15) 3(40) 7(15)
/ \ \ / \ / \ / \
3(40) 5(19) 8(30) 5(19) 7(15) 6(12) 8(30) 5(19) 8(30)
\ /
8(30) 5(19)
(a) (b) (c) (d)
a. 节点6有两个子节点，且左子节点优先级小于右子节点，右旋。
b. 旋转后 6 仍然有两个子节点，右子节点优先级比较小，左旋。
c. 此时 6 只有一个子节点，可以直接删除然后用左子节点替代它本身。
删除最多进行O(h)次旋转，期望复杂度是O(logn)。
查找
根据Treap具有二叉搜索树的性质，可以快速查找所需节点。 时间复杂度： 期望复杂度是O(log n)。
元素排名与根据排名找元素
求“某个元素的排名”，基本思想是查找目标元素在 Treap 中的位置,且在查找路径中统计出小于目标元素的节点的总个数,目标元素的排名就是 总个数+1。即：在查找的路径中统计小于目标元素的个数，当找到目标元素后加上其左子树的个数即可。
Treap 是一种排序的数据结构,如果我们想查找第 k 小的元素或者询问某个元素在 Treap 中从小到大的排名时,我们就必须知道每个子树中节点的个数。维护了子树的大小，我们就可以求“排名第k的元素”这样的问题了。快排也能求“第k大”问题，但是快排适合静态的数据，对于经常变动的数据，我们用树结构来维护更灵活。
由于插入、删除、旋转等操作,会使每个子树的大小改变,所以我们必须对子树的大小进行动态的维护。
- 对于旋转,我们要在旋转后对子节点和根节点分别重新计算其子树的大小。
- 对于插入,在寻找插入的位置时,每经过一个节点,都要先使以它为根的子树的大小增加 1,再递归进入子树查找。
- 对于删除,在寻找待删除节点,递归返回时要把所有的经过的节点的子树的大小减少 1。要注意的是,删除之前一定要保证待删除节点存在于 Treap 中。
对比 ??
Splay树
Splay 和 BST 一样,不需要维护任何附加域,比 Treap 在空间上有节约。但 Splay 在查找时也会调整结构,这使得 Splay 灵活性稍有欠缺。Splay 的查找插入删除等基本操作的时间复杂度为均摊 O(logN) 而非期望。可以故意构造出使 Splay 变得很慢的数据。
AVL和红黑树
AVL 和 红黑树 在调整的过程中,旋转都是均摊 O(1)的,而 Treap 要 O(logN)。与 Treap 的随机优先级不同,它们维护的附加域要动态的调整,而 Treap 的随机修正值一经生成不再改变,这一点使得灵活性不如 Treap。
AVL 和红黑树都是时间效率很高的经典算法,在许多专业的应用领域(如 STL)有着十分重要的地位。然而AVL和红黑树的编程实现的难度要比Treap大得多。
举个栗子
Treap 是一种高效的动态的数据容器,据此我们可以用它处理一些数据的动态统计问题。
游戏排名
[问题描述]
有一个游戏排名系统,通常要应付三种请求:上传一条新的得分记录、查询某个玩家的当前排名以及返回某个区段内的排名记录。当某个玩家上传自己最新的得分记录时,他原有的得 分记录会被删除。为了减轻服务器负担,在返回某个区段内的排名记录时,最多返回 10 条 记录。
[求]
- 更新玩家的得分记录
- 查询玩家排名（如果两个玩家的得分相同, 则先得到该得分的玩家排在前面。）
- 查询第 Index 名开始的最多 10 名玩家名字
[解]
因为作为字符串的姓名是不便于处理的,我们给每个玩家都制定一个ID,首先要建立一个由姓名到玩家ID的映射数据结构。为了查找快速,可以用 Trie树。之后我们建立一个双关键字的Treap,关键字 1 为得分从小到大,关键字 2 为时间戳从大到小,这种排列方式的逆序,恰好是我们要的顺序(也可以直接就是逆序)。
对于问题（1），先查询玩家是否已经存在,如果已经存在,在Treap中更新对应已经存在的记录。
对于问题（2），就是基本的求排名操作。
对于问题（3），就是分别查找第(总记录数 + 1 – k)小的记录。
双端优先队列的实现
优先队列(Priority Queue)是一种按优先级维护进出顺序的数据容器结构,可以选择维护实现取出最小值或最大值。我们通常用堆实现优先队列,通常取出最值的时间复杂度为 O(logN)。
用最小堆可以实现最小优先队列,用最大堆可以实现最大优先队列。但是如果我们要求一种 “双端优先队列”,即要求同时支持插入、取出最大值、取出最小值的操作,用一个单纯的堆就不能高效地实现了。（可以用两个堆来实现，两堆中的元素都互指，但维护两个堆比较复杂。）
我们可以方便地使用Treap实现双端优先队列,只需建立一个 Treap,分别写出取最大值和最小值的功能代码就可以了, 无需做任何修改。由于Treap平衡性不如堆完美,但期望时间仍是 O(logN)。更重要的是在实现的复杂程度上大大下降,而且便于其他操作的推广。所以,用 Treap 实现优先队列不失为一种便捷而又灵活的方法。
注： 这里用treap， 主要是由于treap具有二叉搜索树的优点，能快速查询出最大最小值，同时又有随机树来做平衡，避免了二叉搜索树可能出现退化为链表，效率降低的问题。
