Treap
#define NUM 1000struct Node
{
　Node(int d)
　 {
　 　 data = d;
　 　 priority = rand() % NUM;
　 　 lchild = NULL;
　 　 rchild = NULL;
　 }
　int priority;
　 int data;
　Node* lchild;
　Node* rchild;
};
struct Treap
{
　 Treap()
　 {
　 　 head = NULL;
　 }
　 Node* head;
};
void LRotate(Node** node)
{
　Node* temp = (*node)->rchild;
　 (*node)->rchild = temp->lchild;
　 temp->lchild = *node;
　 *node = temp;
}
void RRotate(Node** node)
{
　 Node* temp = (*node)->lchild;
　 (*node)->lchild = temp->rchild;
　 temp->rchild = *node;
　 *node = temp;
}
void insert(Node** node,int d)
{
　 if (NULL == *node)
　 {
　 　 *node = new Node(d);
　 　 return;
　 }
　 if (d < (*node)->data)
　 {
　 　 insert(&(*node)->lchild, d);
　 　 if ((*node)->lchild->priority < (*node)->priority) RRotate(node);
　 }
　else
　 {
　 　 insert(&(*node)->rchild, d);
　 　 if ((*node)->rchild->priority < (*node)->priority) LRotate(node);
　 }
}
void Insert(Treap* treap,int d)
{
　 insert(&treap->head,d);
}
void rmove(Node** node, int d)
{
　 if ((*node)->data == d)
　 {
　 　 if (NULL == (*node)->lchild || NULL == (*node)->rchild)
　 　 {
　 　 　 Node* temp = *node;
　 　 　 *node = NULL == (*node)->lchild ? (*node)->rchild : (*node)->lchild;
　 　 　 delete temp;
　 　 　 return;
　 　 }
　 　 if ((*node)->lchild->priority < (*node)->rchild->priority)
　 　{
　 　 　 RRotate(node);
　 　 　 rmove(&(*node)->rchild, d);
　 　 }
　 　else
　 　 {
　 　 　 LRotate(node);
　 　 　 rmove(&(*node)->lchild, d);
　 　 }
　 　return;
　 }
　if (d < (*node)->data) rmove(&(*node)->lchild, d);
　else rmove(&(*node)->rchild, d);
}
void Rmove(Treap* treap, int d)
{
　rmove(&treap->head, d);
}

AvlTree
struct Node
{
　Node(int d)
　 {
　 　 data = d;
　 　 height = 0;
　 　lchild = NULL;
　 　rchild = NULL;
　 }
　 int height;
　 int data;
　 Node* lchild;
　Node* rchild;
};
struct AvlTree
{
　 AvlTree()
　 {
　 　 head = NULL;
　 }
　 Node* head;
};
int Height(Node* node)
{
　 return NULL == node ? -1 : node->height;
}
void AdjustHeight(Node* node)
{
　 if (NULL == node) return;
　 node->height = MAX(Height(node->lchild), Height(node->rchild)) + 1;
}
void LRotate(Node** node)
{
　 Node* temp = (*node)->rchild;
　 (*node)->rchild = temp->lchild;
　 temp->lchild = *node;
　 AdjustHeight(temp->lchild);
　 AdjustHeight(temp);
　 *node = temp;
}
void RRotate(Node** node)
{
　Node* temp = (*node)->lchild;
　 (*node)->lchild = temp->rchild;
　 temp->rchild = *node;
　 AdjustHeight(temp->rchild);
　 AdjustHeight(temp);
　*node = temp;
}
void LFix(Node** node)
{
　 if (Height((*node)->lchild) - Height((*node)->rchild) > 1)
　 {
　 　 if (NULL == (*node)->lchild->lchild) LRotate(&(*node)->lchild);
　 　 RRotate(node);
　 }
}
void RFix(Node** node)
{
　if (Height((*node)->rchild) - Height((*node)->lchild) > 1)
　 {
　 　 if (NULL == (*node)->rchild->rchild) RRotate(&(*node)->rchild);
　 　 LRotate(node);
　}
}
void insert(Node** node,int d)
{
　 if (NULL == *node)
　 {
　 　*node = new Node(d);
　 　return;
　 }
　 if (d < (*node)->data)
　 {
　 　 insert(&(*node)->lchild, d);
　 　 LFix(node);
　 }
　else
　 {
　 　insert(&(*node)->rchild, d);
　 　 RFix(node);
　}
　 AdjustHeight(*node);
}
void Insert(AvlTree* avltree,int d)
{
　 insert(&avltree->head,d);
}
void remove(Node** node, int d)
{
　 if ((*node)->data == d)
　 {
　 　 if (NULL == (*node)->lchild || NULL == (*node)->rchild)
　 　 {
　 　 　 Node* temp = *node;
　 　 　 *node = NULL == (*node)->lchild ? (*node)->rchild : (*node)->lchild;
　 　 　 delete temp;
　 　 　 return;
　 　 }
　 　 Node* temp = (*node)->rchild;
　 　 while (temp->lchild != NULL) temp = temp->lchild;
　 　 (*node)->data = temp->data;
　 　 remove(&(*node)->rchild, temp->data);
　 　 LFix(node);
　 　 return;
　 }
　if (d < (*node)->data)
　 {
　 　 remove(&(*node)->lchild, d);
　 　 RFix(node);
　 }
　 else
　 {
　 　 remove(&(*node)->rchild, d);
　 　 LFix(node);
　 }
　 AdjustHeight(*node);
}
void Remove(AvlTree* avltree, int d)
{
　remove(&avltree->head, d);
}