66

我正在寻找在AVL-tree中计算节点余额的最佳方法。我以为我可以正常工作，但是经过一些繁重的插入/更新后，我可以看到它（根本）无法正常工作。

这是一个两部分的问题，第一部分是如何计算子树的高度，我知道定义“节点的高度是从该节点到叶子的最长向下路径的长度。” 我理解它，但我未能实施它。为了让我更加困惑，这句话可以在 wikipedia on tree-heights 上找到“通常，值 -1 对应于没有节点的子树，而 0 对应于具有一个节点的子树。”

第二部分是获取 AVL 树中子树的平衡因子，我对“获取您的树和子树的高度并从中减去”LRRL这个概念没有问题。这被定义为这样的：BALANCE = NODE[L][HEIGHT] - NODE[R][HEIGT]

在维基百科上阅读描述插入 AVL 树的前几行是这样说的：“如果平衡因子变为 -1、0 或 1，那么树仍然是 AVL 形式，不需要旋转。”

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

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

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

我觉得我已经非常接近掌握这个概念了，我已经降低了树的旋转，实现了一个正常的二叉搜索树，并且在掌握 AVL 树的边缘，但似乎只是缺少了那个重要的顿悟。

编辑：代码示例优于学术公式，因为我总是更容易掌握代码中的某些内容，但非常感谢任何帮助。

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

4

9 回答 9

82

第 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

我希望这是有道理的

于 2009-02-22T21:37:36.863 回答
8

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

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

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

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

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

于 2009-03-24T21:23:12.370 回答
6

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

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

于 2009-02-22T21:31:08.533 回答
4

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

好的，顿悟时间。

