Treap又叫树堆属于一种自平衡二叉搜索树是由单词Tree和Heap构成是一种具有二叉搜索树和堆两种数据结构的特性。

在前面我们讲过《笛卡尔树》它也是一种具有二叉搜索树和堆的两种数据结构的特性关于它俩的区别我们后面在介绍。

我们知道如果随机使用一组数据创建二叉搜索树则二叉搜索树很可能会退化成一个链表增加了操作的时间复杂度。

这个时候我们可以给每个节点随机生成一个优先级这个优先级要满足堆的特性。

因为是随机生成的所以从概率上来说退化成链表的可能性就非常小。

Treap在节点插入和删除的时候也会进行旋转因为它不是高度平衡的所以Treap比我们前面讲的《AVL树》要简单很多在讲解之前我们先来看下Treap的节点类。

Java

节点优先级priority满足堆的特性随机生成的TreapNode(int

key)

节点类中有一个优先级priority它是随机生成的要满足堆的特性这里我们使用最大堆堆顶元素是优先级最高的。

再来看下节点的旋转旋转不会改变二叉搜索树的特性但会改变堆的特性旋转的目的就是把优先级高的节点往上调整优先级低的节点往下调整这和我们前面讲的《数据结构堆》类似不过在堆中是直接交换不是通过旋转。