计算avl树中节点的平衡因子

Question

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

Answer 1

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

例子：

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
};

Answer 2

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

更新这个数字将会很复杂。当您插入节点时，您必须更新路径上的所有高度，但不是每个高度。高度始终等于 max( 左子高度，右子高度 ) + 1。此插入是递归的，我不知道这对您来说是否有问题。此外，在平衡过程中，您必须更新高度，并且可能需要再次使用递归。

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