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塞缪尔Klatchko建议，但检查了每个插入的平衡。例如：如果一个插入7,9，5,3，和1连续地，我得到试图插入1时一个零指示字例外

。

编辑：以上的一个原因可能是与我在做高度的方式。如果我每次都计算高度与高度它正常工作与单一右旋转（），但打破了O（日志（n））的AVL树的时间。

这是如何做到这一点有什么想法？

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;
} 

由于代码从递归调用返回，每个返回带给你回父。如果不立即递归调用的返回值，你有机会做你的再平衡。

<强>更新为最新的代码

不要忘了，当你插入正确的重新平衡。

Answer 2

您可以尝试父指针传递到insert方法，或者你可以insert转换成迭代法，并保持在其上记录下来的树路径明确的堆栈。

顺便说一句，为了选择要使用的旋转，你可以知道一个节点是不平衡的，你必须知道的更深层次的子树是否是在右边或左边。这意味着你的简单isBalanced方法是不是很够。这也是效率低下，而且会吹AVL树的的 O（log n）的的复杂性，因为你每次计算的高度。