百大专升本

　　Treap本质上也是一颗BST(平衡二叉搜索树)，和我们之前介绍的SBT是一样的。但是Treap维持平衡的方法和SBT不太一样，有些许区别，相比来说呢，Treap的原理还要再简单一些，所以之前在竞赛当中不允许使用STL的时候，我们通常都会手写一棵Treap来代替。

　　在Treap当中，维护平衡非常简单，只有一句话，就是通过维护小顶堆的形式来维持树的平衡。Treap也正是因此得名，因为它是Tree和Heap的结合体。

　　之所以要增加这个priority属性是为了维护它堆的性质，通过维护这个堆的性质来保持树的平衡。具体的操作方法，请往下看。

　　首先来讲Treap的插入元素的操作，其实插入元素的操作非常简单，就是普通BST插入元素的操作。唯一的问题是如何维持树的平衡。

　　我们前文说了，我们是通过维持堆的性质来保持平衡的，那么自然又会有一个新的问题。为什么维持堆的性质可以保证平衡呢?

　　答案很简单，因为我们在插入的时候，需要对每一个插入的Node随机附上一个priority。堆就是用来维护这个priority的，保证树根一定拥有最小的priority。正是由于这个priority是随机的，我们可以保证整棵树蜕化成线性的概率降到无穷低。

　　当我们插入元素之后发现破坏了堆的性质，那么我们需要通过旋转操作来维护。举个简单的例子，在下图当中，如果B节点的priority比D要小，为了保证堆的性质，需要将B和D进行互换。由于直接互换会破坏BST的性质，所以我们采取旋转的操作。

　　旋转之后我们发现B和D互换了位置，并且旋转之后的A和E的priority都是大于D的，所以旋转之后我们整棵树依然维持了性质。

　　右旋的情况也是一样的，汉奈电气(上海)有限公司第一分公司，其实我们观察一下会发现，要交换左孩子和父亲需要右旋，如果是要交换右孩子和父亲，则需要左旋。

　　前面的逻辑就是BST的插入，也就是和当前节点比大小，决定插入在左边还是右边。注意一下，这里我们在插入完成之后，增加了maintain的逻辑，其实也就是比较一下，刚刚进行的插入是否破坏了堆的性质。可能有些同学要问我了，这里为什么只maintain了一次?有可能插入的priority非常小，需要一直旋转到树根不是吗?

　　的确如此，但是不要忘了，我们这里的maintain逻辑并非只调用一次。随着整个递归的回溯，在树上的每一层它其实都会执行一次maintain逻辑。所以是可以保证从插入的地方一直维护到树根的。

　　删除的操作稍微麻烦了一些，由于涉及到了优先级的维护，不过逻辑也不难理解，只需要牢记需要保证堆的性质即可。

　　首先，有两种情况非常简单，一种是要删除的节点是叶子节点，这个都很容易想明白，删除它不会影响任何其他节点，直接删除即可。第二种情况是链节点，也就是说它只有一个孩子，那么删除它也不会引起变化，只需要将它的孩子过继给它的父亲，整个堆和BST的性质也不会受到影响。

　　对于这两种情况之外，我们就没办法直接删除了，因为必然会影响堆的性质。这里有一个很巧妙的做法，就是可以先将要删除的节点旋转，将它旋转成叶子节点或者是链节点，再进行删除。

　　我们也贴一下旋转操作的代码，其实这里的逻辑和之前SBT当中介绍的旋转操作是一样的，代码也基本相同：

　　这里唯一要注意的是，旅游书报/杂志/音像，由于Python当中存储的都是引用，所以我们在旋转操作之后必须要重新覆盖一下父节点当中当中的值才会生效。负责我们修改了node的引用，但是father当中还是存储的旧的地址，一样没有生效。

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

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

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