FHQTreap小結

Orz范浩強大爺,竟然搞出了如此奪天地造化的數據結構.

FHQ-Treap,又名非旋Treap,是范浩強大爺在某些奇特的靈感之下發明的一種平衡樹,因其與Treap相似的性質和無旋轉操作的特性被稱為非旋Treap.非旋Treap用Split和merge兩個操作維護平衡,其本質是堆的合併.(或可代替左偏樹?)

前置函數&結構體:

#define Drt pair < Treap * , Treap * > struct Treap { Treap * son[2] ; int val , size , rank ; Treap (int val) : val ( val ) { son[0] = son[1] = NULL ; size = 1 ; rank = rand () ; } inline void maintain () { this->size = 1 ; if ( this->son[0] != NULL ) this->size += this->son[0]->size ; if ( this->son[1] != NULL ) this->size += this->son[1]->size ; return ; } } * root = NULL ;

inline int siz (Treap * rt) { return rt == NULL ? 0 : rt->size ; }

我們先來介紹一下FHQ-Treap的靈魂之一:Split操作

Split(rt,k)表示把以rt為根的樹中的前k個元素分裂出來,其返回值為一個二元組表示分裂出來的兩棵樹的根

也十分好寫

Code:

inline Drt Split (Treap * rt , int k) { if ( rt == NULL ) return Drt ( NULL , NULL ) ; Drt t ; if ( k <= siz ( rt->son[0] ) ) { // 如果說需分裂的前k個都在左子樹,直接遞歸處理 t = Split ( rt->son[0] , k ) ; rt->son[0] = t.second ; // 把左子樹中殘餘的元素和右子樹的元素放到一起即為第二棵新樹 rt->maintain () ; t.second = rt ; } else { // 如果需分裂的前k個不只在左子樹,遞歸向右子樹分裂需要的元素個數 t = Split ( rt->son[1] , k - siz ( rt->son[0] ) - 1 ) ; rt->son[1] = t.first ; t.first = rt ; // 把右子樹中的殘餘前k個拿出來,和左子樹一起組成第一棵新樹 } return t ; }

這樣,就完成了Split操作.

再來看merge操作

merge(x,y)表示把以x為根的樹和以y為根的樹合併,返回值為新樹的根

也並不難寫

Code:

inline Treap * merge (Treap * x , Treap * y) { if ( x == NULL ) return y ; if ( y == NULL ) return x ; // 顯然 if ( x->rank < y->rank ) { // 類似於啟發式合併 x->son[1] = merge ( x->son[1] , y ) ; x->maintain () ; return x ; } else { y->son[0] = merge ( x , y->son[0] ) ; y->maintain () ; return y ; } }

這就是非旋Treap的兩個核心操作,當然還有一些比較重要的基礎操作,直接放上吧,也不難寫

Getrank(rt,key)表示在以rt為根的樹中查詢key的排名(名次樹功能之一)

inline int Getrank (Treap * rt , int key) { if ( rt == NULL ) return 0 ; else if ( key <= rt->val ) return Getrank ( rt->son[0] , key ) ; else return Getrank ( rt->son[1] , key ) + siz ( rt->son[0] ) + 1 ; }

Getkth(rt,key)表示在以rt為根的子樹中查詢排名為key的元素(名次樹功能之二)

inline int Getkth (Treap * & rt , int key) { // 這裡有對根的修改 if ( rt == NULL ) return 0 ; Drt x = Split ( rt , key - 1 ) ; // 把前key-1個數字分裂出來 Drt y = Split ( x.second , 1 ) ; // 這時剩下的樹中的第一個元素即為所求 Treap * t = t.first ; // 先記下來 rt = merge ( x.first , merge ( t , y.second ) ) ; // 別忘了合併回去 return t == NULL ? 0 : t->val ; }

insert(rt,key)表示在以rt為根的樹中插入key這個元素

inline void insert (Treap * & rt , int key) { int k = Getrank ( rt , key ) ; Drt t = Split ( rt , k ) ; // 找出該插入的位置 Treap * node = new Treap ( key ) ; // 創建新節點(只有根的樹) rt = merge ( t.first , merge ( node , t.second ) ) ; // 把新節點合併回去 return ; }

remove(rt,key)$表示在以rt為根的樹中刪除key這個元素

inline void remove (Treap * & rt , int key) { int k = Getrank ( rt , key ) ; Drt x = Split ( rt , k ) ; // 把應該刪除的拿出來 Drt y = Split ( x.second , 1 ) ; delete ( y.first ) ; // 刪去 rt = merge ( x.first , y.second ) ; return ; // 再合併回去 }

前驅和後繼也比較簡單

前驅就是:

Getkth ( root , Getrank ( root , key ) ) ;

後繼就是:

Getkth ( root , Getrank ( root , key + 1 ) + 1 )

當然你也可以像Treap那樣,利用BST的性質去查找前驅和後繼

這幾個相信各位一看就懂,也就不再贅述了.

我個人認為FHQ-Treap是最容易理解的平衡樹,而且碼量也較小,很適合像博主這樣的蒟蒻學習.

Added:

最近又發現了FHQTreap的另一種Split的方式:按權值分裂

就是把整棵樹按照權值分裂成一半比key大的,一半比key小的

有的時候,這種分裂有奇效

Code:

inline Drt SplitV ( Treap * rt , int key ) { if ( rt == NULL ) return Drt ( NULL , NULL ) ; Drt t ; if ( rt->val <= key ) { t = SplitV ( rt->son[1] , key ) ; rt->son[1] = t.first ; rt->maintain () ; t.first = rt ; } else { t = SplitV ( rt->son[0] , key ) ; rt->son[0] = t.second ; rt->maintain () ; t.second = rt ; } return t ; }