计算二叉搜索树高度的最佳方法?(平衡 AVL 树) [英] The best way to calculate the height in a binary search tree? (balancing an AVL-tree)

问题描述

我正在寻找在 AVL-tree 中计算节点余额的最佳方法.我以为我可以正常工作，但是在进行了大量插入/更新之后，我可以看到它无法正常工作(根本无法正常工作).

I'm looking for the best way to calculate a nodes balance in an AVL-tree. I thought I had it working, but after some heavy inserting/updating I can see that it's not working correct (at all).

这是一个两部分的问题，第一部分是如何计算子树的高度，我知道定义节点的高度是最长向下路径的长度到那个节点的叶子." 我理解它，但我未能实现它.更让我困惑的是，这句话可以在维基百科的树高上找到通常，值 -1 对应于没有节点的子树，而零对应于有一个节点的子树."

This is kind of a two-part question, the first part would be how to calculate the height of a sub-tree, I know the definition "The height of a node is the length of the longest downward path to a leaf from that node." and I understand it, but I fail at implementing it. And to confuse me further this quote can be found on wikipedia on tree-heights "Conventionally, the value -1 corresponds to a subtree with no nodes, whereas zero corresponds to a subtree with one node."

第二部分是获取 AVL 树中子树的平衡因子，我理解这个概念没有问题，获取 L 的高度和R 子树并从 L" 中减去 R.这被定义为这样的:BALANCE = NODE[L][HEIGHT] - NODE[R][HEIGT]

And the second part is getting the balance factor of a sub-tree in an AVL tree, I've got no problem understanding the concept, "get the height of your L and R sub-trees and subtract R from L". And this is defined as something like this: BALANCE = NODE[L][HEIGHT] - NODE[R][HEIGT]

阅读维基百科在描述插入 AVL 树的前几行中说:如果平衡因子变为 -1、0 或 1，则树仍处于 AVL 形式，不需要旋转."

Reading on wikipedia says this on the first few lines describing insertions into an AVL tree: "If the balance factor becomes -1, 0, or 1 then the tree is still in AVL form, and no rotations are necessary."

然后继续说如果平衡因子变为 2 或 -2，则以该节点为根的树不平衡，需要进行树旋转.最多需要单次或双次旋转平衡树." - 我很容易掌握.

It then goes on, saying this "If the balance factor becomes 2 or -2 then the tree rooted at this node is unbalanced, and a tree rotation is needed. At most a single or double rotation will be needed to balance the tree." - which I have no trouble grasping.

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

But (yes, there's always a but).

这是令人困惑的地方，文本指出如果 R 的平衡因子为 1，则意味着插入发生在该节点的(外部)右侧，需要向左旋转".但是从我的理解来看，文本说(正如我引用的那样)如果平衡因子在 [-1, 1] 内，那么就不需要平衡?

Here's where it gets confusing, the text states "If the balance factor of R is 1, it means the insertion occurred on the (external) right side of that node and a left rotation is needed". But from m understanding the text said (as I quoted) that if the balance factor was within [-1, 1] then there was no need for balancing?

我觉得我已经接近掌握这个概念了，我已经降低了树的旋转度，实现了一个普通的二叉搜索树，并且在掌握 AVL 树的边缘，但似乎只是缺少那个基本的顿悟.

I feel I'm so close to grasping the concept, I've gotten the tree rotations down, implemented a normal binary search tree, and on the brink of grasping AVL-trees but just seem to be missing that essential epiphany.

代码示例比学术公式更受欢迎，因为我总是更容易掌握代码中的某些内容，但非常感谢任何帮助.

Code examples are preferred over academic formulas as I've always had an easier time grasping something in code, but any help is greatly appreciated.

我希望我可以将所有答案标记为已接受"，但对我来说，尼克的答案是第一个让我啊哈"的答案.

I wish I could mark all answers as "accepted", but for me NIck's answer was the first that made me go "aha".

推荐答案

Part 1 - height

正如starblue 所说，高度只是递归的.在伪代码中:

Part 1 - height

As starblue says, height is just recursive. In pseudo-code:

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

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

Now height could be defined in two ways. It could be the number of nodes in the path from the root to that node, or it could be the number of links. According to the page you referenced, the most common definition is for the number of links. In which case the complete pseudo code would be:

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

如果您想要节点数，代码将是:

If you wanted the number of nodes the code would be:

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

无论如何，我认为重新平衡算法的工作原理应该相同.

Either way, the rebalancing algorithm I think should work the same.

但是，如果您在树中存储和更新高度信息，而不是每次都计算它，那么您的树将更加高效(O(ln(n))).(O(n))

However, your tree will be much more efficient (O(ln(n))) if you store and update height information in the tree, rather than calculating it each time. (O(n))

当它说如果R的平衡因子为1"时，它是在谈论右分支的平衡因子，当顶部的平衡因子为2时.它告诉你如何选择是否做一个单转或双转.在(类似python)伪代码中:

When it says "If the balance factor of R is 1", it is talking about the balance factor of the right branch, when the balance factor at the top is 2. It is telling you how to choose whether to do a single rotation or a double rotation. In (python like) Pseudo-code:

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

我希望这是有道理的

这篇关于计算二叉搜索树高度的最佳方法?(平衡 AVL 树)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！