【treap】
treap：http://dongxicheng.org/structure/treap/（似乎文中理解的旋转方向不太一样，我一般认为左旋即把右节点旋上去）
因为第一次理解旋转，详细写一下树的旋转过程，下面以右旋为例。
void rturn(int &t)
{
int k=tree[t].l;
tree[t].l=tree[k].r;//让旋转后的右节点t承接原左节点k的右子树作为新左子树，同时解除k作为左节点对于t的隶属关系。
tree[k].r=t;//将k的右节点置为t(原k的右节点已送出)。
t=k;//赋新根便于返回。
}
右旋就是将左节点旋上去作为新根。
原根t，新根k(原根t的左节点)
本质就是原根t的左节点解放出k并更新为k的右节点。
解放出来的k的右节点更新为原根t，k本身不再隶属其它节点而是作为新根。
真正动到的节点：t的左节点(解放出k)，k的右节点(存放t)，而原k的右节点变成了t的左节点(替换过去)。
---
由于插入是从根进入的，应该可以保证左子树所有值均小于根节点，右子树所有值均大于根节点。
其它的上面给的博客链接已经说得很清楚了，可以结合代码去看。
【算法】数据结构
原文：http://www.cnblogs.com/onioncyc/p/6617685.html
