私はhttp://discuss.joelonsoftware.com/default.asp?interview.11.780597.8でMorrisInOrderトラバーサルを使用して与えられた解決策に出くわしました。これを使用して、O(n)時間の中央値を見つけることができます。
しかし、同じ使用O(logn)時間を達成することは可能ですか？同じことがここで尋ねられました-http://www.careercup.com/question?id =192816
7441 次
3 に答える
5
ノードの左右の子孫の数のカウントも維持する場合、中央の位置を検索することで、O(logN) 時間で実行できます。実際、O(logn) 時間で k 番目に大きい要素を見つけることができます。
もちろん、これはツリーのバランスが取れていることを前提としています。カウントを維持しても、挿入/削除の複雑さは変わりません。
ツリーのバランスが取れていない場合は、最悪の場合の複雑さが Omega(n) になります。
参照:注文統計ツリー。
ところで、BigO と Smallo は大きく異なります (タイトルは Smallo です)。
于 2010-08-18T19:26:25.170 に答える
4
ある種のバランスの取れたツリーを保証しない限り、それは不可能です。
完全に縮退したツリーを考えてみましょう。たとえば、すべてのleftポインタが NULL (nil など) であるため、各ノードには適切な子しかありません (つまり、すべての実際的な目的のために、「ツリー」は実際には 1 つリンクされたリストです)。
この場合、中央値ノードにアクセスするだけでも (まったく) 直線的な時間がかかります。ノード N が中央値であることを最初から知っていたとしても、そのノードに到達するには N ステップが必要です。
于 2010-08-18T19:31:39.273 に答える
0
rabbitとturtleポインターを使用して中央値を見つけることができます。ウサギは、BST の順序通りのトラバーサルでカメの 2 倍の速さで移動します。このようにして、ウサギがトラバーサルの終わりに到達すると、カメは BST の中央値に入ります。
完全な説明を参照してください。
于 2011-01-25T05:42:09.197 に答える