AVL树平衡 [英] AVL Tree Balancing

问题描述

我正在处理一项要求我实施AVL树的任务.我很确定我有正确的旋转方法，但是在弄清楚何时使用它们时遇到了麻烦.

I am working on an assignment that asks me to implement an AVL tree. I'm pretty sure I have the rotation methods correct, but I'm having trouble figuring out when to use them.

例如，书中的解释说，我应该沿着向下插入节点/元素的路径向上爬.但是，我没有任何父指针.

For example, the explanation in the book says that I should climb up the same path I went down to insert the node/element. However, I can't have any parent pointers.

最新代码:

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子句中.

What I want to do here is climb back up the tree, but it can only check the balancing AFTER it inserts the node. Hence, this being in the else clause.

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

I also tried putting the balance code where R Samuel Klatchko suggested, but checked the balance on each insert. For example: If one inserts 7, 9, 5, 3, and 1 consecutively, I get a null pointer exception when trying to insert 1.

上述原因之一可能与我的身高高低有关.如果我每次使用height()来计算高度，它在向右旋转时都可以正常工作，但这会破坏AVL树的O(log(n))时间.

One reason for the above may have something to do with the way I was doing the height. It works fine with a single right rotation if I calculate the height every time with height() but that breaks the O(log(n)) time of an AVL Tree.

关于如何实现这一目标的任何想法?

Any thoughts on how to accomplish this?

推荐答案

您的代码正在沿着您所走的相同路径攀登.考虑以下代码:

You code is climbing up the same path you went down. Consider this code:

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

并稍加修改:

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

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

As the code returns from the recursive calls, each return brings you back to the parent. By not immediately returning the value of the recursive call, you have a chance to do your rebalancing.

更新最新代码

在右侧插入时，别忘了重新平衡.

Don't forget to rebalance when you've inserted to the right.

这篇关于AVL树平衡的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！