Treap是一棵拥有键值、优先级两种权值的树 

1.唯一性

2.期望的插入、删除、查找的时间复杂度都是O(log n)

3.插入

                                              （灰色为先前位置）

　　旋转代码

void rotate(node* &o,int d){      //d=0，左旋;d=1，右旋
    node *k=o->son[d^1];          //d^1与1-d等价，但是更快
    o->son[d^1]=k->son[d];        //图中的x
    k->son[d]=o;    
    o=k;                          //返回新的根
}

 4.删除

　　调整至叶子结点后直接删除

5.分裂与合并问题

6.Treap与名次树问题

　　例题：hdu4585 "Shaolin"

　　题解地址：https://www.cnblogs.com/ynzhang2020/p/15071130.html

二叉树系列之Treap树