java - AVL树平衡

Question

我正在做一项要求我实现 AVL 树的作业。我很确定我的旋转方法是正确的，但我无法弄清楚何时使用它们。

比如书上的解释说，我应该沿着我下山的那条路往上爬，插入节点/元素。但是，我不能有任何父指针。

最新代码:

public BinaryNode<T> insert(BinaryNode<T> node) {
    if (this.getElement().compareTo(node.getElement()) > 0) {
        if (this.getLeftChild() != null) {
            BinaryNode<T> b = this.getLeftChild().insert(node);

            if(!this.isBalanced()) {
                this.balance();
            }

            return b;
        } else {
            this.setLeftChild(node);
        }

    } else if (this.getElement().compareTo(node.getElement()) < 0) {
        if (this.getRightChild() != null) {
            return this.getRightChild().insert(node);
        } else {
            this.setRightChild(node);
        }
    }

    return this;
}

我想在这里做的是爬回树上，但它只能在插入节点后检查平衡。因此，这在 else 子句中。

我还尝试将余额代码放在 R Samuel Klatchko 建议的位置，但检查了每个插入的余额。例如:如果连续插入 7、9、5、3 和 1，我在尝试插入 1 时会出现空指针异常。

编辑:上述原因之一可能与我测量高度的方式有关。如果我每次都使用 height() 计算高度，但它会打破 AVL 树的 O(log(n)) 时间，那么它可以很好地进行单次右旋转。

关于如何实现这一点有什么想法吗？

Answer 1

您的代码在您跌倒的相同路径上攀升。考虑这段代码:

if (this.getLeftChild() != null) {
    return this.getLeftChild().insert(node);
} 

稍微修改一下:

if (this.getLeftChild() != null) {
    boolean b = this.getLeftChild().insert(node);
    // do something here
    return b;
} 

随着代码从递归调用返回，每次返回都会将您带回父级。通过不立即返回递归调用的值，您有机会进行重新平衡。

更新最新代码

当你向右插入时，不要忘记重新平衡。