在二叉搜索树中计算高度的最佳方法是什么？(平衡AVL树)

Question

我正在寻找计算AVL树中节点平衡的最佳方法.我以为我有它工作,但经过一些繁重的插入/更新,我可以看到它的工作正常(根本没有).

这是一个由两部分组成的问题,第一部分是如何计算子树的高度,我知道定义"节点的高度是从该节点到叶子的最长向下路径的长度".而我理解它,但我没有实现它.并且为了进一步混淆我这个引用可以在维基百科的树高上找到"传统上,值-1对应于没有节点的子树,而零对应于具有一个节点的子树."

而第二部分是得到一个子树的平衡因素,AVL树,我没有问题理解概念,"让你的高度L和R子树和减去R从L".这被定义为这样的事情:BALANCE = NODE[L][HEIGHT] - NODE[R][HEIGT]

在维基百科上阅读在描述插入到AVL树中的前几行中说:"如果平衡因子变为-1,0或1,那么树仍然是AVL形式,并且不需要旋转."

然后继续说,"如果平衡因子变为2或-2,那么植根于此节点的树是不平衡的,并且需要树旋转.最多需要单次或双次旋转来平衡树." - 我没有抓麻烦.

但是(是的,总有一个但是).

这是令人困惑的地方,文本说明"如果R的平衡因子为1,则意味着插入发生在该节点的(外部)右侧,需要左旋转".但是从理解的角度来看,正如我所引用的那样,如果平衡因素在[-1, 1]那之内,那么就没有必要进行平衡了吗？

我觉得我是如此接近抓概念,我已经得到了树旋转下来,实现正常的二叉搜索树,抓AVL树的边缘,但只是似乎缺少必要的顿悟.

编辑:代码示例比学术公式更受欢迎,因为我总是更容易在代码中掌握一些东西,但是非常感谢任何帮助.

编辑:我希望我能将所有答案都标记为"已接受",但对我而言,NIck的答案是第一个让我走"aha"的答案.

Answer 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

我希望这是有道理的

Answer 2

您不需要即时计算树的深度。

您可以在执行操作时维护它们。

此外，您实际上不必保持对深度的跟踪；您可以简单地跟踪左右树深度之间的差异。

http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx

只是跟踪平衡因子（左右子树之间的差异）我发现从编程 POV 中更容易，除了在旋转后整理平衡因子是一个 PITA ......

Answer 3

• 高度很容易通过递归实现，取子树高度的最大值加一。

• 我想，“R 的平衡因子”是指失去平衡的树的右子树。