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(后綴和,莫隊算法,容斥原理,好題)