5

バランスの取れた BST (二分探索木) があるとします。各ツリー ノードには、countそのノードのすべての子孫 + ノード自体をカウントする特別なフィールドが含まれています。彼らはこれをデータ構造と呼んでいますorder statistics binary tree。

このデータ構造は、O(logN) の 2 つの操作をサポートしています。

  • rank(x)-- より小さい要素の数x
  • findByRank(k)rank-- ==でノードを見つけますk

median()ここで、中央値を見つけるための新しい操作を追加したいと思います。ツリーのバランスがとれている場合、この操作は O(1) であると想定できますか?

4

3 に答える 3

2

ツリーが完全でない限り、中央値は葉ノードである可能性があります。したがって、一般的な場合、コストは O(logN) になります。要求されたプロパティと O(1) findMedian 操作 (おそらくスキップ リスト + 中央ノードへのポインター; findByRank とランク操作についてはわかりません) を持つデータ構造があると思いますが、バランスの取れた BST はありません。それらの中の一つ。

于 2012-08-10T13:48:35.330 に答える
1

ツリーが完全である場合 (つまり、すべてのレベルが完全に埋められている場合)、はい、できます。

于 2012-08-10T12:22:26.743 に答える
1

平衡順序統計ツリーでは、中央値を見つけるのは O(log N) です。O(1) 時間で中央値を見つけることが重要な場合は、中央値へのポインターを維持することでデータ構造を拡張できます。もちろん、問題は、挿入または削除操作のたびにこのポインターを更新する必要があることです。ポインターの更新には O(log N) の時間がかかりますが、これらの操作には既に O(log N) の時間がかかるため、中央値ポインターを更新する余分な作業によって big-O コストが変わることはありません。

実際問題として、これは、挿入/削除の数と比較して多くの「中央値を見つける」操作を行う場合にのみ意味があります。

必要に応じて、 (二重に) スレッド化されたバイナリ ツリーを使用して、挿入/削除中に中央値ポインターを O(1) に更新するコストを削減できますが、挿入/削除は依然として O(log N) になります。

于 2012-08-11T20:39:42.637 に答える