非常に大きなバイナリ ツリー (つまり、数百万のノード) が与えられた場合、ツリー内のノード数の決定をどのように処理しますか? つまり、このツリーのルート ノードを関数に指定すると、関数はツリー内のノードの数を返す必要があります。
または、ツリーに非常に多数のノードがある場合、バイナリ ツリーが BST であるかどうかをどのように確認しますか?
2 に答える
1
すべてのノードをウォークし、必要な条件/メトリックを確認します。ツリーに関する追加の知識がなければ、他に何もできません。
ツリーの作成時に特定の条件を適用したり (つまり、バランス/ソート/何でもする必要があります)、作成時にツリーに関する情報を収集したり (つまり、子の数を保存して常に更新したり) できます。
于 2012-11-21T16:47:34.970 に答える
0
有効な bst かどうかを確認するには、最初にすべてのノードの深さにアクセスし、各ノードが前のものよりも小さいことを確認する必要があります。
バランスの取れたBSTにかかる時間を評価したい場合は、片足の長さを数えることでサイズの簡単な概算を得ることができます.合計サイズは2^(n-1)と2^nの間になると思います. -1 を含む
于 2018-04-18T18:48:12.777 に答える