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