学习Treap

其实很久以前就有写这样一篇文章的想法，由于时间问题没有实现。停课集训马上就要开始，时间稍稍充裕，终于有机会写本文。本文不打算介绍Treap的各种细节，你可以在这里找到详细的教程。而本文仅仅列出一个大纲，以日记的方式简单地介绍Treap，作为自己的一个备忘，也希望能给初学者提供一个参考。

Treap=Tree+Heap。Treap本身是一棵二叉搜索树，它的左子树和右子树也分别是一个Treap，和一般的二叉搜索树不同的是，Treap纪录一个额外的数据，就是优先级。Treap在以关键码构成二叉搜索树的同时，还满足堆的性质(在这里我们假设节点的优先级大于该节点的孩子的优先级)。

如果您是一个初学者，在读下面的文字的时候，请同时参阅NOCOW上的Treap介绍。

简单的说，Treap通过给予每个节点一个附加的随机优先级，在保证Treap数据域的排序二叉树性质的前提下，使节点的优先级同时满足堆的性质。经过种种的分析证明，在一般情况下这样做可以让Treap维持平衡。
阅读更多

省选集训Day2

二月3日，徐持衡老师上课的第二天……

早上还是考试，3题4小时，一道数据结构，一道DP，一道图论。数据结构不会写，朴素地骗分，DP和图论诡异地错掉了。

下午讲了SBT，Splay等。昨天讲的网络流和今天的平衡树，都是以前惧怕的东西，发现今天来写轻松了多。我感觉考完高一的联赛后就基本没掌握什么新知识了，实际还是有一点点进步的。

由于还是不能理解SBT，我还是写Treap好了……实现起来真的比较轻松啊，但是删除还是不怎么熟练，省选将近，要赶快复习才是。

发现玩校内网的人很多，在那加的几位大牛，也在这个Blog上留下了足迹。谢谢啦！大牛们要教教我这个fresh fish啊:-)

今天就不贴巨丑的代码了，热烈欢迎访问本页的大牛，感谢在下面评论的大牛！