0

AVL ツリーにノードを追加するための挿入関数を再帰的に呼び出すときに、特定のノードのバランス係数を計算するにはどうすればよいですか。ローテーション ロジックを開始していません。バランス係数を計算したいだけです。

私の現在の試みでは、左と右のサブツリーの高さを保存することを余儀なくされています。それらがなければバランス係数を見つけることができないからです。

typedef struct _avlTree
{
 int num;
 int balFactor;
 int height[2];  // left & right subtree heights
 struct _avlTree *left,*right;
} *avlTree;


int avlAdd(avlTree a,avlTree aNew)
{
                ...
  if(a->left == NULL)   // left subtree insertion case
  {
   a->left = aNew;
   return(1); 
  }
  else
  {
   a->height[0] = avlAdd(a->left,aNew);
   a->balFactor = a->height[0] - a->height[1];
   return( (a->height[0]>a->height[1]) ? (a->height[0]+1) : (a->height[1]+1) );
  }
                ...
}
4

2 に答える 2

1

バランス係数は、ノードの左右のサブツリー間の高さの差です。

新しいノードを作成するときは、バランスが取れている（サブツリーがない）ため、バランス係数をゼロに初期化します。

右側に新しいノードを挿入する場合は、バランス係数を1増やします。

左側に新しいノードを挿入する場合は、バランス係数を1つ減らします。

リバランス（回転）後、このノードでサブツリーの高さを増やすと、高さの増加を親ノードに再帰的に伝播します。

于 2010-10-12T18:45:15.293 に答える
1

これは非常に単純なアプローチです。再帰height()関数があった場合、バランス係数は次のように簡単に計算できます。

node->balFactor = height( node->right ) - height( node->left );

ただし、このアプローチの複雑さは AVL ツリー内のの高さにあるO( h )ため、これは最善のアプローチではありません。より良いアプローチのためには、より大きな議論が必要です:)hnode

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/

ところで、avlAdd()関数は間違っているようです。aNew->numと比べてがどこにあるかわかりませんa->num。左のサブツリーまたは右のサブツリーに移動するかどうかは、それに依存する必要があります。指定されたコードは、無条件に左のサブツリーに追加されているようです。

于 2010-10-12T19:07:27.657 に答える