AVL Tree的平衡过程

Question

根据我对AVL树的理解，对于每个节点，左右子树的高度最多相差1。

这是我想出的代码，可以在插入新节点时平衡高度。下面的方法会从新节点开始向上传播直到root

重复执行

private Node balance(Node x) {
    if (Math.abs(height(x.left) - height(x.right)) <= 1) {
        return x;
    }
    // left sub tree is heavier than right sub tree
    if (height(x.left) > height(x.right)) {
        // right sub tree of left sub tree is heavier than left sub tree of left sub tree
        if (height(x.left.left) < height(x.left.right)) {
            leftRotate(x.left);
        }
        return rightRotate(x);
    }
    // right sub tree is heavier than left sub tree
    else {
        // left sub tree of right sub tree is heavier than right sub tree of right sub tree
        if (height(x.right.left) > height(x.right.right)) {
            rightRotate(x.right);
        }
        return leftRotate(x);
    }
}

当我查看MIT solutions (Page 5)时，如果节点插入到不平衡节点的左子树的左子树中，他们似乎正在执行左旋转然后右旋转：

按照我的理解，如果我们在不平衡节点的左子树的左子树中插入一个节点，我们应该只右旋转，而不是左旋转和随后的右旋转。

我在这里错过了什么？我是否正确实施了它？

Answer 1

您确实在第 5 页的 referenced document 中发现了一个错误。

第4页的图片是正确的，但是第5页的实现是错误的，可能是错别字。

从逻辑上讲，第 4-7 行应该在左右方向上反映第 8-11 行。考虑到这一点，显然那里有一个错误。

第 5 行应该交换 left 和 right -- 或者使用 < 而不是 >归结为同一件事——像这样：

5 if 高度(左[y]) < 身高(右[y])

您的实施在这方面是正确的。

AVL Tree的平衡过程

Balance procedure of AVL Tree

algorithm

data-structures

binary-search-tree

avl-tree