Treap 動態(tài)平衡樹

2019-11-09 19:49:46

字體：大中小

來源：轉(zhuǎn)載

供稿：網(wǎng)友

(注：本文是筆者在學(xué)習(xí)Treap的時候的一點收獲，并將一些基礎(chǔ)知識記錄下來）

Treap

定義：

treap是一中動態(tài)平衡的BST，可以高效地處理插入和刪除等，是一棵有鍵值和優(yōu)先值的樹。

一些小筆記：

（我剛學(xué)c++是很討厭指針，但學(xué)到Treap時竟然可以接受了，O(∩_∩)O~~）

初始定義

struct node{ char *ch[2];//左右子樹 int r;//隨機(jī)的優(yōu)先值 int v;//值 int s;//以這個節(jié)點為根的節(jié)點總數(shù) 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; }};

旋轉(zhuǎn)

void rotate(node* &o,int d)//左右旋轉(zhuǎn) { 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的旋轉(zhuǎn) { 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);//注意有沒有相同的結(jié)點 insert(o->ch[d],x); if(o->ch[d]->r > o->r) rotate(o,d^1); }}

刪除

void remove(node* &o,int x)//刪除結(jié)點 { 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); }//將左右子樹的根中優(yōu)先級高的旋轉(zhuǎn)上來，再繼續(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);}

這是我所偏好的代碼風(fēng)格。。。

然后還有一道很妙的例題，叫：LA-5031，感覺很復(fù)雜O(∩_∩)O~

上一篇：Day16_01 集合框架（ArrayList存儲字符串并遍歷）

下一篇：天氣預(yù)報接口