在二叉搜索树中计算高度的最佳方法？（平衡AVL树）

一尘不染

在二叉搜索树中计算高度的最佳方法？（平衡AVL树）

algorithm

我正在寻找在AVL-
tree中计算节点平衡的最佳方法。我以为我可以使用它，但是经过大量的插入/更新后，我可以看到它根本无法正常工作。

这是一个分为两部分的问题，第一部分将是如何计算子树的高度，我知道以下定义： “节点的高度是从该节点到叶子的最长向下路径的长度”。
并且我理解它，但是我无法实现它。令我进一步困惑的是，该引言可以在维基百科上以树高的形式找到：
“通常，值-1对应于没有节点的子树，而零则对应于具有一个节点的子树。”

而第二部分是得到一个子树的平衡因素，AVL树，我没有问题理解概念， “让你的高度L和R子树和减去R从L”。定义如下：BALANCE = NODE[L][HEIGHT] - NODE[R][HEIGT]

在Wikipedia上阅读时，在描述插入到AVL树中的前几行中说了这一点： “如果平衡因子变为-1、0或1，则该树仍为AVL形式，不需要旋转。”

然后继续说： “如果平衡因子变为2或-2，则以该节点为根的树是不平衡的，并且需要旋转树。最多只需要旋转一次或两次就可以平衡树。” -我很容易掌握。

但是（是的，总是有一个but）。

这是令人困惑的地方，文本指出 “如果R的平衡因子为1，则意味着插入发生在该节点的（外部）右侧，并且需要向左旋转”
。但是从我的理解中，文本说（如我所引），如果平衡因子在范围之内，[-1, 1]那么就不需要平衡了吗？

我觉得我已经非常了解这个概念，我已经将树旋转了下来，实现了一个普通的二叉搜索树，并且濒临掌握AVL树，但似乎只是缺少了这个重要的顿悟。

编辑： 代码示例比学术公式更可取，因为我一直以来都比较容易掌握代码中的某些内容，但是对您的帮助将不胜感激。

编辑： 我希望我可以将所有答案标记为“已接受”，但是对我来说，尼克的答案是第一个使我“答应”的答案。

阅读 1007

2020-07-28

共1个答案

一尘不染

第1部分-高度

正如starblue所说，高度只是递归的。用伪代码：

height(node) = max(height(node.L), height(node.R)) + 1

现在可以通过两种方式定义高度。它可以是从根到该节点的路径中的节点数，也可以是链接数。根据您引用的页面，最常见的定义是链接数。在这种情况下，完整的伪代码将是：

height(node): 
   if node == null:
        return -1
   else:
        return max(height(node.L), height(node.R)) + 1

如果您想要节点数，则代码为：

height(node): 
   if node == null:
        return 0
   else:
        return max(height(node.L), height(node.R)) + 1

无论哪种方式，我认为重新平衡算法都应该起作用。

但是，如果您在树中存储和更新高度信息，而不是每次都进行计算，则树的效率将大大提高（ O（ln（n）） ）。（ O（n） ）

第2部分-平衡

当它说“如果R的平衡因子是1”时，它是在说右分支的平衡因子，当顶部的平衡因子是2时。它告诉您如何选择单旋转还是旋转。两次旋转。在（类似于python）伪代码中：

if balance factor(top) = 2: // right is imbalanced
     if balance factor(R) = 1: // 
          do a left rotation
     else if balance factor(R) = -1:
          do a double rotation
else: // must be -2, left is imbalanced
     if balance factor(L) = 1: // 
          do a left rotation
     else if balance factor(L) = -1:
          do a double rotation

我希望这是有道理的

2020-07-28