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 を挿入しようとすると null ポインター例外が発生します。

編集：上記の理由の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 に答える