0

我想在不使用任何递归过程的情况下计算 avl 树中节点的平衡因子。我怎样才能做到这一点?请告诉我方法或提供 C++ 代码片段。

4

2 回答 2

8

您可以将平衡因子保存为每个节点保存的信息的一部分。具体来说,您可以保存左右子树的高度,并在插入/删除路径上的每次插入/删除时更新值。

例子:

class Node {
  public:
    // stuff...
    int GetBF() { return lHeight - rHeight; }
  private:
    int data;
    Node* right;
    Node* left;
    Node* parent; // optional...
    int rHeight;  // Height of the right subtree
    int lHeight;  // Height of the left subtree
};
于 2009-12-30T09:54:47.933 回答
2

如果没有递归,它可能会有点复杂,但您可以在每个节点中保存节点高度。然后您可以在恒定时间内获得平衡因子(左右孩子身高之间的差异,如果孩子为 NULL 则高度为 0 )。

更新这个号码会很复杂。插入节点时,您必须更新路径上的所有高度,但不是每个高度。高度总是等于 max(left child height, right child height) + 1。这个插入是递归的,我不知道这对你来说是否有问题。同样在平衡期间,您必须更新高度,并且可能再次使用递归。

我希望这对你有帮助。如果不是,请指定递归问题 - 时间,内存,......我们可以尝试找到更好的解决方案

于 2009-12-30T10:04:17.947 回答