0

私の AVL ツリーの実装では、左、右、および親のポインターとバランス変数を持つノードがあります。新しいノードを挿入して必要なローテーションを実行するたびに、左のサブツリーから右のサブツリーを差し引いてバランスを更新しています。問題のこのメソッドは、高さを計算するためにそれ自体を再帰的に呼び出します。

問題の方法：

private int getHeight(Node nd){
    if (nd != null){
        if (nd.getLeft() == null && nd.getRight() == null)
            return 0;
        else if (nd.getLeft() == null)
            return getHeight(nd.getRight()) + 1;
        else if (nd.getRight() == null)
            return getHeight(nd.getLeft()) + 1;
        else
            return Math.max(getHeight(nd.getLeft()), getHeight(nd.getRight())) + 1;
    }
    else return -1;
}

私の質問は、AVL Tree Insert の時間計算量はO(log n)であるため、この方法はこの時間計算量に影響を与えると思います。それを修正するために何ができますか？

4

3 に答える 3

1

各挿入のすべてのノードのバランス係数を計算する必要はありません。

バランス2または-2のノードに到達し、それらを回転させながら、挿入されたノードの親とその親を計算する必要があります。

この方法でテーマを回転させる方法がわからない場合（どの回転が適切か）、私に知らせてください

于 2013-01-14T19:12:03.637 に答える
1

ヒント：新しいバランスを計算するのに高さは必要ありません。ノードとその左右の子の古いバランス値で十分です。

于 2013-01-14T08:04:37.460 に答える
1

高さは必要ありません。古いバランスを知っていると、バランスを保つことができます。とはいえ、ローテーションをまだ書いていない場合は、「移動」するたびにバランスを更新し続けるように、おそらくローテーションを調整する必要があります。

于 2013-01-14T08:07:29.727 に答える