首页 > 代码库 > treap模版
treap模版
#include <cstdio> #include <cstring> #include <cstdlib> using namespace std; struct Node { Node *ch[2]; int r; int v; int s; Node(int v): v(v) { ch[0] = ch[1] = NULL; r = rand(); s = 1; } bool operator < (const Node& rhs) const{ return r < rhs.r; } int cmp(int x) const{ if(x == v) return -1; return x < v ? 0 : 1; } void maintain(){ 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] = 0; o->maintain(); k->maintain(); o = k; } void insert(Node* &o, int x){ if(o == NULL){ o = new Node(x); } else{ int d = (x < o->v ? 0 : 1); insert(o->ch[d], x); if(o->ch[d] > o) rotate(o, d^1); } } void remove(Node* &o, int x){ int d= o->cmp(x); if(d == -1){ Node* u = o; if(o->ch[0] != NULL && o->ch[1] != NULL){ int d2 = o->ch[0] > o->ch[1] ? 1 : 0; rotate(o, d2); remove(o->ch[d2], x); } else{ if(o->ch[0] == NULL) o = o->ch[1]; else o = o->ch[0]; delete u; } } else remove(o->ch[d], x); if(o != NULL) o->maintain(); }
treap模版
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。