4

我正在处理一项要求我实现 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)) 时间，那么它在一次右旋转时效果很好。

关于如何做到这一点的任何想法？

4

2 回答 2

3

你的代码正在沿着你走的同一条路爬上去。考虑这段代码：

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

并稍作修改：

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

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

更新最新代码

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

于 2010-01-05T07:32:56.380 回答
1

您可以尝试将父指针传递给insert方法，或者您可以转换insert为迭代方法并保留一个显式堆栈，在该堆栈上记录树下的路径。

顺便说一句，为了选择使用哪个旋转，你可以只知道一个节点是不平衡的，你必须知道更深的子树是在右边还是在左边。这意味着您的简单isBalanced方法还不够。它也效率低下，并且会破坏 AVL 树的O(log n)复杂度，因为您每次都计算高度。

于 2010-01-05T05:42:28.597 回答