1

O(1) の時間でバイナリ検索ツリーの高さを微調整する必要があります。これを行うには、add メソッドと remove メソッドにチェックを入れて、グローバル カウンターをインクリメントする必要があります。他に方法はありますか?

4

2 に答える 2

3

O(1) time は、要求されたときにすでに高さを持っている必要があることを示唆しています。

最良の方法は、新しいノードが追加/削除されるたびに正しい値を保持/更新することです。正しい方法で行っていますが、追加と削除の複雑さが増します。

ツリー内のノードとともに深さの値を保持するなど、さまざまな方法で実行できます。

class Node{
int depth;
Object value;
}

Node lowestNode;

最大深度ノード参照をオブジェクトに格納し、それを depth として保持することを考えることができます。したがって、新しい要素を追加するときはいつでも、その親に基づいて要素の深さを確認し、新しい要素がより深い場合は最大深さノードを置き換えることができます。

最大深度ノードを削除する場合は、それを親に置き換えます。それ以外の場合は、ツリーに沿ってすべての要素の深度を再帰的に修正します。

木の高さは、lowestNode.depth

于 2013-03-04T01:51:22.053 に答える
2

高さの属性を保存し、追加/削除を行うときにそれを更新することが最も合理的な解決策です。

ツリーのバランスが取れていることが保証されている場合 (AVL など)、ツリー内の要素の数で高さを計算できます (ただし、要素の数を保持する必要があります :P )

于 2013-03-04T01:50:58.533 に答える