AVL树插入

Question

当我递归调用插入函数以将节点添加到 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) );
  }
                ...
}

Answer 1

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

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

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

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

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

Answer 2

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

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

但这不是最好的方法，因为这种方法的复杂性是 O( h ) 其中h是AVL树中节点的高度。为了更好的方法，需要进行更广泛的讨论:)

网络上有许多关于 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()< /code> 函数看起来错误。我不知道 aNew->num 与 a->num 相比在哪里。是否转到左子树或右子树必须取决于此。给定的代码似乎无条件添加到左子树。