1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <time.h>
  4 
  5 struct node_t
  6 {
  7   node_t* left;//左节点
  8   node_t* right;//右节点
  9   int priority;//优先级
 10   int key;//存储的关键字
 11 };
 12 
 13 struct treap_t
 14 {
 15   node_t* root;
 16 };
 17 
 18 //左旋转
 19 void rotate_left(node_t** node)
 20 {
 21   node_t* x = (*node)->right;
 22   (*node)->right = x->left;
 23   x->left = *node;
 24   *node = x;
 25 }
 26 
 27 //右旋转
 28 void rotate_right(node_t** node)
 29 {
 30   node_t* x = (*node)->left;
 31   (*node)->left = x->right;
 32   x->right = *node;
 33   *node = x;
 34 }
 35 
 36 //插入操作
 37 void treap_insert(node_t** root, int key, int priority)
 38 {
 39   //根为NULL，则直接创建此结点为根结点
 40   if (*root == NULL)
 41   {
 42     *root = (node_t*)malloc(sizeof(struct node_t));
 43     (*root)->left = NULL;
 44     (*root)->right = NULL;
 45     (*root)->priority = priority;
 46     (*root)->key = key;
 47   }
 48   //向右插入结点
 49   else if (key < (*root)->key)
 50   {
 51     treap_insert(&((*root)->left), key, priority);
 52     if ((*root)->left->priority < (*root)->priority)
 53       rotate_right(root);
 54   }
 55   //向左插入结点
 56   else
 57   {
 58     treap_insert(&((*root)->right), key, priority);
 59     if ((*root)->right->priority < (*root)->priority)
 60       rotate_left(root);
 61   }
 62 }
 63 
 64 void treap_delete(node_t** root, int key)
 65 {
 66   if (*root != NULL)
 67   {
 68     if (key < (*root)->key)
 69       treap_delete(&((*root)->left), key);
 70     else if (key > (*root)->key)
 71       treap_delete(&((*root)->right), key);
 72     else
 73     {
 74       //左右孩子都为空不用单独写出来
 75       if ((*root)->left == NULL)
 76         *root = (*root)->right;
 77       else if ((*root)->right == NULL)
 78         *root = (*root)->left;
 79       else
 80       {
 81         //先旋转，然后再删除
 82         if ((*root)->left->priority < (*root)->right->priority)
 83         {
 84           rotate_right(root);
 85           treap_delete(&((*root)->right), key);
 86         }
 87         else
 88         {
 89           rotate_left(root);
 90           treap_delete(&((*root)->left), key);
 91         }
 92       }
 93     }
 94   }
 95 }
 96 
 97 //中序遍历
 98 void in_order_traverse(node_t* root)
 99 {
100   if (root != NULL)
101   {
102     in_order_traverse(root->left);
103     printf("%d\t", root->key);
104     in_order_traverse(root->right);
105   }
106 }
107 
108 //计算树的高度
109 int depth(node_t* node)
110 {
111     if(node == NULL)
112         return -1;
113     int l = depth(node->left);
114     int r = depth(node->right);
115 
116     return (l < r)?(r+1):(l+1);
117 }
118 
119 int main()
120 {
121   Treap treap = (Treap)malloc(sizeof(struct treap_t));
122   treap->root = NULL;
123   int i = 0;
124   
125   srand(time(0));
126   
127   for (i = 0; i < 100; i++)
128     treap_insert(&(treap->root), i, rand());
129   in_order_traverse(treap->root);
130   printf("\n高度：%d\n", depth(treap->root));
131   
132   printf("---分割线---\n");
133 
134   for (i = 23; i < 59; i++)
135     treap_delete(&(treap->root), i);
136   in_order_traverse(treap->root);
137   printf("\n高度：%d\n", depth(treap->root));
138   return 0;
139 }