数据结构与算法：Treap树堆（Tree+Heap）详解

    Treap = Tree + Heap, 又称树堆， 它在满足二叉搜索树的同时又满足堆的性质。

    因为二叉搜索树，根据输入序列不同创建的树也不同，最坏的情况会退化为线性（只有左子树或右子树）。

    二叉搜素树的效率和树高成正比，因此在构建二叉搜索树时，尽可能地平衡左右子树，力求期望时间复杂度为 O(logn)。平衡地方法很多， AVL树，splay树，红黑树等，这些调平衡地方法相对复杂。

    如果一个二叉搜索树插入结点地顺序是随机的，得到的二叉搜索树大多情况下是平衡的，即使存在一些极端情况，但是这种情况发生的概率很小，因此以随机顺序创建的二叉搜索树，其期望高度是 O(log n) 。可以将输入数据随机打乱，再创建二叉搜索树，但是某些时候我们并不能事前得知所有待插入的结点， Treap 可以有效解决该问题。

    树堆也是一种平衡二叉搜索树，它给每个结点附加一个随机数值，使其满足堆的性质，而结点的值又满足二叉搜索树，其基本操作（增删改查）的期望时间复杂度 O(log n)。相对于其他的平衡二叉树， Trap 的特点是实现简单，且能基本实现随机平衡的结构。

    树堆的构建过程中，插入结点时会给每个结点附加一个随机数作为优先级，该优先级满足堆的性质（最大堆或最下堆均可，这里以最大堆为例，根的优先级大于左右孩子），数值满足二叉搜索树性质（中序有序，左子树大于根，右子树小于根）。

例如：输入 6 4 9 7 2构建的树堆，如图所示。

树堆是如何构建的呢？     调平衡：树堆需要两种旋转操作，右旋和左旋。

（1）右旋（zig）

    结点 p 右旋时，携带自己的右孩子，向右旋转到 q 的右子树位置， q 的右子树被挤掉，此时 p 右旋后左子树正好空闲，将 q 的游资是放在 p 的左子树，旋转后的树根为 q 。

（2）左旋（zag）

    结点 p 左旋时，携带自己的孩子，向左旋转到 q 的左子树位置， q 的左子树被挤掉抛弃，此时 p 左旋后右子树正好空闲，将 q 的左子树放在 p 的右子树，旋转后的树根为 q 。

总结：无论是右旋还是左旋，旋转后，总有一个孩子被抛弃，一个指针空闲，正好配对。

（3）插入

    树堆的插入操作，和二叉搜索树一样首先根据有序性找到插入位置，然后创建新结点插入； 创建新结点时，会给该结点附加一个随机数作为优先级，自底向上检查该优先级是否满足堆性质，如果不满足则需要右旋或左旋，使其满足堆性质。

算法步骤：

回退操作/回溯：在递归调用的下面，写回退程序。上面代码就是在递归调用结束后，回退时进行旋转操作。

（4）删除

    树堆的删除操作非常简单，首先找到待删除的结点，然后将其向优先级大的孩子旋转，一直旋转到叶子，直接删除叶子即可。

性能分析：

    由于树堆引入了随机性，构建的树堆是一种平衡二叉树，其查找，插入，删除，求前驱和后继的时间复杂度均为 O(log n)。