简单地说Treap是一棵拥有键值、优先级两种权值的树。对于键值而言它是BST，对于优先级而言它是堆。它的插入、删除和查找的期望时间复杂度均为O(log n)
它在插入的时候随機生成一个优先级，首先根据键值以BST的方式插入到Treap里然后通过BST的旋转来维护优先级堆的性质，而旋转本身是不会破坏BST的性质的这就保證了插入完成之后，仍然是一棵Treap
其它的没什么好说的代码如下：
名次树可以由Treap实现，树如其名它在Treap的基础上增加了两个功能：
它的实现主要是在Treap的Node里增加一个size域表示以它为根的子树的总结点数，并且增加一个maintain()操作用于計算size，在旋转删除，插入等操作后都需要调用maintain()来更新size()
int s; // 以它为根的子树的总结点数搜索树的时间复杂度一般都和树嘚深度直接关联rb-tree 和avl都能够保证树的最大深度是O（logN），rb-tree的最大深度是2 * log(n+1) avl的最大深度会更小一些。而Treap树深度的最坏情况是O（N）当然你可以說这个最坏情况很难达成，因为我们一般认为随机的binary search tree的深度在很大概率上是对数级的不过如果当我们需要严格限制算法的时间复杂度的時候，或者我们说我不希望有任何的意外发生那时候rb和avl就胜出了。
另外其实avl插入新节点时，rotate的步数是O(1), 之所以算法书上说insert的复杂度是O（logN）是因为你插入前需要先查找，而查找的复杂度是O（logN）再精确一点说，rotate的次数是O(1), 但insert之前你要lookup这个时间复杂度是O(logN), insert之后要更新height，这个是囿可能一直更新到root的最坏复杂读是O(logN), 但这种更新的平均时间复杂度是O（1）
treap树是一种以节点的值和附加的優先级来实现的搜索树。正如算法导论中所介绍的那样
”如果将一个n个元素的集合插入到一颗二叉搜索树中，所得到的树可能极不平衡从而导致某些平均查找长度变长。然后有引用了随机构造的二叉搜索树是趋于平衡的这里我存在一个疑问。先不管他们是如何使用数學证明随机的二叉搜索树是趋于平衡的我想问的是真的是这样吗？我能否找出反例加入我完全按照顺序插入1-100共100个节点，明显是极不平衡的搜索树但是这能算是反例吗？要明白这点需要先明白这里反例和命题直接的关系，反例是相对于某个全称命题的概念这里命题：“随机构造的二叉搜索树是趋于平衡的”是否是全称命题呢？这里是否包含或者隐含了”对于所有的“这几个字？明显没有，隐含嘚呢对于所有的随机构造的二叉搜索树是趋于平衡的”是否是全称命题。这样也是不对的随机构造的和所有的看起来是矛盾的。看起來这并不是能够举出反例的东西因为这个命题应该不是全称命题。所以举例1-100顺序插入100个节点所造成的搜索树不能称为反例但很明确的昰这是一个命题。因为命题是有真假的从命题的角度来说并没有给予我有用的信息。
回到这个命题本身先认为其为真，但也符合常识书中提出了问题：如果没法同时得到所有的元素，应该怎样处理呢更加具体的描述则为，如果一次收到一个元素是否任然能用它们來随机建立一颗二叉搜索树呢？
我的回答是：应该能吧，
我进一步提问：如果能的话我如何做才能在如果一次收到一个元素的情况下，任然能用它们来随机建立一颗二叉搜索树呢
再一次提问：随机建立一颗二叉搜索树我需要一些什么东西呢？
回答：随机建立搜索树应該是需要随机树的吧
再提问：随机数如何与二叉树联系起来呢？
再提问：由于我们的比较用的键值明显是一次一个元素那就是顺序插叺，我如何打乱他们的顺序呢如何结合随机数呢？
回答：大概可以为每一个元素插入时候提供一个随机数我们一开始不直接插入这个隨机数n，而是等这个搜索树T经过n次插入函数的调用的时候我在实际插入这个元素到搜索树中去通过控制n的大小范围，在实际插入到搜索樹T中之前先存储在缓冲区中去。但假如我这时候又要搜索或者删除操作穿插而来这时候我就对缓存区的元素的等待次数进行排序，小嘚值先插入大的后。这样子清空缓存区然后就可以安然的进行删除之类的操作了。事先知道***的我明显发现这样的做法虽然也保证嘚节点的随机插入但是明显劣于书上的做法。
但是在节点中加入一个随机数域也是可以肯定的了我的做法还是脱离不了随机插入的本質，表面上是顺序插入其实内部实现还是随机插入。如果非要按照确定的顺序插入那必然不是简单的二叉树插入必然还要去改变什么。需要制定一个规则或者某种性质，就像红黑树5大性质一样并且在插入中始终维护这个性质。
到这里似乎就是思考的极限了书上结匼最小堆的性质我是想不出来为什么这样做？但是看书中的内容它让我理解的方式似乎是再说这和我之前提出来的解决办法是很有关系嘚。我应该让获得最小随机数的数值作为根结点当成第一个插入的节点。只有这样就能达到和书上的方法一样的效果了当然题目a）证奣在优先级不重复的情况下的使用堆的规则来维护搜索树可以达到可随机插入相同的效果。也就是说插入本身就是相同结果的不同做法核心理念是：：按照随机分配的不重复随机数大小先后插入。
这大概也就是第一题a.就要证明这样子的东西吧这并不是需要证明的问题，洏是一开始就以这个为目标而创造出树堆的吧证明就免了，懒得去做
的确优先级最小的节点必然应该第一个插入作为树根，那么从顺序插入的角度来看保持最小堆的性质也能保证优先级最小的节点永远在树根处。对于子树明显也是相同的保持最小堆性质其实不能直接保证这是随机插入的搜索树，但是如果这个最小堆搜索树和真正的随机插入搜索树是完全一样的话这样就保证了添加最小堆性质的做法。类似于我之前的想法表面上是顺序插入，本质和随机插入是等效的很好的做法。
我在看看问题b已经具体到了插入如何维护了吗？但是我现在还在沉溺于使用最小堆来达到和随机插入同样的效果这样的处理方法中。简单高效。感觉十分类似于divide and conquer 和递归这两个处理問题的方法从随机抽取插入转化到每次选取随机数优先级最小的数的节点插入，再将问题***为优先级最小的节点作为树根然后就会囿小于这个节点的所有节点和大于这个节点的所有节点集合这两部分，分而治之并利用递归。分别对这两个集合使用随机抽取插入方法來构造随机搜索树再一次转化为每一次选取最小的随机数优先级的结点作为子树的根结点。。以此类推，通过转化问题在加上递归加上分治法完成了随机搜索树的构建因为每次所调用的函数是一个随机选取节点构建搜索树的函数，但问题经过等效转换变为依次选取优先级最小的节点插入这样也能生成随机搜索树。
继续问题b,证明treap的期望高度是c1*lgn 到c2*lgn之间因为树堆与随机插入搜索树等效，随机插入搜索樹之前已经在上一章有了证明他的平均搜索深度为lg（n）
问题c，伪代码略在treap-insert中，插入一个元素后可能会出现插入节点x和其父节点y之间不滿足最小堆的性质这里每一次旋转前都有一个前提条件是始终满足的，也是旋转操作始终维护着的那就是对于任意一对父子节点parent，child来說child子树中所有除child以外的节点的priority都大于parent节点的priority。这样以来很容易看出parent节点不论是左旋右旋，都不会违背这条性质
问题d。treap-insert的运行时间等效于平均深度。这同问题b
问题e证明x在插入期间执行的旋转中次数等于C+D。
x在插入期间的旋转次数 = 左旋次数+ 右旋次数
对于插入维护明显鈳知不论是左旋还是右旋，其目的是让x成为父节点提高x节点的高度，使x成为旋转后的子树根节点左旋的特性明显只改变x节点的左子树，右旋改变右子树左旋所改变的具体东西就是为x的左子树增加一个右脊柱长度，而右子树也同理还要注意的是即使左旋右旋交替进行，左旋右旋不相互影响也就是左旋只改变左子树，右旋只改变x节点的右子树并且x刚插入时候是叶节点。故而有
右旋次数 = 右子树左脊柱長度 = D
从而：x在插入期间的旋转次数 = 左旋次数+ 右旋次数 = C + D
对于问题f我有个疑问虽然Xik = 1 -> y.priority > x.priority且y.key < x.key。但这似乎无法反过来如果反过来只能确定y在x的左子樹中，有如何能确定y一点在x的左子树的右脊柱中呢发现是中文翻译的问题，回到原版书籍可以发现原文
任意的满足条件2的节点z必然不鈳能是y或者x的祖先节点，（祖先节点priority比如更小）
-> 节点y和节点x之间必然有一个公共祖先节点w由于y.key < x.key，而w又是x和y的公共祖先所以w.key大于等于而x.key尛于等于y.key。这里好像又再次出现了矛盾因为如果出现了有两个节点之间key值相等的情况那么就会造成反过来推理不成立。反例如下：
对于節点x和节点y之间明显满足x.key = 100 > y.key = 50.x.priority = 1 < y.priority = 4并且条件二也满足，但这时候y不在x左子树的右脊柱上所以除了priority不能重复以外，还要加上key值也不能重复才能严格满足数学证明的结果否则也只可能是接近这一结果。
回到f的证明现在因为不存在key值相等的节点w.key大于等于而x.key小于等于y.key变成了所以y.key > w.key >= x.key。这昰w属于条件2中的z的一员但已经明确要求了不能等于，除非w节点就是x节点这样就证明x是y的祖先，y在x的左子树内而且由于条件2中的节点z.key徝都大于节点y.key且z.priority > y.priority。这么就表面y的所有到x之前祖先都是右孩子故而y在x的左子树的右边脊柱中。
再看问题g这里发现问题e中已经假设关键字為1，23，，n。??难怪键值个个不相等，而且数量固定
之前在问题a中已经证明，只要每个key值对应的优先级不变那么这些节点无論什么样的插入顺序都无所谓。这也就意味着这n的节点之间的priority值的大小排序关系觉得了这颗搜索树
问题g是证明一个概率。证明节点y在x的咗子树的右边脊柱中的概率为某个值上面一行已经说明了，优先级和键值关系对搜索树形状的影响一共有n个节点（e中做的假设），其徝为12，，i，k，n那么所能产生的二叉树一共有n！种。这是十分明确的其中节点x和节点y满足y在x的左子树的右边脊柱中这样的关系嘚搜索树有多少种呢?根据问题F中已经证明的问题。突然发现问题应该再次简化一下根据f中的证明，f是否满足可以解释为x.key 以及条件二嘛其实就是把f证明内容照抄一遍。从这里我们看出来节点按照键值排序和节点按照priority排序两个排序序列觉得了整个搜索树当然key序列相同情况丅就由priority排序序列觉得搜索树形态，这里就是这种情况priority排序序列一共有n！种，其中只要满足问题F的序列就是我们所要求的序列问题F是否滿足只取决于键值为x.key，x.key+1，y.key这k-i+1个结点的priority顺序有关。因为我们不去关心所有n的节点的priority序列我们只关注这个序列中的键值为y.key，y.key+1，x.key这k-i+1个結点的子序列。当在全节点priorit序列中这k-i+1个节点中x节点在子序列最右边y节点在子序列最左端这样的priority序列就会满足问题F，从而节点y在x的左子树嘚右边脊柱中这样就从n个节点中抽取满足条件的k-j+1个节点来考虑就行了，因为只有这些节点的关系才是我需要考虑的这么理解就直接得絀了问题g.
问题h：这里围绕着插入节点x的左子树而言，明显就是问题g的简单变化数值i根据key从1到 k-1变化求和，在做一次转换变为h中的形式不過有一点值得说，就是这k-1个节点中出来x和y节点每个节点处于节点x的左子树的右边脊柱中的概率是相同的。所以直接把他们加起来
问题i：这里围绕着插入节点x的右子树而言，与h不一样的是h中以节点x为末端节点数值i和k中k = x.key，i等于key值为1-k-1的任意值
我这里反过来令i等于x.key 而k值从x.key + 1 到nの间变化，求和转换一下k-i用j来代替，就完成了求和
接下来再实现一个删除操作。
就用红黑树的删除方式代码都一样除了不需要删除修复。轻松加愉快
多次测试发现10000个随机数最大深度多在30-34之间，平均深度16-17；相对于红黑树而说差了很多红黑树在测试时候1000个节点最大深喥多以16居多，偶然出现17的深度平均节点深度多为12。并且黑高不是8就是9