计算节点的平衡因子在AVL树 [英] Calculating the balance factor of a node in avl tree

问题描述

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

I want to calculate the balance factor of a node in avl tree without using any recursive procedure. How can i do that? Please tell me method or provide C++ code snippet.

推荐答案

您可以将平衡因子保存为每个节点保存的信息的一部分。 具体而言，可以节省左，右子树的高度，并更新值与每一个插入/缺失插入/缺失的道路上。

You can save the balance factor as a part of the information each node saves. Specifically, you can save the height of the left and right subtrees, and update the values with every insertion/deletion on the insertion/deletion path.

例如：

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

这篇关于计算节点的平衡因子在AVL树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！