在 AVL 树中查找节点的高度以计算平衡因子
Finding Height of a node in an AVL Tree for Balance Factor calculation
AVL 树是一种平衡的二叉搜索树，即高度 = O(log(n))。这是通过确保每个节点都遵循 AVL 树 属性:
来实现的
Height of the left subtree(LST) - Height of the right subtree(RST) is
in the range [-1, 0, 1]
其中高度 (LST) - 高度 (RST) 称为给定节点的平衡因子 (BF)。
节点的高度通常定义为“从该节点到最深节点的路径长度(#edges)”
例如：
根据这个定义，叶子的高度为 0。
但几乎每次在讨论 AVL 树时，人们都认为 叶子的高度为 1。
我的问题是，我们可以将叶子的高度设为0吗？这将使后面的 BST 也成为 AVL 树，对吧？
由于这些文章，身高概念让我感到困惑：
- https://www.geeksforgeeks.org/minimum-number-of-nodes-in-an-avl-tree-with-given-height/
- https://www.tutorialspoint.com/minimum-number-of-nodes-in-an-avl-tree-with-given-height-using-cplusplus
首先，他们从0开始高度。
然后他们说，高度为 2 的 avl 树所需的最小节点数为 4 但是如果高度从零开始，我也可以拥有以下 AVL 树，对吗？
By this definition, height of leaf is 0.
这是正确的。
BUT if height is starting with zero, I can have the following AVL trees too, right?
不，叶子的父节点高度为 1，因为从该节点到叶子的路径有 1 条边。
所以应该是：
O -- height 2, balance factor 2
/
O -- height 1, balance factor 1
/
O -- height 0
根的平衡因子是2，因为它的左子树的高度是1，它的右子树的高度是-1（！）。请注意，如果单个节点的高度为 0，则空树的高度为 -1。这也是Wikipedia中提到的：
The height of a node is the length of the longest downward path to a leaf from that node. [...] The root node has depth zero, leaf nodes have height zero, and a tree with only a single node (hence both a root and leaf) has depth and height zero. Conventionally, an empty tree (tree with no nodes, if such are allowed) has height −1.
所以这些不是有效的 AVL 树：它们需要重新平衡。
AVL 树是一种平衡的二叉搜索树，即高度 = O(log(n))。这是通过确保每个节点都遵循 AVL 树 属性:
来实现的Height of the left subtree(LST) - Height of the right subtree(RST) is in the range [-1, 0, 1]
其中高度 (LST) - 高度 (RST) 称为给定节点的平衡因子 (BF)。
节点的高度通常定义为“从该节点到最深节点的路径长度(#edges)”
例如：
根据这个定义，叶子的高度为 0。 但几乎每次在讨论 AVL 树时，人们都认为 叶子的高度为 1。
我的问题是，我们可以将叶子的高度设为0吗？这将使后面的 BST 也成为 AVL 树，对吧？
由于这些文章，身高概念让我感到困惑：
- https://www.geeksforgeeks.org/minimum-number-of-nodes-in-an-avl-tree-with-given-height/
- https://www.tutorialspoint.com/minimum-number-of-nodes-in-an-avl-tree-with-given-height-using-cplusplus
首先，他们从0开始高度。
然后他们说，高度为 2 的 avl 树所需的最小节点数为 4 但是如果高度从零开始，我也可以拥有以下 AVL 树，对吗？
By this definition, height of leaf is 0.
这是正确的。
BUT if height is starting with zero, I can have the following AVL trees too, right?
不，叶子的父节点高度为 1，因为从该节点到叶子的路径有 1 条边。
所以应该是：
O -- height 2, balance factor 2
/
O -- height 1, balance factor 1
/
O -- height 0
根的平衡因子是2，因为它的左子树的高度是1，它的右子树的高度是-1（！）。请注意，如果单个节点的高度为 0，则空树的高度为 -1。这也是Wikipedia中提到的：
The height of a node is the length of the longest downward path to a leaf from that node. [...] The root node has depth zero, leaf nodes have height zero, and a tree with only a single node (hence both a root and leaf) has depth and height zero. Conventionally, an empty tree (tree with no nodes, if such are allowed) has height −1.
所以这些不是有效的 AVL 树：它们需要重新平衡。