treap 的C实现 --增加实用接口 (2011-08-07
15:05) 转载
这个版本改进了功能
1允许重复元素插入，维护一个字段 weight，如果weight >1 ,表示存在重复元素。
/*尽量不要用重复插入，因为有date字段*/
2 增添了floor 和ceil两个功能，顾名思义，就是key值不大于 A的最大元素,和K值不小于A的最小元素
3 选择第K个最小关键字的元素。0表示最小关键字，1表示第二小关键字。
--------------------------------------------------------------------------------------------------
#ifndef _TREAP_H
#define _TREAP_H
typedef int key_type ;
typedef unsigned int prio_type;
typedef struct _treap_node
{
struct
_treap_node *left;
struct
_treap_node *right;
key_type
key;
prio_type
priority;
int size;
int
weight;
int data;
}treap_node;
typedef struct _treap
{
treap_node*
root;
}treap;
treap_node* treap_insert(treap_node* root,int key,int data);
treap_node* treap_delete(treap_node* root,int key);
treap_node* treap_floor(treap_node *root,key_type key);
treap_node* treap_ceil(treap_node* root,key_type key);
treap_node* treap_select(treap_node* root,int K); /*0 is the min
element*/
#endif
--------------------------------treap.c-----------------------------------------------------------
#include
#include"treap.h"
#include
#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;
}
-----------------------------treap_test.c-----------------------------------------------------------
#include
#include
#include
#include"treap.h"
#define NODE_NUM 10
#define random(x) (rand()%x)
void test_treap()
{
int i;
treap_node* floor = NULL;
treap_node* mid = NULL;
int array_random[NODE_NUM] ;
for(i = 0;i
{
array_random[i] = random(10000);
printf("array_random[%d]
= %d\n",i,array_random[i]);
}
treap my_treap;
my_treap.root = NULL;
for(i = 0;i
{
my_treap.root =
treap_insert(my_treap.root,array_random[i],array_random[i]);
}
floor = treap_floor(my_treap.root, 5000);
if(floor)
printf("the biggest node biger than 5000 is %d\n",floor->key);
mid = treap_select(my_treap.root,my_treap.root->size/2);
if(mid)
printf("the mid is %d\n",mid->key);
}
int main()
{
test_treap();
return 0;
}