在AVL树中查找节点高度以计算平衡因子

Question

AVL树是一种平衡的二元搜索树，即高度=O（log（n））。这是通过确保每个节点都遵循AVL树属性来实现的：

左侧子树（LST）的高度-右侧子树（RST）的高度在[-1,0,1]范围内

其中，对于给定节点，高度（LST）-高度（RST）称为平衡因子（BF）。

根据这个定义，叶子的高度是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

Answer 1

根据此定义，叶的高度为0。

这是正确的。

但是如果高度从零开始，我也可以有下面的AVL树，对吗？

否，叶的父节点的高度为1，因为从该节点到叶的路径有1条边。

所以应该是：

              O  -- height 2, balance factor 2
             /
            O  -- height 1, balance factor 1
           /
          O  -- height 0

根的平衡因子为2，因为其左子树的高度为1，右子树的高度为-1（！）。请注意，如果单个节点的高度为0，则空树的高度为1。这也是维基百科中提到的：

节点的高度是从该节点到叶子的最长下行路径的长度。[...]根节点的深度为零，叶节点的高度为零，只有单个节点（因此既是根又是叶）的树的深度和高度为零。传统上，空树（没有节点的树，如果允许的话）的高度为−1。

所以这些不是有效的AVL树：它们需要重新平衡。