Treap树的C++类实现-创新互联
Treap:
创新互联建站服务项目包括东乡族网站建设、东乡族网站制作、东乡族网页制作以及东乡族网络营销策划等。多年来,我们专注于互联网行业,利用自身积累的技术优势、行业经验、深度合作伙伴关系等,向广大中小型企业、政府机构等提供互联网行业的解决方案,东乡族网站推广取得了明显的社会效益与经济效益。目前,我们服务的客户以成都为中心已经辐射到东乡族省份的部分城市,未来相信会继续扩大服务区域并继续获得客户的支持与信任!一种数据结构,结合了二叉搜索树和堆的特点,为了避免BST树插入有序数列时一边树过高的问题,引入了随机权值,在插入时进行随机权值的比较来进行左旋右旋的操作,进而达到平衡的效果,目的与avl类似,但操作方便,代码更加简洁。支持插入节点、删除节点、求第x大的节点、求权值为x的节点的排名、求权值比x小的大节点、求权值比x大的最小节点
除建树外,各操作时间复杂度均为O(logn)
#include#include#include#include#includeusing namespace std;
struct Node {
int data;
Node *left;
Node *right;
int priority;
int size;
int cnt;
Node(int value, int level) : data(value), left(NULL), right(NULL), priority(level), size(1), cnt(1) {}
};
class Treap {
private:
Node *root;
void leftRotate(Node* &p); //左旋
void rightRotate(Node* &p); //右旋
void insert(Node* &p, int value); //插入节点的递归写法
void remove(Node* &p, int value); //删除节点的递归写法
int get_rank_by_value(Node* &p, int value); //通过排名获取节点值的递归写法
int get_value_by_rank(Node* &p, int rank); //通过节点值获取排名的递归写法
int get_prev(Node* &p, int value); //找到节点的前驱的递归写法
int get_next(Node* &p, int value); //找到节点的后继的递归写法
void pushup(Node* &p); //更新节点的参数
public:
Treap();
void insert(int value);
void remove(int x);
bool search(int x);
int get_rank_by_value(int value);
int get_value_by_rank(int rank);
int get_prev(int value);
int get_next(int value);
bool empty(); //判断是否树为空
};
Treap::Treap() {
root = NULL;
}
void Treap::pushup(Node* &p){
if(!p) return;
p->size = 0;
if(p->left) p->size += p->left->size;
if(p->right) p->size += p->right->size;
p->size += p->cnt;
}
void Treap::leftRotate(Node* &p) {
Node *k = p->right;
p->right = k->left;
k->left = p;
p = k;
pushup(p->left);
pushup(p);
}
void Treap::rightRotate(Node* &p) {
Node *k = p->left;
p->left = k->right;
k->right = p;
p = k;
pushup(p->right);
pushup(p);
}
void Treap::insert(int value) {
insert(root, value);
}
void Treap::insert(Node* &p, int value) {
if (p == NULL) {
p = new Node(value, rand());
}
else if (value == p->data) p->cnt++;
else if (value< p->data) {
insert(p->left, value);
if(p->left && p->left->priority >p->priority) rightRotate(p);
}
else{
insert(p->right, value);
if(p->right && p->right->priority< p->priority) leftRotate(p);
}
pushup(p);
}
void Treap::remove(int value) {
remove(root, value);
}
void Treap::remove(Node* &p, int value) {
if(!p){cout<<"invalid value!"<data == value) {
if (p->left == NULL) {
p = p->right;
} else if (p->right == NULL) {
p = p->left;
} else {
if (p->left->priority >p->right->priority) {
rightRotate(p);
remove(p->right, value);
} else if (p->left->priority< p->right->priority) {
leftRotate(p);
remove(p->left, value);
}
}
} else {
if (value< p->data) {
remove(p->left, value);
} else {
remove(p->right, value);
}
}
pushup(p);
}
bool Treap::search(int value) {
Node *p = root;
while (p) {
if (p->data == value) {
return true;
} else {
p = p->data< value ? p->right : p->left;
}
}
return false;
}
bool Treap::empty(){
return root == nullptr ? true : false;
}
int Treap::get_rank_by_value(Node* &p, int value){
if(!p) return -1;
int l = 0;
if(p->left) l = p->left->size;
if(p->data == value) return l + 1;
if(p->data >value) return get_rank_by_value(p->left, value);
return l + p->cnt + get_rank_by_value(p->right, value);
}
int Treap::get_rank_by_value(int value){
return get_rank_by_value(root, value);
}
int Treap::get_value_by_rank(Node* &p, int rank){
if(!p) return INT_MAX;
int l = 0;
if(p->left) l = p->left->size;
if(l >= rank) return get_value_by_rank(p->left, rank);
if(l + p->cnt >= rank) return p->data;
return get_value_by_rank(p->right, rank - l - p->cnt);
}
int Treap::get_value_by_rank(int rank){
return get_value_by_rank(root, rank);
}
int Treap::get_prev(Node* &p, int value){
if(!p) return -INT_MAX;
if(p->data >= value) return get_prev(p->left, value);
return max(p->data, get_prev(p->right, value));
}
int Treap::get_prev(int value){
return get_prev(root, value);
}
int Treap::get_next(Node* &p, int value){
if(!p) return INT_MAX;
if(p->data<= value) return get_next(p->right, value);
return min(p->data, get_next(p->left, value));
}
int Treap::get_next(int value){
return get_next(root, value);
}
测试代码:
int main(int argc, char const *argv[]) {
Treap treap;
int N;
cout<<"input len: ";
cin>>N;
cout<>value;
treap.insert(value);
}
cout<>query;
cout<<"value "<
测试结果:
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
本文名称:Treap树的C++类实现-创新互联
网站链接:http://pwwzsj.com/article/dcschg.html