FHQ-Treap小结

$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 )

这几个相信各位一看就懂,也就不再赘述了.

我个人认为$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 ;
}