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

问题描述

我正在寻找在 AVL-tree 中计算节点余额的最佳方法。我以为我已经工作了，但经过一些沉重的插入/更新，我可以看到它不正确（总是）。

这是一个两部分的问题，第一部分将是如何计算子树的高度，我知道定义节点的高度是从该节点到叶片的最长下行路径的长度。我明白了，但是我未能实现它。为了进一步混淆我这个引用可以在树高度上的维基百科上找到通常，值-1对应于没有节点的子树，而零对应于一个具有一个节点的子树。 / p>

第二部分是在AVL树中获得子树的平衡因子，理解概念没有任何问题，获得高度的 L 和 R 子树，并减去 R 来自 L 。这个定义如下： BALANCE = NODE [L] [HEIGHT] - NODE [R] [HEIGT]

在维基百科上阅读说明在描述插入到AVL树中的前几行：如果平衡因子变为-1,0或1，那么树仍然是AVL形式，没有旋转是

然后继续说，这个如果平衡因子变为2或-2，则根据该节点的树是不平衡，需要树状旋转，最多需要单轮或双轮来平衡树。 - 我没有抓住任何麻烦。

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

这里是令人困惑的地方， em>如果R的平衡因子为1，则表示插入发生在该节点的（外部）右侧，需要左旋转。但是从理解文本中（正如我引用的），如果平衡因子在 [ - 1，1] 之内，则不需要平衡？

我觉得我非常接近这个概念，我已经把树旋转了下来，实现了一个正常的二叉搜索树，并且在抓住AVL的边缘 - / />

编辑：代码示例优于学术公式，因为我一直有更容易掌握代码中的东西，但是任何帮助都是非常感激的。

编辑：我希望我可以将所有答案标记为接受但是对于我来说，NIck的答案是第一个让我去aha的答案。

解决方案

第1部分 - 高度

如starblue所说，height只是递归。在伪代码中：

  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 like）伪代码：

  if balance factor（top）= 2：// right is不平衡
如果平衡因子（R）= 1：// 
执行左旋转
否则如果平衡因子（R）= -1：
执行双轮换
否则： /必须是-2，左边是不平衡的
如果平衡因子（L）= 1：// 
做一个左旋转
如果平衡因子（L）= -1：
做一个双轮换
  

我希望这是有道理的

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).

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."

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]

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."

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).

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?

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.

Edit: 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.

Edit: 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

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.

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))

Part 2 - balancing

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

I hope this makes sense

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