#include
#include"treap.h"
#include
#include"treap.h"
#define lsize(node) (node->left?node->left->size:0)
#define rsize(node) (node->right?node->right->size:0)
treap_node* treap_left_rotate(treap_node *node)
{
assert(node->right != NULL);
treap_node* right = node->right;
int original_nodesize = node->size;
node->size = lsize(node) + lsize(right) +node->weight;
right->size = original_nodesize;
node->right = right->left;
right->left = node;
return right;
}
treap_node* treap_right_rotate(treap_node* node)
{
assert(node->left !=NULL);
treap_node* left = node->left;
int original_nodesize = node->size;
node->size = rsize(node)+ rsize(left) + node->weight;
left->size = original_nodesize;
node->left = left->right;
left->right = node;
return left;
}
treap_node* treap_allocnode(key_type key,int data)
{
treap_node* node = NULL;
node = (treap_node*)malloc(sizeof(treap_node));
if(node == NULL)
return NULL;
else
{
node->left = node->right = NULL;
node->key = key;
node->data = data;
node->priority = rand()*rand();
node->size = 1; /*节点个数*/
node->weight = 1;
return node;
}
}
void treap_freenode(treap_node* node)
{
if(node)
free(node);
}
treap_node* __treap_insert(treap_node* root,key_type key,int data,unsigned char *isinsert)
{
if(root == NULL)
{
treap_node *new_node = treap_allocnode(key,data);
*isinsert = 1;
return new_node;
}
if(root->key == key)
{
#if 0 /*如果不允许重复，直接返回*/
return root;
#endif
root->weight++;
*isinsert = 1;
return root; /*允许重复，weight++即可*/
}
if(root->key > key)
{
root->left = __treap_insert(root->left,key,data,isinsert);
if(*isinsert == 1)
root->size ++;
if(root->left->priority < root->priority)
return treap_right_rotate(root);
else
return root;
}
if(root->key < key)
{
root->right = __treap_insert(root->right,key,data);
if(*isinsert == 1)
root->size++;
if(root->right->priority < root->priority)
return treap_left_rotate(root);
else
return root;
}
}
treap_node* treap_insert(treap_node* root,key_type key,int data)
{
unsigned char isinsert =0;
return __treap_insert(root,key,data,&isinsert);
}
treap_node* __treap_delete(treap_node* root,key_type key,unsigned char *isfind)
{
if(root == NULL)
{
*isfind = 0;
return NULL;/*not find a element with key equal to key*/
}
if(root->key == key)
{
*isfind = 1;
if(root->weight == 1)
{
if(root->left == NULL || root->right == NULL)
{
treap_node* delnode =root;
if(root->left == NULL)
root = root->right;
else
root = root->left;
treap_freenode(delnode);
return root;
}
else
{
if(root->left->priority < root->right->priority)
{
treap_node* retnode = root->left;
treap_right_rotate(root);
retnode->right = __treap_delete(root,key,isfind);
if(isfind)
retnode->size--;
return retnode;
}
else
{
treap_node* retnode = root->right;
treap_left_rotate(root);
retnode->left = __treap_delete(root,key,isfind);
if(isfind)
retnode->size--;
return retnode;
}
}
}
else
{
root->weight--;
return root;
}
}
else
{
if(root->key < key)
{
root->right = __treap_delete(root->right,key,isfind);
if(*isfind == 1)
root->size--;
}
else
{
root->left = __treap_delete(root->left,key,isfind);
if(*isfind)
root->size--;
}
return root;
}
}
treap_node* treap_delete(treap_node *root,key_type key)
{
unsigned char isfind = 0;
return __treap_delete(root,key,&isfind);
}
treap_node* __treap_floor(treap_node* node,key_type key,treap_node* optimal)
{
if(node == NULL )
{
return optimal;
}
if(node->key == key)
{
return node; /*及时终止，毕竟压栈弹栈耗费性能*/
}
if(node->key < key)
{
return __treap_floor(node->right,key,node);/* third parameter means node is current optimal*/
}
else
{
return __treap_floor(node->left,key,optimal);
}
}
treap_node* __treap_ceil(treap_node* node ,key_type key,treap_node* optimal)
{
if(node == NULL)
{
return optimal;
}
if(node->key == key)
{
return node; /*及时终止，毕竟压栈弹栈耗费性能*/
}
if(node->key > key)
{
return __treap_ceil(node->left,key,node);
/*third para means node is current optimal*/
}
else
{
return __treap_ceil(node->right,key,optimal);
}
}
treap_node* treap_floor(treap_node *root,key_type key)
{
return __treap_floor(root,key,NULL);
}
treap_node* treap_ceil(treap_node* root,key_type key)
{
return __treap_ceil(root, key,NULL);
}
treap_node* treap_select(treap_node* root,int K) /*0 is the min element*/
{
if(root == NULL)
return NULL;
if(K < lsize(root))
return treap_select(root->left,K);
else if(K >lsize(root) + root->weight)
return treap_select(root->right,K - (lsize(root)+root->weight));
else
return root;
}
