1. 简述
同splay tree一样，treap也是一个平衡二叉树，但是Treap会纪录一个附加的数据信息，即优先。Treap在以关键码组成二叉搜索树的另外，还按优先来考虑堆的特性。因此，Treap=tree heap。这儿必须留意的是，Treap并并不是二叉堆，二叉堆务必是完全二叉树，而Treap能够并不一定是。
2. Treap操作过程
为了更好地使Treap 中的连接点另外考虑BST特性和最小堆特性，难以避免地要对其构造开展调节，调节方法被称作转动。在维护保养Treap 的全过程中，仅有二种转动，分别是左转动(通称左旋体)和右转动(通称左旋体)。
左旋体一个子树，会把它的根节点转动到根的左子树部位，另外根节点的右子连接点变成子树的根；左旋体一个子树，会把它的根节点转动到根的右子树部位，另外根节点的左子连接点变成子树的根。
struct Treap_Node
{
Treap_Node *left,*right; //连接点的上下子树的表针
int value,fix; //连接点的值和优先
};
void Treap_Left_Rotate(Treap_Node *&a) //左旋体 连接点表针一定要传送引入
{
Treap_Node *b=a->right;
a->right=b->left;
b->left=a;
a=b;
}
void Treap_Right_Rotate(Treap_Node *&a) //左旋体 连接点表针一定要传送引入
{
Treap_Node *b=a->left;
a->left=b->right;
b->right=a;
a=b;
}
3. Treap的实际操作
同别的树结构一样，treap的操作过程有：搜索，插进，删掉等。
3.1 搜索
同别的二叉树一样，treap的搜索全过程便是二分查找的全过程，复杂性为O(lg n)。
3.2 插进
在Treap 中插进原素，与在BST 中插入方法类似。最先寻找适合的插进部位，随后创建新的连接点，储存原素。可是要留意新的连接点会有一个优先特性，该值很有可能会毁坏堆序，因而我们要依据必须开展适当的转动。具体做法以下：
1. 从根节点逐渐插进；
2. 假如要插进的值不大于当今连接点的值，在当今连接点的左子树中插进，插进后假如左子连接点的优先低于当今连接点的优先，对当今连接点开展左旋体；
3. 假如要插进的值超过当今连接点的值，在当今连接点的右子树中插进，插进后假如右子连接点的优先低于当今连接点的优先，对当今连接点开展左旋体；
4. 假如当今连接点为空连接点，在这里创建新的连接点，该连接点的数值要插进的值，上下子树为空，插进取得成功。
Treap_Node *root;
void Treap_Insert(Treap_Node *&P,int value) //连接点表针一定要传送引入
{
if (!P) //寻找部位，创建连接点
{
P=new Treap_Node;
P->value=value;
P->fix=rand();//转化成任意的调整值
}
else if (value <= P->value)
{
Treap_Insert(P->left,r);
if (P->left->fix < P->fix)
Treap_Right_Rotate(P);//左子连接点调整值低于当今连接点调整值，左旋体当今连接点
}
else
{
Treap_Insert(P->right,r);
if (P->right->fix < P->fix)
Treap_Left_Rotate(P);//右子连接点调整值低于当今连接点调整值，左旋体当今连接点
}
}
3.3 删掉
与BST 一样，在Treap 中删掉原素要考虑到多种多样状况。我们可以依照在BST 中删掉原素一样的方式来删掉Treap 中的原素，即用它的后续(或前轮驱动)连接点的值替代它，随后删掉它的后续(或前轮驱动)连接点。
所述方式期待算法复杂度为O(logN)，可是这类方式并沒有灵活运用Treap 现有的任意特性，只是再次得任意选择替代连接点。大家得出一种更加通用性的删掉方式，这类方式是根据转动调节的。最先要在Treap 树中寻找待删掉连接点的部位，随后分状况探讨：
状况一，该连接点为叶连接点或链节点，则该连接点是能够立即删掉的连接点。若该连接点有非空档连接点，用非空档连接点替代该连接点的，不然用空连接点替代该连接点，随后删掉该连接点。
状况二，该连接点有两个非空档连接点。大家的对策是根据转动，使该连接点变成能够立即删掉的连接点。假如该连接点的左子连接点的优先低于右子连接点的优先，左旋体该连接点，使该连接点降至右子树的根节点，随后浏览右子树的根节点，再次探讨；相反，左旋体该连接点，使该连接点降至左子树的根节点，随后浏览左子树的根节点，那样坚持下去，直至变为能够立即删掉的连接点。
BST_Node *root;
void Treap_Delete(Treap_Node *&P,int *value) //连接点表针要传送引入
{
if (value==P->value) //寻找要删掉的连接点 对其删掉
{
if (!P->right || !P->left) //状况一，该连接点能够立即被删掉
{
Treap_Node *t=P;
if (!P->right)
P=P->left; //用左子连接点替代它
else
P=P->right; //用右子连接点替代它
delete t; //删掉该连接点
}
else //状况二
{
if (P->left->fix < P->right->fix) //左子连接点调整值较小，左旋体
{
Treap_Right_Rotate(P);
Treap_Delete(P->right,r);
}
else //左子连接点调整值较小，左旋体
{
Treap_Left_Rotate(P);
Treap_Delete(P->left,r);
}
}
}
else if (value < P->value)
Treap_Delete(P->left,r); //在左子树搜索要删掉的连接点
else
Treap_Delete(P->right,r); //在右子树搜索要删掉的连接点
}
4. Treap运用
Treap能够处理splay tree能够处理的全部难题，实际参照另一篇博闻：《数据结构之伸展树》
能够那样界定建筑结构：
struct Treap_Node
{
Treap_Node *left,*right; //连接点的上下子树的表针
int value,fix,weight,size; //连接点的值，优先，反复记数（纪录同样连接点数量，节约室内空间），子树尺寸
inline int lsize(){ return left ?left->size ?0; } //回到左子树的连接点数量
inline int rsize(){ return right?right->size?0; } //回到右子树的连接点数量
};
5. 小结
Treap 做为一种简约高效率的井然有序算法设计，在电子信息科学和关键技术中拥有 关键的影响力。它能够用于完成结合、多种结合、词典等器皿型算法设计，还可以用于设计方案动态性统计分析算法设计。
6. 参考文献
（1）Treap：http://www.nocow.cn/index.php/Treap
（2）任意均衡二叉查找树Treap 的剖析与运用：http://www.byvoid.com/blog/wp-content/uploads/2010/12/treap-analysis-and-application.pdf
