ツリーを伸ばして勉強します.

3719 ワード

データ構造 tree query UP。テキスト編集 BTをかける

転載は出典を明記してください.ありがとうございます. http://blog.csdn.net/ACM_cxlove?view mode=contensts by---cxlove
最近勉強しているSplay treeをまとめます.何事も初めが難しいです.このような神のようなデータ構造は、勉強したばかりではつらいです.バランスツリーやSBTなどのデータ構造を先に勉強することを提案します.
資料はすべてネット上でめちゃくちゃにめくったので、前の2つの問題、コードは主に他の人に従って、後はゆっくりと調整して、自分のものになります.
Splay treeは伸び木という意味で、他とは違って伸び作業にあります.
ここでは、木の時間の複雑さ、操作の利点などを説明できないことを証明します.ネットでは正規の資料にも紹介されています.
拡張ツリーは厳密な意味でのバランスツリーではなく、線形構造に劣化する可能性が高いですが、彼のストレッチ操作は、その都度の操作を近似(logn)し、他のデータ構造では実現できないものを解決します.
まず、ストレッチ操作は私の理解では、ストレッチ操作とバランスツリーのバランスが似ていますが、彼はバランスを取ることを要求しないで、回転だけです.
回転するノードの親ノードが目標の結点であれば、一回だけ回転すればいいです.しかし、バランスツリーの中では、このステップはまだ分解されます.
例えば、根を結んでいる左の子供を右に回します.この時、根の左の子供が右の子供がいると、直接に回転します.新しい根は左の子供が二人います.明らかにだめです.左の木を先に左に回してから右に曲がればいいです.
伸び木の中で、親ノードが目標の結点ではない場合は、おじいさんの結点が親ノードの方向と同じであれば、上の右回りまたは左回りを2回連続して行うことができます.方向が違ったら、左と右の二つの回転です.図面の方が分かりやすいです.他の資料から図を見つけられます.伸び木の中で一字型という字型です.複雑な話ですが、Splayでは、コードはすでに先輩達に短く最適化されていて、洗練されています.

void Rotate(int x,int kind){   //kind        
    int y=pre[x];      
    Push_Down(y);  
    Push_Down(x);  
    ch[y][!kind]=ch[x][kind];     
    pre[ch[x][kind]]=y;    
    if(pre[y])    
        ch[pre[y]][ch[pre[y]][1]==y]=x;    
    pre[x]=pre[y];    
    ch[x][kind]=y;    
    pre[y]=x;    
    Push_Up(y);    
}     
//   r   goal
void Splay(int r,int goal){    
    Push_Down(r);  
    while(pre[r]!=goal){    
        if(pre[pre[r]]==goal)    
            Rotate(r,ch[pre[r]][0]==r);    
        else{    
            int y=pre[r];    
            int kind=(ch[pre[y]][0]==y);    
            if(ch[y][kind]==r){    
                Rotate(r,!kind);    
                Rotate(r,kind);    
            }    
            else{    
                Rotate(y,kind);    
                Rotate(r,kind);    
            }    
        }    
    }    
    Push_Up(r);    
    if(goal==0) root=r;    
}

このようなストレッチは私たちの区間操作に何かメリットがありますか?
一つの問題が考えられます.一つの区間[l,r]に対して、バランスツリー、SBTに対して、この区間にすぐに位置決めするのは難しいです.線分樹に対してできることなら、区間を削除したり、回転したりすれば、線分樹はできなくなります.
次にSplay treeはどうやって作ったのかを見てみます.まず木の本質を伸ばしますか?それとも二叉で木を探します.作り方も簡単です.第l-1の結点をルート(以前のSplay操作)に回転させて、第r＋1の結点をルートの右の子供に回転させると、二叉の調べ木によって、この二つの結点の間に、ルートの右の子供である左の木がノード［l,r］を含めていることが分かります.そのうちGet_KthはK番目の結点を見つけて、子樹の大きさを記録すれば、すぐに実現できるという意味です.

int Get_interval(int l,int r){
	Splay(Get_Kth(l-1),0);
	Splay(Get_Kth(r+1),root);
	Push_Up(ch[root][1]);
	Push_Up(root);
}

この関数は、区間[l,r]を実行した後のルートの右の子供の左の木が所要区間となり、操作が可能です.
伸び木は線分樹の一部の作業を完了することもできます.遅延マークを設定したり、上に更新したり、下に更新したりすることもできます.具体的には後の練習の中で会います.
次はいくつかの練習です.
入門問題:いくつかの線分樹を探してもいいです.あるいは他のデータ構造のトレーナーです.操作が少ないです.簡単です.線分樹はここにあります
その後、自分でやったトレーニングの多くはここから参考にしました.
[HUNOI 2002]売上高統計
最初のSplayは、様々なデータ構造が解明されます.その中の主な操作は先駆者と後継者を見つけることです.一本の二叉として木を探すのは難しくないです.一つのノードの後継は、右子樹の中の一番左の結点であり、前駆は左子樹の中で一番右のノードである.
ここにあります
POJ 3468 A Simple Proble with Integers
古典的な線分樹のテーマを比較します.区間を先に木に差し込むと、最初はきちんとしています.その後の操作は順序を変えず、怠け者マークに注意してください.
ここにあります

HDU 1890 Robotic Sort
前に順番を作って、下付きを順番に保存します.K番目の大きさを順に考えて、根に回します.左の木の数は反転して、根を削除してもいいです.
ここにあります
HDU 3436 Que-jumers
ポイントは離散化が必要で、TOPとQULYで動作するノードを取り出して、中間の異なる区間をポイントに縮めることです.
ここにあります
HDU 3487 Play with Charin
新しい操作が現れました.CUT.回転して、削除して、挿入します.鋭いです.
ここにあります
[AHOI 2006]テキストエディタeditor
カーソル位置を保存します.つまりK番目の位置です.その後はSplay経典操作です.
ここにあります
[NOI 2005]修理数列
NOIの中で非常にBTのデータ構造問題ですが、この問題をやったことがありません.Splayの勉強は完璧とは言えません.
他のものは全部似ています.一番大きいサブ列と、線分樹の古典的な操作にも似ています.
ここにあります
POJ 3580 SuperMemo
ユニークな操作があります.REVOLVEは右にシフトして操作します.つまり、区間を見つけて、二つの部分に分けて、削除と挿入します.
ここにあります

Atomインストールactivate-power-mode