【数据结构】伸展树 Splay

// 平衡树 splay 模板
void rotate( int i )
{
    int D = dad[i],G = dad[D],S = son[i][ !typ[i] ];
    son[G][ typ[D] ] = i,dad[S] = D;
    son[D][ typ[i] ] = S,dad[D] = i;
    son[i][ !typ[i] ] = D,dad[i] = G;
    typ[S] = typ[i],typ[i] = typ[D],typ[D] = !typ[S];
    update( D );
}

void splay( int i )
{
    while( typ[i] != 2 )
    {
        if( typ[ dad[i] ] != 2 )
            if( typ[i] == typ[ dad[i] ] ) rotate( dad[i] ); else rotate( i );
        rotate( i );
    }
    update( i );
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!