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

这是一个非常简单的方法。如果有一个递归height()函数，那么平衡因子可以简单地计算为

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

虽然这不是最好的方法，因为这种方法的复杂性在于AVL 树中的高度在O( h )哪里。为了更好的方法，需要进行更大的讨论:)hnode

网络上有很多关于 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 回答
1

平衡因子是节点的左右子树之间的高度差。

创建新节点时，将平衡因子初始化为零，因为它是平衡的（它没有子树）。

如果要在右侧插入一个新节点，请将平衡因子增加 1。

如果要在左侧插入新节点，请将平衡因子减少 1。

重新平衡（旋转）后，如果增加该节点的子树高度，则递归地将高度增加传播到父节点。

于 2010-10-12T18:45:15.293 回答