考虑一下旋转的作用。让我们考虑一下左旋转。

 P = parent
 O = ourself (the element we're rotating)
 RC = right child
 LC = left child (of the right child, not of ourself)

 P              10
  \               \
   O               15
    \                \
     RC               20
    /                /
   LC               18

          ↓
 P              10
   \               \
     RC              20
   /               /
  O              15
   \               \
   LC              18

 basically, what happens is;

 1. our right child moves into our position
 2. we become the left child of our right child
 3. our right child's left child becomes our right

现在，您必须在这里注意一件大事——左旋转并没有改变树的深度。我们已经不再平衡了。

但是 - 这就是 AVL 的魔力 - 如果我们将正确的孩子旋转到正确的 FIRST，我们将拥有的是......

 P
  \
   O
    \
     LC
      \
       RC

现在，如果我们向左旋转 O，我们得到的是……

 P
   \
     LC
    /  \
   O   RC

魔法！我们已经设法摆脱了树的一个层次——我们已经使树平衡了。

平衡树意味着摆脱多余的深度，并更完整地打包上层——这正是我们刚刚所做的。

关于单/双旋转的全部内容就是你必须让你的子树看起来像这样；

 P
  \
   O
    \
     LC
      \
       RC

在您旋转之前 - 您可能需要进行正确的旋转才能进入该状态。但是，如果您已经处于该状态，则只需进行左旋转即可。

于 2009-03-24T21:30:34.617 回答
4

这是另一种查找高度的方法。向您的节点添加一个名为 height 的附加属性：

class Node
{
data value; //data is a custom data type
node right;
node left;
int height;
}

现在，我们将对树进行简单的广度优先遍历，并不断更新每个节点的高度值：

int height (Node root)
{
Queue<Node> q = Queue<Node>();
Node lastnode;
//reset height
root.height = 0;

q.Enqueue(root);
while(q.Count > 0)
{
   lastnode = q.Dequeue();
   if (lastnode.left != null){
      lastnode.left.height = lastnode.height + 1; 
      q.Enqueue(lastnode.left);
   }

   if (lastnode.right != null){
      lastnode.right.height = lastnode.height + 1;
      q.Enqueue(lastnode.right);
   }
}
return lastnode.height; //this will return a 0-based height, so just a root has a height of 0
}

干杯，

于 2010-10-30T20:54:55.137 回答
2

好吧，您可以使用以下递归函数计算树的高度：

int height(struct tree *t) {
    if (t == NULL)
        return 0;
    else
        return max(height(t->left), height(t->right)) + 1;
}

max()和的适当定义struct tree。您应该花时间弄清楚为什么这与您引用的基于路径长度的定义相对应。此函数使用零作为空树的高度。

但是，对于像 AVL 树这样的东西，我认为您实际上不会在每次需要时计算高度。相反，每个树节点都增加了一个额外的字段，该字段记住以该节点为根的子树的高度。当树被插入和删除修改时，该字段必须保持最新。

我怀疑，如果您每次都计算高度而不是像上面建议的那样将其缓存在树中，那么 AVL 树的形状将是正确的，但它不会具有预期的对数性能。

于 2009-02-22T21:49:13.717 回答
2

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

R是当前节点的右手子节点N。

如果balance(N) = +2，那么您需要某种轮换。但是使用哪个轮换？好吧，这取决于balance(R)：如果balance(R) = +1那么您需要左旋转N; 但是如果balance(R) = -1那样的话，您将需要某种双重旋转。

于 2009-02-22T21:52:27.653 回答
0

给BinaryTree<T, Comparator>::Node一个subtreeHeight数据成员，在其构造函数中初始化为 0，并且每次都自动更新：

template <typename T, typename Comparator>
inline void BinaryTree<T, Comparator>::Node::setLeft (std::shared_ptr<Node>& node) {
    const std::size_t formerLeftSubtreeSize = left ? left->subtreeSize : 0;
    left = node;
    if (node) {
        node->parent = this->shared_from_this();
        subtreeSize++;
        node->depthFromRoot = depthFromRoot + 1;
        const std::size_t h = node->subtreeHeight;
        if (right)
            subtreeHeight = std::max (right->subtreeHeight, h) + 1;
        else
            subtreeHeight = h + 1;
    }
    else {
        subtreeSize -= formerLeftSubtreeSize;
        subtreeHeight = right ? right->subtreeHeight + 1 : 0;
    }
}

template <typename T, typename Comparator>
inline void BinaryTree<T, Comparator>::Node::setRight (std::shared_ptr<Node>& node) {
    const std::size_t formerRightSubtreeSize = right ? right->subtreeSize : 0;
    right = node;
    if (node) {
        node->parent = this->shared_from_this();
        subtreeSize++;
        node->depthFromRoot = depthFromRoot + 1;
        const std::size_t h = node->subtreeHeight;
        if (left)
            subtreeHeight = std::max (left->subtreeHeight, h) + 1;
        else
            subtreeHeight = h + 1;
    }
    else {
        subtreeSize -= formerRightSubtreeSize;
        subtreeHeight = left ? left->subtreeHeight + 1 : 0;
    }
}

请注意，数据成员subtreeSize和depthFromRoot也会更新。插入节点时会调用这些函数（所有已测试），例如

template <typename T, typename Comparator>
inline std::shared_ptr<typename BinaryTree<T, Comparator>::Node>
BinaryTree<T, Comparator>::Node::insert (BinaryTree& tree, const T& t, std::shared_ptr<Node>& node) {
    if (!node) {
        std::shared_ptr<Node> newNode = std::make_shared<Node>(tree, t);
        node = newNode;
        return newNode;
    }
    if (getComparator()(t, node->value)) {
        std::shared_ptr<Node> newLeft = insert(tree, t, node->left);
        node->setLeft(newLeft);
    }
    else {
        std::shared_ptr<Node> newRight = insert(tree, t, node->right);
        node->setRight(newRight);
    }
    return node;
}

如果删除节点，请使用不同版本的removeLeftandremoveRight替换subtreeSize++;为subtreeSize--;. 和的算法rotateLeft也rotateRight可以毫无问题地进行调整。以下测试并通过：

template <typename T, typename Comparator>
void BinaryTree<T, Comparator>::rotateLeft (std::shared_ptr<Node>& node) {  // The root of the rotation is 'node', and its right child is the pivot of the rotation.  The pivot will rotate counter-clockwise and become the new parent of 'node'.
    std::shared_ptr<Node> pivot = node->right;
    pivot->subtreeSize = node->subtreeSize;
    pivot->depthFromRoot--;
    node->subtreeSize--;  // Since 'pivot' will no longer be in the subtree rooted at 'node'.
    const std::size_t a = pivot->left ? pivot->left->subtreeHeight + 1 : 0;  // Need to establish node->heightOfSubtree before pivot->heightOfSubtree is established, since pivot->heightOfSubtree depends on it.
    node->subtreeHeight = node->left ? std::max(a, node->left->subtreeHeight + 1) : std::max<std::size_t>(a,1);
    if (pivot->right) {
        node->subtreeSize -= pivot->right->subtreeSize;  // The subtree rooted at 'node' loses the subtree rooted at pivot->right.
        pivot->subtreeHeight = std::max (pivot->right->subtreeHeight, node->subtreeHeight) + 1;
    }
    else
        pivot->subtreeHeight = node->subtreeHeight + 1;
    node->depthFromRoot++;
    decreaseDepthFromRoot(pivot->right);  // Recursive call for the entire subtree rooted at pivot->right.
    increaseDepthFromRoot(node->left);  // Recursive call for the entire subtree rooted at node->left.
    pivot->parent = node->parent;
    if (pivot->parent) {  // pivot's new parent will be its former grandparent, which is not nullptr, so the grandparent must be updated with a new left or right child (depending on whether 'node' was its left or right child).
        if (pivot->parent->left == node)
            pivot->parent->left = pivot;
        else
            pivot->parent->right = pivot;
    }
    node->setRightSimple(pivot->left);  // Since pivot->left->value is less than pivot->value but greater than node->value.  We use the NoSizeAdjustment version because the 'subtreeSize' values of 'node' and 'pivot' are correct already.
    pivot->setLeftSimple(node);
    if (node == root) {
        root = pivot;
        root->parent = nullptr; 
    }
}

在哪里

inline void decreaseDepthFromRoot (std::shared_ptr<Node>& node) {adjustDepthFromRoot(node, -1);}
inline void increaseDepthFromRoot (std::shared_ptr<Node>& node) {adjustDepthFromRoot(node, 1);}

template <typename T, typename Comparator>
inline void BinaryTree<T, Comparator>::adjustDepthFromRoot (std::shared_ptr<Node>& node, int adjustment) {
    if (!node)
        return;
    node->depthFromRoot += adjustment;
    adjustDepthFromRoot (node->left, adjustment);
    adjustDepthFromRoot (node->right, adjustment);
}

这是整个代码：http: //ideone.com/d6arrv

于 2015-10-24T00:16:17.470 回答
0

这种类似 BFS 的解决方案非常简单。只需一个接一个地跳级。

def getHeight(self,root, method='links'):
    c_node = root
    cur_lvl_nodes = [root]
    nxt_lvl_nodes = []
    height = {'links': -1, 'nodes': 0}[method]

    while(cur_lvl_nodes or nxt_lvl_nodes):
        for c_node in cur_lvl_nodes:
            for n_node in filter(lambda x: x is not None, [c_node.left, c_node.right]):
                nxt_lvl_nodes.append(n_node)

        cur_lvl_nodes = nxt_lvl_nodes
        nxt_lvl_nodes = []
        height += 1

    return height
于 2017-10-16T14:34:56.180 回答