1

所以我很难理解如何平衡 AVL 树。我了解旋转的东西，但我不知道如何找到节点高度的平衡因子，例如：

http://i.imgur.com/yh5zNIl.png

谁能向我解释一下我们实际上是如何找到每个节点的平衡因子的？

我知道 [(left subtree) - (right subtree)] 的高度是否不在 (-1<= x <= 1) 范围内，那么它不平衡......但我不知道如何找到“x”。

（编辑：我不需要代码，我只想了解如何找到BF）。

4

3 回答 3

1

如果我正确理解您的问题，您想知道如何维护给定节点的平衡因子。保持跟踪的最佳方法是在树中进行“插入”。这是因为您知道您的新节点是在“当前”节点的左侧还是右侧。当它向左时，你减少余额，当它向右时，你增加余额。这个想法是在退出“插入”方法之前让树已经平衡。

我见过的另一种方法是在“插入”期间不进行平衡。您只需像在 BST 中一样插入即可。插入后，您开始平衡操作，在每个节点处获取左子树和右子树高度并开始洗牌指针。这不是一个好方法，因为在查找高度时每个节点都会产生 O(logn)，并且因为你会对每个节点都这样做，所以它会导致 n*O(logn)。

我正在发布我曾经编写过的“插入”方法，该方法使树在每次插入时保持平衡，并且不会在插入期间的任何点单独计算高度。看看是否有帮助：

Node*
AVL::insert(Node* node, int key, int value)
{
    if(node == NULL)
        node = new Node(key, value);

    else if (key <= node->key)
    {
        node->balance--;
        node->left = insert(node->left, key, value);
    }

    else if (key > node->key)
    {
        node->balance++;
        node->right = insert(node->right, key, value);  
    }

    // Right Tree Heavy
    if (node->balance == 2) 
    { 
        // Left tree unbalanced
        if (node->right && node->right->balance == 1) 
        {
            // LL
            node = singleLeftRotation(node);
            node->balance = 0;
            node->left->balance = 0;
        }
        if (node->right && node->right->balance == -1) 
        {
            // LR
            int nodeRLBalance = node->right->left->balance;
            node = doubleLeftRotation(node);
            node->balance = 0;
            node->left->balance = nodeRLBalance == 1 ? -1 : 0;
            node->right->balance = nodeRLBalance == -1 ? 1 : 0;
        }
    }

    // Left Tree Heavy
    if (node->balance == -2) 
    {
        // Right tree unbalanced
        if (node->left && node->left->balance == -1) 
        {
            // RR
            node = singleRightRotation(node);
            node->balance = 0;
            node->right->balance = 0;
        }
        if (node->left && node->left->balance == 1) 
        {
            // RL
            int nodeLRBalance = node->left->right->balance;
            node = doubleRightRotation(node);
            node->balance = 0;
            node->left->balance = nodeLRBalance == 1 ? -1 : 0;
            node->right->balance = nodeLRBalance == -1 ? 1 : 0;
        }
    }

    return node;
}
于 2013-10-06T18:09:54.767 回答
1

X 是左子树的高度——右子树的高度。

如果左子树的最大高度为 3，右子树的最大高度为 2，则平衡因子为

3 - 2 = Balance Factor of 1 (Left Heavy)

另一种方式：

2 - 3 = Balance Factor of -1 (Right Heavy)

如果两者相同：

3 - 3 = Balance Factor of 0 (Even Heavy)

当高度差大于 1 或小于 -1 时，树就会变得不平衡。

5 - 3 = Balance Factor of 2 (UNBALANCED!)
3 - 5 = Balance Factor of -2 (UNBALANCED!)
于 2019-02-24T10:55:59.477 回答
1

一个节点的平衡因子是它的左右后代节点的高度差。

平衡因子被一些人定义为： balance = node.left.height - node.right.height

和其他为： balance = node.right.height - node.left.height

因此，如果您想了解图表中某些节点的平衡，您必须知道它们如何定义平衡因子。

例如 wikipedia 将其定义为 node.left.height - node.right.height 并且您可以看到公式结果与节点平衡因子 Avl Tree Balance of Nodes Example匹配

于 2017-04-26T14:09:02.867 回答