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 ;

}

巴特西

FHQ-Treap小结

最新文章

热门文章