// 2016_2_20_treap.cpp : Defines the entry point for the console application.
//
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef struct node_t* Node;
typedef struct treap_t* Treap;
struct node_t
{
Node left;//左节点
Node right;//右节点
int priority;//优先级
int key;//存储的关键字
};
struct treap_t
{
Node root;
};//treap_t 是 标识符，而不是名字
//左旋转
void rotate_left(Node* node)
{
Node x=(*node)->right;//(*node)才是指向根节点的指针
(*node)->right=x->left;
x->left=*node;
*node=x;
}
//指针数组--是存储指针的数组，数组的名字本身是一个指针，数组的名字就相当于node
//这个node相当于是二重指针，因为它是使用一个指针类型声明的一个指针，声明一个指针，往上提升一个层次
//右旋转
void rotate_right(Node* node)
{
Node x=(*node)->left;
(*node)->left=x->right;
x->right=*node;
*node=x;
}
//插入操作
void treap_insert(Node* root,int key,int priority)
{
//根为null，则直接创建此节点为根节点
if(*root == NULL)
{
*root=(Node)malloc(sizeof(struct node_t));
(*root)->left=NULL;
(*root)->right=NULL;
(*root)->priority=priority;
(*root)->key=key;
}
//向左插入节点
else if(key<(*root)->key)
{
treap_insert(&((*root)->left),key,priority);
if((*root)->left->priority<(*root)->priority)//插入之后，如果左边的优先级小于根节点的优先级，则需要旋转
rotate_right(root);
}
//向右插入节点
else
{
treap_insert(&((*root)->right),key,priority);
if((*root)->right->priority < (*root)->priority)//插入之后，如果右边的优先级小于根节点的优先级，则需要旋转
rotate_left(root);
}
}
void treap_delete(Node* root,int key)
{
if(*root != NULL)
{
if(key < (*root)->key)
treap_delete(&((*root)->left),key);
else if(key > (*root)->key)
treap_delete(&((*root)->right),key);
else
{
//左右孩子都为空不用单独写出来
if((*root)->left == NULL)//删除节点之后，如果这个节点有左孩子，则把左孩子替换这个节点的位置
*root=(*root)->right;
else if((*root)->right==NULL)
*root=(*root)->left;
else//如果删除的结点有左右两个孩子的话，则需要对节点先旋转，然后再删除
{
if((*root)->left->priority < (*root)->right->priority)//如果左子树的优先级小于右子树的优先级，则右旋转
{
rotate_right(root);
treap_delete(&((*root)->right),key);
}
else//否则，左旋转
{
rotate_left(root);
treap_delete(&((*root)->left),key);
}
}
}
}
}
//中序遍历
void in_order_traverse(Node root)
{
if(root != NULL)
{
in_order_traverse(root->left);
printf("%d\t",root->key);
in_order_traverse(root->right);
}
}
//计算树的高度
int depth(Node node)
{
if(node == NULL)
return -1;
int l=depth(node->left);
int r=depth(node->right);
return (l<r)?(r+1):(l+1);
}
int main()
{
Treap treap=(Treap)malloc(sizeof(struct treap_t));
treap->root=NULL;
int i=0;
srand(time(0));//这句代码是啥意思啊？
for(i=0;i<100;i++)
treap_insert(&(treap->root),i,rand());
in_order_traverse(treap->root);
printf("\n高度：%d\n",depth(treap->root));
printf("---分割线---\n");
for(i=23;i<59;i++)
treap_delete(&(treap->root),i);
in_order_traverse(treap->root);
printf("\n高度：%d\n",depth(treap->root));
return 0;
}
原文：http://www.cnblogs.com/Study02/p/5203345.html