0

この avlRotate 関数を使用するたびに、ツリーからいくつかの要素が削除されます。z は不均衡が検出されたノード、y はより高い高さを持つそのサブツリー ノード、x は新しく挿入されたノードです。この関数は、1 回の挿入の直後に呼び出されます。

#define RESTRUCTURE  a->left = t0; a->right = t1; c->left = t2; c->right = t3; b->left = a; b->right = c;

avlTree avlRotate(avlTree z,avlTree y,avlTree x)
{
    avlTree a,b,c;  
    avlTree t0,t1,t2,t3;

    if(y==z->left && x==y->left)  //single rotation
    {
        a=x;b=y;c=z;
        t0=a->left;
        t1=a->right;
        t2=b->right;
        t3=c->right;
        RESTRUCTURE
        c->height[0] = y->height[1];

    }
    else if(y==z->right && x==y->right) //single rotation
    {
        a=z;b=y;c=x;
        t0=a->left;
        t1=b->left;
        t2=c->left;
        t3=c->right;
        RESTRUCTURE
        a->height[1] = y->height[0];

    }
    else if(y==z->right && x==y->left)  //double rotation
    {
        a=z;b=x;c=y;
        t0=a->left;
        t1=b->left;
        t2=b->right;
        t3=c->right;
        RESTRUCTURE
        a->height[1] = x->height[0];
        c->height[0] = x->height[1];
    }
    else if(y==z->left && x==y->right)  //double rotation
    {
        a=y;b=x;c=z;
        t0=a->left;
        t1=b->left;
        t2=b->right;
        t3=c->right;
        RESTRUCTURE
        a->height[1] = x->height[0];
        c->height[0] = x->height[1];    
    }

    printf("\nRem parts:\n");
    printf("{%d %d} {%d %d} {%d %d}\n",a->part->range[0],a->part->range[1],b->part->range[0],b->part->range[1],c->part->range[0],c->part->range[1]);
    printf("\n\n");

    b->height[0] = ( (a->height[0] > a->height[1]) ? (a->height[0])+1 : (a->height[1])+1 ); 
    b->height[1] = ( (c->height[0] > c->height[1]) ? (c->height[0])+1 : (c->height[1])+1 ); 
    a->balFactor = a->height[0] - a->height[1];
    b->balFactor = b->height[0] - b->height[1];
    c->balFactor = c->height[0] - c->height[1]; 
    return(b);
}

関数は次のように呼び出されます。

if(a->balFactor > 1 || a->balFactor < -1)
    {
        printf("imbalance fside=%d pside=%d\n",*finalSide,*prevSide);

        if(*finalSide == 0)
        {yLike = a->left;}
        else
        {yLike = a->right;}
        if(*prevSide == 0)
        {xLike = yLike->left;}
        else
        {xLike = yLike->right;}
        printf("passing to rotate %u %u %u\n",a,yLike,xLike);
        printf("{%d %d} {%d %d} {%d %d}\n",a->part->range[0],a->part->range[1],yLike->part->range[0],yLike->part->range[1],xLike->part->range[0],xLike->part->range[1]);
        a = avlRotate(a,yLike,xLike);
        avlInOrderTraversal(a,0);           
        printf("{%d %d} {%d %d} {%d %d}\n",a->left->part->range[0],a->left->part->range[1],a->part->range[0],a->part->range[1],a->right->part->range[0],a->right->part->range[1]);
    }

挿入機能で。

出力：

a->height[0]=1 a->height[1]=0
BALANCE FACTOR = 1



    16 to 18
51 to 53



a->height[0]=0 a->height[1]=1
BALANCE FACTOR = -1
a->height[0]=2 a->height[1]=0
BALANCE FACTOR = 2
imbalance fside=0 pside=1
passing to rotate 147992552 147992584 147992616
{51 53} {16 18} {41 41}

Rem parts:
{16 18} {41 41} {51 53}





51 to 53



a->height[0]=0 a->height[1]=1
BALANCE FACTOR = -1



51 to 53
    60 to 61



a->height[0]=1 a->height[1]=1
BALANCE FACTOR = 0



    4 to 6
51 to 53
    60 to 61

この関数で明らかに間違っていることはありますか?

注:各ノードには範囲が格納されます。3 to 5.

4

2 に答える 2

1

ツリーをダンプする関数を作成します。各ノードについて、左、右、上、および左/右のサブツリーの深さを表示します。

ローテーションの前にツリーをダンプし、ローテーション後にダンプします。

それは私が私のものを書いたときに私がしたことです。

ツリーに微妙なバグが発生することになります。問題ごとに SO に頼っても、どこにもすぐには行きません。また、ツリーを登る際にリバランスをデバッグするためのダンプ機能も必要になります。検証が必要な追加と削除には、多くの固有のリバランス ケースがあります。これらすべてにツリー ダンプが必要です。

于 2010-10-13T14:37:37.883 に答える
1

Web には AVL ツリーに関する多数のリソースがあり、その一部を以下に示します。

  1. http://en.wikipedia.org/wiki/AVL_tree
  2. C 実装: http://www.stanford.edu/~blp/avl/libavl.html
  3. アニメーション: http://www.cs.jhu.edu/~goodrich/dsa/trees/avltree.html
  4. アニメーション: http://www.strille.net/works/media_technology_projects/avl-tree_2001/

Blank Xavier の回答をさらに続けると、プログラムのダンプ出力をアニメーションの結果と比較することをお勧めします。

于 2010-10-13T18:26:18.010 に答える