AVLツリーメモ(二):mantain、delete

まずmantainで操作します.AVLTREのバランスを維持できます.mantainがあったら、AVLTREのinsertとdeleteはすぐにバランスを維持するのではなく、操作が終わったらバランスを維持することができます.

void maintain(int &r)
{
    if(tree[tree[r].lc].h==tree[tree[r].rc].h+2)
    {
        int t=tree[r].lc;
        if(tree[tree[t].lc].h==tree[tree[r].rc].h+1)r=zig(r);
        else if(tree[tree[t].rc].h==tree[tree[r].rc].h+1)r=zagzig(r);
    }
    else if(tree[tree[r].rc].h==tree[tree[r].lc].h+2)
    {
        int t=tree[r].rc;
        if(tree[tree[t].rc].h==tree[tree[r].lc].h+1)r=zag(r);
        else if(tree[tree[t].lc].h==tree[tree[r].lc].h+1)r=zigzag(r);
    }
    tree[r].h=max(tree[tree[r].lc].h,tree[tree[r].rc].h)+1;
}

よく見ると昨日のinsertのメンテナンスバランスと似ています.今回はtree[r].vと挿入値xでxを比較することができません.左子樹か右子樹かをhで判断します.そしてinsertは二叉で木を探すinsertです.

int insert(int r,int x)
{
    if(r==0)
    {
        tree[++cnt].v=x;
        tree[cnt].h=1;
        return cnt;
    }
    if(tree[r].v>x)tree[r].lc=insert(tree[r].lc,x);
    else if(tree[r].v<x)tree[r].rc=insert(tree[r].rc,x);
    maintain(r);
    return r;
}

次はdelete操作です.まず私達はfind、findが来たらdeleteにします.deleteのポイントは葉なら、直接削除します.息子が一人しかいないなら、この点を削除して、その父親を直接に息子につなげます.息子が左右にいるなら、面倒です.その前駆を見つけて、この点の値を前駆の値に修正して、最後に前駆を削除します.前駆は必ず息子が2人いるという状況がないことが証明されています.可能なのはこの点を削除すると、前駆者が上に来るからです.この点を直接前駆に変えて、前の駆を削除したほうがいいです.実際の実装はfindを参照することができる.findが来たら、前の2つの状況なら、削除します.第三種類なら、現在のポイントの前駆を削除します.削除したらh値を維持してください.

int del(int &r,int x)
{
    int tv;
    if(x==tree[r].v||(x<tree[r].v&&tree[r].lc==0)||(x>tree[r].v&&tree[r].rc==0))
    {
        if(tree[r].lc==0||tree[r].rc==0)
        {
            tv=tree[r].v;
            r=tree[r].lc+tree[r].rc;
            return tv;
        }
        else tree[r].v=del(tree[r].lc,x);
    }
    else
    {
        if(tree[r].v>x)tv=del(tree[r].lc,x);
        else tv=del(tree[r].rc,x);
    }
    maintain(r);
    return tv;
}

求前駆の関数を直接呼び出さないでください.時間の複雑さが大きくなります.