Treap 动态平衡树

2019-11-10 17:41:09

字体：大中小

来源：转载

供稿：网友

(注：本文是笔者在学习Treap的时候的一点收获，并将一些基础知识记录下来）

Treap

定义：

treap是一中动态平衡的BST，可以高效地处理插入和删除等，是一棵有键值和优先值的树。

一些小笔记：

（我刚学c++是很讨厌指针，但学到Treap时竟然可以接受了，O(∩_∩)O~~）

初始定义

struct node{ char *ch[2];//左右子树 int r;//随机的优先值 int v;//值 int s;//以这个节点为根的节点总数 int cmp(int x) { if(x == v) return -1; return x < v ? 0 : 1; } void maintain()//用于更新s { s = 1; if(ch[0] != NULL) s += ch[0]->s; if(ch[1] != NULL) s += ch[1]->s; }};

旋转

void rotate(node* &o,int d)//左右旋转 { node* k = o->ch[d^1]; o-ch[d^1] = k->ch[d]; k-ch[d] = o; o = k;}//then change rotatevoid rotate(node* &o,int d)//加上maintain的旋转 { node* k = o->ch[d^1]; o->ch[d^1] = k->ch[d]; k->ch[d] = o; o->maintain(); k->maintain();//先更新o，再更新k o = k;}

插入

void insert(node* &o,int x){ if(o == NULL) { o = new node(); o->ch[0] = o->ch[1] = NULL; o->v = x; o->rand(); } else { int d = o->cmp(x);//注意有没有相同的结点 insert(o->ch[d],x); if(o->ch[d]->r > o->r) rotate(o,d^1); }}

删除

void remove(node* &o,int x)//删除结点 { int d = o->cmp(x); if(d == -1) { if(o->ch[0] == NULL) o = o-> ch[1]; else if(o->ch[1] == NULL) o = o-> ch[0]; else { int d2 = (o->ch[0]->r > o->ch[1]->r ? 1 : 0); rotate(o,d2); remove(o->ch[d2],x); }//将左右子树的根中优先级高的旋转上来，再继续删点 } else remove(o->ch[d],x);}

查询

int find(node* o,int x)//在每次操作前可以查询这个点是否存在 { while(o != NULL) { int d = o->cmp(x); if(d == -1) return -1;//存在 else o = o->ch[d]; } return 0;//不存在 }

Kth

int kth(node* o,int k)//找第k大的值 { if(o == NULL || k <= 0 || k > o->s) return 0; int s = (o->ch[0] == NULL ? 0 : o->ch[0]->s; if(k == s+1) return o->v; else if(k <= s) return kth(o->ch[0],k); else return kth(o->ch[1],k-s-1);}

这是我所偏好的代码风格。。。

然后还有一道很妙的例题，叫：LA-5031，感觉很复杂O(∩_∩)O~

上一篇：可调闹钟lcd时钟

下一篇：gym-101138D(后缀和,莫队算法,容斥原理,好题)