AVL树平衡

我正在做一项作业，要求我实现 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)) 时间。

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

您的代码正在沿着您所走的路向上爬。考虑这段代码：

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

并稍微修改一下：

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

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

更新最新代码

当您插入右侧时，不要忘记重新平衡。